Cтраница 3
Мы, с нашим человеческим интеллектом, можем вывести некое истинное утверждение теории чисел, истинность которого компьютер не в состоянии заметить ( то есть, компьютер никогда не выведет этого утверждения) именно из-за Геделева аргумента, действующего как бумеранг. [31]
Для любого заданного утверждения X и любого множества положительных целых чисел А мы будем называть X геделевым утверждением для А, если либо X истинно и его геделев номер принадлежит А, либо X ложно и его геделев номер не принадлежит А. Подобное утверждение можно представлять себе как высказывание о том, что его собственный геделев номер принадлежит А: если это утверждение истинно, то его геделев номер действительно принадлежит А; если же оно ложно, то его геделев номер не принадлежит А. Далее, мы будем называть систему геделевой в том случае, если для каждого множества А, допускающего наименование в этой системе, существует хотя бы одно геделево утверждение для А. [32]
Геделева нумерующая присваивает выражениям ( из некоторого множества) натуральные числа ( называемые геделевыми номерами этих выражений); при этом должны выполняться следующие условия: ( 1) разным выражениям присвоены разные геделевы номера; ( 2) геделев номер любого выражения эффективно вычисляется по выражению; ( 3) эффективно разрешим вопрос о том, является ли число геделевым номером некоторого выражения из рассматриваемого множества выражений, и, если является, эффективно находится выражение, имеющее этот геделев номер. [33]
Так как множество символов, которые могут встретиться в предложениях языка теории Т, разрешимо ( по ранее сделанному предположению), то множество предложений языка теории Т само разрешимо, т.е. существует машина Тьюринга, которая, получив число в качестве входного значения, выдает в качестве результата 1 тогда и только тогда, когда это число есть геделев номер предложения языка теории Т, и 0 в противном случае. [34]
Геделева нумерующая присваивает выражениям ( из некоторого множества) натуральные числа ( называемые геделевыми номерами этих выражений); при этом должны выполняться следующие условия: ( 1) разным выражениям присвоены разные геделевы номера; ( 2) геделев номер любого выражения эффективно вычисляется по выражению; ( 3) эффективно разрешим вопрос о том, является ли число геделевым номером некоторого выражения из рассматриваемого множества выражений, и, если является, эффективно находится выражение, имеющее этот геделев номер. [35]
Геделева нумерация ( 2) для N х N показывает, что такие по-прежнему замкнуты относительно конечных произведений. [36]
Открыв Геделеву нумерацию и построенный на ее основе изоморфизм, мы в каком-то смысле расшифровали код, на котором высказывания о системе MIU записаны при помощи строчек ТТЧ. Геделев изоморфизм - это новый обнаружитель информации, в том же смысле, как дешифровки старинных текстов были обнаружителями заложенной в этих текстах информации. [37]
Подобная ситуация рассматривается в последней главе моей книги Как же называется эта книга. Дважды геделевы острова, к которому мы и отсылаем читателя. [38]
Предположим, что данная система является геделевой и что условия Gt и G2 выполняются; предположим также, что система правильна. Однако если геделев номер утверждения X принадлежит Р, то тем самым он не принадлежит Р, а это значит, что утверждение X недоказуемо. [39]
Если В ( х) - формула первого или второго порядка, то говорят, что она определяет множество 6 в арифметике второго порядка, если для любого натурального числа k тогда и только тогда имеет место k G 0, когда B ( k) истинна в Л /; в этом случае говорят, что множество 0 определимо в арифметике второго порядка. Предположим, наша геделева нумерующая продолжена таким образом, что предложениям второго порядка приписаны геделевы номера. Покажите, что ни множество геделевых номеров истинных предложений второго порядка языка L, ни множество геделевых номеров общезначимых предложений второго порядка не определимы в арифметиках второго порядка. [40]
Рассмотрим некоторое конкретное множество выражений и конкретную геделеву нумерующую. Слова выражение и геделев номер будут относиться в дальнейшем именно к ним. В этой конкретной геделевой нумерующей нет ничего специфического; теоремы и доказательства, приводимые нами и базирующиеся на этой нумерующей, остаются верными и относительно любой другой геделевой нумерующей. [41]
По-видимому, самым коротким доказательством неполноты теории Z является следующее. Пусть п - геделев номер формулы G ( x), выражающей х не является самоприменимой. Если п самоприменимо, G ( n) ложно в доказуемо, что невозможно; таким образом, п не является самоприменимым и 7 ( п) является недоказуемой и истинной. [42]
Опишем несколько более точно природу конечных последовательностей предложений: каждая такая последовательность может быть отождествлена с выражением, состоящим из тех же предложений, расположенных в том же порядке, но разделенных запятыми. Поскольку запятой уже приписан геделев номер 29, каждое доказательство в Z приобретает свой собственный геделев номер вследствие такого отождествления. [43]
Я хотел попытаться проимитировать автореферентную Геделеву схему - а она, как вы знаете, косвенна и зависит от изоморфизма, установленного при помощи Геделевой нумерации. [44]
В [1] вводится соглашение обозначать 50 символом р, а 1 вводится для Si. Так как символу Si соответствует в [1] геделев номер 24 7, то р, 1 и 0 получают геделевы номера 27, 211 и 215 соответственно. Мы будем свободно использовать здесь эти соглашения. [45]