Cтраница 2
Предположим, что данная система является геделевой и что условия Gt и G2 выполняются; предположим также, что система правильна. Однако если геделев номер утверждения X принадлежит Р, то тем самым он не принадлежит Р, а это значит, что утверждение X недоказуемо. [16]
Очевидно, что наша геделева нумерующая действительно является геделевой нумерующей в смысле второго абзаца. [17]
Если система удовлетворяет условию GJ, то эта система является геделевой. [18]
Мы исходим из предположения, что условиям некоторым разумным образом приписаны геделевы номера. По меньшей мере это означает, что отношения R, равное ( г, j) г является геделевым номером условия, усиливающего условие с геделевым номером j, и 5, равное k, m) k является геделевым номером условия, содержащего Gm, рекурсивны и, таким образом, определимы в арифметике. С ( х, у), определяющую отношение i, k) qi имеет геделев номер k в арифметике. Но тогда, если D ( y z) определяет 5, то формула ЗхЗу ( С ( х у) & D ( y z)) определяет А в арифметике. [19]
А В) тогда и только тогда, когда е - геделев номер такой одноместной частично рекурсивной функции р, что для любого натурального числа а, если. [20]
Существует рекурсивная функция, diag, такая, что если п - геделев номер выражения А, то diag ( n) - геделев номер диагонализации выражения А. [21]
Xn-Наконец, при помощи Encoderi мы затем определим функцию Initn, которая дает геделев номер начального мгновенного описания, лента которого содержит двоичную запись п аргументов Initn, взятых в том же порядке. [22]
Теорема 5.4. Выводы и и v подобны тогда и только тогда, когда совпадают их геделевы номера. [23]
Обычно считается, что ТТЧ и подобные ей системы со - непротиворечивы, и что Геделева строчка, которая может быть выведена в данной системе, неразрешима внутри этой системы. [24]
Будем считать списки индивидных переменных, переменных предикатов и переменных операций достаточно хорошими и подразумевать некоторую геделеву нумерацию формул. [25]
Доопределим теперь геделеву нумерующую так, чтобы всем конечным последовательностям символов табл. 15 - 1 были приписаны геделевы номера. Мы не делаем различия между отдельным символом и последовательностью, состоящей из одного этого символа. [26]
Существует рекурсивная функция, diag, такая, что если п - геделев номер выражения А, то diag ( n) - геделев номер диагонализации выражения А. [27]
Последний иронический штрих для доказательства теоремы Геделя о неполноте потребовалось внедрить парадокс Эпименида прямо в сердце Оснований математики - бастиона, считавшегося недоступным для Странных Петель Хотя Геделева Странная Петля и не разрушила Оснований математики, она сделала их гораздо менее интересными для математиков, доказав иллюзорность цели, первоначально поставленной Расселом и Уайтхедом. [28]
Для любого заданного утверждения X и любого множества положительных целых чисел А мы будем называть X геделевым утверждением для А, если либо X истинно и его геделев номер принадлежит А, либо X ложно и его геделев номер не принадлежит А. Подобное утверждение можно представлять себе как высказывание о том, что его собственный геделев номер принадлежит А: если это утверждение истинно, то его геделев номер действительно принадлежит А; если же оно ложно, то его геделев номер не принадлежит А. Далее, мы будем называть систему геделевой в том случае, если для каждого множества А, допускающего наименование в этой системе, существует хотя бы одно геделево утверждение для А. [29]
Геделева нумерующая присваивает выражениям ( из некоторого множества) натуральные числа ( называемые геделевыми номерами этих выражений); при этом должны выполняться следующие условия: ( 1) разным выражениям присвоены разные геделевы номера; ( 2) геделев номер любого выражения эффективно вычисляется по выражению; ( 3) эффективно разрешим вопрос о том, является ли число геделевым номером некоторого выражения из рассматриваемого множества выражений, и, если является, эффективно находится выражение, имеющее этот геделев номер. [30]