Cтраница 1
Знаменитые теоремы Геделя о неполноте и теорема Черча о неразрешимости доказаны в гл. Здесь авторы следуют современной манере изложения, которая состоит в доказательстве в общем виде леммы о диагонализации, а затем применении этой леммы к формуле для геделевых номеров недоказуемых формул. [1]
Знаменитая теорема Геделя о неполноте [1931] предстг ляет собой один из многих результатов о формальной арифи тике, в котором теория вычислимости и логика тесно nepenj таются друг с другом. Полные доказательства этих утверж ний выходят за рамки настоящей книги. [2]
Обе знаменитые теоремы Геделя о неполноте изложены в главе VIII, причем доказательство одной леммы отложено до главы X Автору удавалось закончить эти десять глав ( а иногда даже несколько больше) в течение семестрового курса, который он неоднократно читал в Висконсинском университете. [3]
В ней содержатся начала и некоторые дополнительные главы математической логики, последовательно и строго излагаются классические теоремы о неразрешимости логики предикатов и разрешимости некоторых ее фрагментов, знаменитые теоремы Геделя о полноте, нестандартные модели и многое другое. [4]
Лейбницем, ни Булем, ни Расселом, Более того, если формулировка гильбертовской теории доказательства и дала повод для мнения о полной формализации логики ( достаточно популярного в наше время), то уже знаменитая теорема Геделя ( см. [9, 10]), с одной стороны, противопоставляемые гильбертовской интуиционистские и конструктивистские альтернативные программы [11, 12], с другой, и, наконец, стимулируемые этими идеями успешные поиски новых методов дедукции, отвечающих критерию строгой формальности 4, с третьей, показали со всей убедительностью, что процесс этот не завершен и до сих пор. [5]
Таким образом, рекурсивно-перечислимые множества образуют собственный подкласс класса арифметических множеств. Это утверждение эквивалентно знаменитой теореме Геделя о неполноте арифметики [26, 36] и вскрывает принципиальную ограниченность финитных формальных систем. В противоположность финитным формальным системам арифметические отношения представимы в К-системах. В силу теоремы 8.1, отправляясь от конечного набора элементарных арифметических отношений и применяя к ним последовательно конечное число операций объединения, пересечения, дополнения и квантификации мы придем к полному К-отношению. [6]
В частности, никто не знает, как доказать и как опровергнуть, скажем, формулу G, приведенную выше, даже используя всю мощь аналитической теории чисел, что заведомо больше довольно скромных ресурсов, заложенных в Z. В соответствии со знаменитой теоремой Геделя о неполноте неизбежное отсутствие в Z некоторых необходимых аксиом совсем не случайно. Эта теорема утверждает, что не существует формальной системы, содержащей в качестве теорем все арифметически истинные высказывания и ни одного ложного. S, использующую ту же символику, и такую, что все ее теоремы истинны и некоторые из них не встречаются среди теорем S. [7]
Заметим, кстати, что воинствующий материализм XIX-XX веков теперь присмирел и вполне уживается в целостности материального и идеального. Их концепции взаимо дополнительны согласно принципу Нильса Бора и знаменитой теореме Геделя о неполноте любого научного знания. И тут трудно согласиться с Эммануилом Кантом, что в знании столько науки, сколько математики. [8]
Так, для доказательства непротиворечивости приходится выходит ь за рамки строго финитных методов. Полнота же вообще не имеет места для построенной нами формальной арифметической системы. В этом состоит смысл знаменитой теоремы Геделя о неполноте арифметики, заставившей по-новому взглянуть на всю проблему обоснования математики и автоматизации ( на базе полной формализации) процесса вывода новых теорем в дедуктивно строящихся теориях. [9]
Допустим, что некоторый субъект произносит следующую фразу: Высказывание, которое я сейчас произношу, ложно. Ложно само это высказывание или нет. Из допущения, что оно истинно, и его смысла следует, что оно должно быть ложно. С другой стороны, из его ложности немедленно следует, что оно не может быть ложно. Известно много вариантов этого парадокса - парадокс лжеца, парадокс Эпименида и др. Идея этого парадокса лежит в основе доказательства знаменитой теоремы Геделя о неполноте формальных аксиоматических теорий. [10]