Cтраница 3
Знаменитая теорема Геделя о неполноте [1931] предстг ляет собой один из многих результатов о формальной арифи тике, в котором теория вычислимости и логика тесно nepenj таются друг с другом. Полные доказательства этих утверж ний выходят за рамки настоящей книги. [31]
Если язык Геделя лишить схемы минимизации, тогда все выразимые в нем функции будут тотальными. Эти функции называются примитивно рекурсивными. [32]
Открытие Курта Геделя - неразрешимые предложения - было впервые опубликовано в работе Гедель [1] и было применено им для установления того, что для любой системы теории чисел ее непротиворечивость не может быть доказана средствами, формализуемыми в этой системе. [33]
Заглавие статьи Геделя включало в конце римское I; это означало, что он собирался написать продолжение этой статьи с тем, чтобы подробно остановиться на особенно трудных моментах доказательства. Однако первая статья получила настолько широкое признание, что нужда в продолжении отпала, и вторая статья так и не была написана. [34]
Согласно теореме Геделя о неполноте [15], никакая система не может быть логически замкнутой: всегда можно найти такую теорему, для доказательства которой потребуется внешнее дополнение. Поэтому критерии выбора модели сложных объектов необходимо разделять на внутренние и внешние. [35]
Знаменитые теоремы Геделя о неполноте и теорема Черча о неразрешимости доказаны в гл. Здесь авторы следуют современной манере изложения, которая состоит в доказательстве в общем виде леммы о диагонализации, а затем применении этой леммы к формуле для геделевых номеров недоказуемых формул. [36]
Хофштадера Эшер, Гедель, Бах: вечная золотая связь [36], в которой золотая связь событий ассоциирована с рекурсией. [37]
На самом деле Гедель доказал, что гипотеза континуума не приводит к противоречивости теории множеств ( см. К - Гедель, Совместимость аксиомы выбора и обобщенной континуум-гипотезы с аксиомами теории множеств. [38]
Более того, Гедель показал, что невозможно доказать непротиворечивость арифметической логики ( даже неполной) теми методами, которые выразимы в самой этой логике. [39]
В этой работе Гедель показал также, что теорема о полноте верна и в некоторой усиленной форме - а именно, что всякая счетная последовательность формул, из которой нельзя вывести противоречия, выполнима. Гедель получил это усиление, показав, что если выполнима любая конечная подпоследовательность какой-либо счетной последовательности формул, то выполнима и сама эта последовательность. [40]
По второй теореме Геделя о неполноте отсюда следовало бы, что формализм ( Z), а тем более и ( Z), противоречив. [41]
Обе знаменитые теоремы Геделя о неполноте изложены в главе VIII, причем доказательство одной леммы отложено до главы X Автору удавалось закончить эти десять глав ( а иногда даже несколько больше) в течение семестрового курса, который он неоднократно читал в Висконсинском университете. [42]
Различные доказательства теоремы Геделя сравниваются в монографии Мостовского [1952], которая была недоступна автору при написании настоящей книги. [43]
Ошибка: Теорема Геделя [1932-33] не имеет места для исчисления предикатЬв, как утверждает Гейтинг на стр. [44]
В действительности теорема Геделя носит более частный характер, поскольку от формальной системы того типа, который рассматривал Гедель, требовалась адекватность по отношению к арифметическим утверждениям, а не математическим утверждениям вообще. [45]