Cтраница 3
Там показано, что непротиворечивость арифметики Та типа а доказуема в арифметике Та типа а 1, так как в 7 а 1 можно записать определение истинности для Та. Поэтому Ta i не интерпретируется в Та в силу теоремы Геделя о недоказуемости непротиворечивости. [31]
Пусть Т - цепочка [ R ( q): q ], которая, как мы видели, утверждает свою собственную недоказуемость. [32]
Помимо эквивалентов аксиомы выбора, имеется обширный класс математических предложений, которые неизвестно как доказывать без обращения к этой аксиоме или одному из ее эквивалентов. Большинство из них не носит столь общего характера, как рассматриваемая аксиома или ее эквиваленты, а представляет собой относительно частные высказывания; их обычно рассматривают не только как недоказанные без обращения к ним, но и как недоказуемые без них. В предположении такой недоказуемости естествен вопрос о том, какому частному случаю аксиомы выбора ( или ее эквивалента) равносильно то или иное предложение подобного рода. [33]
Высказывание Р возникает при подстановке в Q вместо переменной х кодового номера q высказывания Q. Следовательно, высказывание Р эквивалентно следующему: Не доказуемо, что высказывание с кодовым номером q не доказуемо. Таким образом, высказывание Р содержит утверждение о своей собственной недоказуемости. Ясно, что такое высказывание не доказуемо. Действительно, если бы оно было доказуемо, то мы могли бы доказать его недоказуемость, что противоречит самому высказыванию. Следовательно, высказывание не доказуемо, хотя и опровергнуть его также невозможно: к выводу о недоказуемости Р мы пришли путем логических рассуждений. [34]
Он серьезнейшим образом воспринял концепцию Брауэра, поддержанную Марковым, что математика по сути своей есть гуманитарная наука, и рассматривал ее как одну из отраслей мировой культуры. Сам он стеснялся публиковать философские работы ( многие математики страдают этой ложной скромностью), но его философские рассуждения на близкие к современной логике темы всегда были исключительно глубокими. В частности, именно он одним из первых в России заметил, что программа Гильберта обоснования математики вовсе не завершилась провалом. Теорема Геделя о недоказуемости непротиворечивости показала лишь неточность формулировки средств, а сама цель программы Гильберта была практически достигнута в результате метаматематических исследований по интуиционистской и конструктивной математике. Таким образом, А. Г. Драгалин еще раз подтвердил глубину воззрений Гильберта, поддержанных, кстати, его якобы непримиримым ( если судить по писаниям вульгаризаторов истории науки) оппонентом Брауэром: хотя порою в принципе идеальные понятия могут быть устранены, редукционизм и ползучий 4 эмпиризм приводят к полной умственной прострации, просто невероятно увеличивая объем выкладок. Ни до чего нетривиального мы не можем добраться без использования идеальных понятий, и чем более сильного практического результата мы желаем добиться, тем более высокую теорию надо задействовать. Другое дело, что с этой высоты надо еще суметь спуститься на грешную землю, поскольку даже операция выяснения, не является ли одно из понятий высокого уровня примером другого, уже неразрешима алгоритмически. [35]
Кант находит его проявления в общественном чувстве логич. При этом общедоступное суждение понимается Кантом как оценка, которая в своей рефлексии мысленно обращает внимание на способ представления каждого другого... Оговорка как бы подчеркивает недоказуемость искомой всеобщности логич. Гегель нелестно отзывается о грубом мериле пользы и о познават. [36]
Если мы теперь заменим предыдущую формулу на - - Ууфх ( Я ( у) уЯ ( х)) - & ( у) уУхЖ ( х), то увертка пропадает. В самом деле, , полученная в антецеденте перед - i -, превращается теперь в ( с) для некоторой переменной с. Затем, которая появляется в сук-цеденте после - 1 -, за которым теперь будет следовать - V по отношению к переменной у, превратится в ( d), где d - переменная, отличная от с, в силу ограничения на переменные для - V. Читателю предоставляется разработать, изменения доказательства ( i), чтобы недоказуемость рассматриваемой формулы была установлена строго. [37]
Ясно, что [ вь следовательно, ПЧ оХ / ПДЧ / Фо - тождественно истинное предложение. Отсюда, используя гот факт, что А истинно на системах 31, у которых отношение Vя ( Е) является равенством, получаем, что Т - - Ф также тождественно истинно. V - ПФ также было бы тождественно истинным, что противоречит условию о его недоказуемости. [38]
Высказывание Р возникает при подстановке в Q вместо переменной х кодового номера q высказывания Q. Следовательно, высказывание Р эквивалентно следующему: Не доказуемо, что высказывание с кодовым номером q не доказуемо. Таким образом, высказывание Р содержит утверждение о своей собственной недоказуемости. Ясно, что такое высказывание не доказуемо. Действительно, если бы оно было доказуемо, то мы могли бы доказать его недоказуемость, что противоречит самому высказыванию. Следовательно, высказывание не доказуемо, хотя и опровергнуть его также невозможно: к выводу о недоказуемости Р мы пришли путем логических рассуждений. [39]
Обозначим через класс проблем ( языков), решаемых ( воспринимаемых) детерминированными машинами Тьюринга за полиномиальное время, в через / Г - класс проблем ( языков), решаемых ( воспринимаемых) недетерминированными машинами Тьюринга за полиномиальное время. Возможны три варианта; 1) Ф N & 2) Ф J ty и 3) гипотезы Ф Ф Ф N & так же, как и tP N &, не доказуемы. Есть много веских доводов считать, чтоФ Ф N &, однако никому не удалось строго доказать это. В последнее время в связи о многочисленными неудачными попытками получения прямого ответа заслуживает внимания третий вариант. Аналогичные случаи уже встречались в истории математики - результат о недоказуемости континиум-гипотезы. [40]
Высказывание Р возникает при подстановке в Q вместо переменной х кодового номера q высказывания Q. Следовательно, высказывание Р эквивалентно следующему: Не доказуемо, что высказывание с кодовым номером q не доказуемо. Таким образом, высказывание Р содержит утверждение о своей собственной недоказуемости. Ясно, что такое высказывание не доказуемо. Действительно, если бы оно было доказуемо, то мы могли бы доказать его недоказуемость, что противоречит самому высказыванию. Следовательно, высказывание не доказуемо, хотя и опровергнуть его также невозможно: к выводу о недоказуемости Р мы пришли путем логических рассуждений. [41]
В частности, возникает проблема логической н е з а в н с и м о-с т и аксиом данной теории, состоящая в установлении того, что ни одна из аксиом теории не может быть чисто логически выведена из остальных аксиом. Было предпринято много тщетных попыток вывести его из остальных аксиом эвклидовой геометрии, пока, наконец, в работах Н. И. Лобачевского не было впервые в явной форме высказано убеждение в невозможности осуществить такой вывод. Это убеждение было подкреплено Лобачевским построением новой геометрии, в корне отличной от эвклидовой. В геометрии Лобачевского, тщательно разработанной ее творцом, не обнаруживалось противоречий; это вселяло уверенность в том, что противоречия и вообще не могут возникнуть, как бы далеко ни было продвинуто выведение следствий из аксиом новой геометрии. Так возникли и были частично решены исторически первые проблемы недоказуемости и непротиворечивости в аксиоматич. [42]
Путь, ведущий к преодолению этой трудности, основан на ограничении числа применений 7 - пРавила ПРИ доказательстве методом таблиц. Для этого используется метод Q-depth, заключающийся в следующем. Когда 7 - пРавило было применено максимальное число раз, которое определяется заранее в виде значения Q-depth, оно может больше никогда не применяться. Таким образом, используя метод Q-depth, можно построить замыкание расширения таблицы ( ни одно из правил не может быть применено), за конечное число шагов, и далее переходить к этапу тестирования замыкания. Таким образом, доказательства являются конечными. Если выражение X является доказуемым, то имеется доказательство, в котором сделано конечное число применений 7 - пРавила - Следовательно, если X является истинным, то оно будет доказуемо, если использовать метод Q-depth. В принципе применяя каждый раз большее значение для метода Q-depth, можно получить доказательство истинности любого выражения при условии игнорирования проблемы временной сложности и ограниченного объема памяти. С другой стороны, ложность выражения эквивалентна его недоказуемости на основе метода Q-depth любой размерности, и это никогда не может быть выполнено, даже если будет сделано бесконечное число шагов. [43]