Но поскольку это число n не принадлежит Р, то утверждение X должно быть недоказуемым в данной системе. Значит, утверждение X истинно, но недоказуемо в данной системе. Итак, теорема G действительно имеет место.
7. Пусть теперь нам даны условия G1 и G3.
а. Согласно условию G1, множество R именуемо в данной системе. Тогда, согласно условию G5, множество R* также допускает имя в рамках этой системы. Следовательно, существует такое число Н, при котором Ah = R*. Далее, по определению множества R* число х принадлежит R* в том и только том случае, если число х*х принадлежит множеству R. Поэтому для любого а это х принадлежит Ah в том и только том случае, если число х*х входит в множество R. В частности, если к качестве x выбратьh, то число h будет принадлежать, Ah, в том и только том случае, если число h*h входит в R. Далее, h принадлежит Ah в том и только том случае, если утверждение h Є Ah, истинно. С другой стороны, поскольку число h*h есть гёделев номер утверждения h Є Ah, то h*h входит в R в том и только в том случае, если утверждение h Є Ah опровержимо. Значит, утверждение h Є Ah истинно в том и только в том случае, если оно опровержимо. Отсюда следует, что данное утверждение либо истинно и опровержимо, либо ложно и неопровержимо. Однако оно не может быть истинным и опровержимым, поскольку наша система правильна по условию задачи; следовательно, оно должно быть ложным и неопровержимым. Наконец, раз это утверждение ложно, оно не может быть и доказуемым (опять же потому, что система правильна). Таким образом, утверждение h Є Ah, недоказуемо и неопровержимо (и, кроме того, оно ложно).
б. Пусть нам дано, что множество а10 — это К и что А5n при любом числе n совпадает с множеством An*. Значит, A50 есть множество R*. Тогда, согласно решению «а», если принять h = 50, то утверждение 50 Є A50 будет недоказуемым и неопровержимым. Кроме того, это утверждение будет ложным.
Машины, рассказывающие о себе
Рассмотрим теперь доказательство Гёделя с несколько иной точки зрения, которая позволяет увидеть основную идею особенно ярко.
Возьмем четыре символа Р, N, А, — , и рассмотрим всевозможные комбинации этих символов. Произвольную комбинацию указанных символов мы будем называть выражением. Например, выражением является комбинация Р-NA-Р; точно так же выражением будет комбинация — PN-А-Р-. Некоторым выражениям мы будем приписывать определенный смысл — такие выражения в дальнейшем будут называться утверждениями.
Предположим, что у нас имеется машина, которая может выдавать нам (распечатывать) одни выражения и не может выдавать другие. При этом те выражения, которые машина может напечатать, мы будем называть Допускающими распечатку. Предполагается, что любое выражение, которое может напечатать машина, рано или поздно обязательно будет ею напечатано. Если нам задано выражение X и мы хотим высказать суждение, что X допускает распечатку, то будем записывать это как Р-X. Так, например, запись Р-ANN означает, что выражение ANN допускает распечатку (при этом неважно, является ли это утверждение истинным или ложным). Если же мы хотим сказать, что выражение X не допускает распечатки, то будем писать NP-X. (Символ N — от англ. not — отрицание «не», а символ Р — от англ. printable — допускающий распечатку.) Таким образом, запись вида NP-X следует читать как «не допускающее распечатки X», или, что по существу то же самое, «выражение X не допускает распечатки».
Ассоциатом выражения X мы будем называть выражение X–X; при этом вместо слова «ассоциат» нами будет использоваться символ А (от англ. associate). Таким образом, если нам задано некоторое выражение X и мы хотим сказать, что ассоциат выражения X допускает распечатку, то будем записывать это как РА-X. Если мы теперь хотим сказать, что ассоциат утверждения X не допускает распечатки, то это будет записываться как NPA-X.
Читателя, быть может, удивляет, что мы используем тире в качестве своеобразного символа. В самом деле, почему, когда нам нужно высказать суждение о том, что выражение X допускает распечатку, вместо записи Р-X не писать просто РХ? Это делается для того, чтобы избежать определенной двусмысленности. В самом деле, что, например, может означать запись PAN, если мы откажемся от тире? Она может означать либо что ассоциат выражения N допускает распечатку, либо что допускает распечатку выражение AN. Если же мы пользуемся тире, то подобной двусмысленности не возникает. Так, если мы хотим сказать, что ассоциат выражения N допускает распечатку, то записываем этот факт как РА-N; если же хотим сказать, что допускает распечатку выражение AN, то пишем Р-AN. Предположим теперь, нам нужно сказать, что выражение — X допускает распечатку. Правильно ли будет записать эту фразу как Р-Х? Нет, ведь запись Р-X означает, что выражение X допускает распечатку. Поэтому чтобы сказать, что допускает распечатку выражение — X, нужно написать Р-X.
Рассмотрим еще несколько примеров: запись Р- означает, что «-» допускает распечатку, запись РА- означает, что выражение (ассоциат выражения-) допускает распечатку; запись Р- также означает, что «-» допускает распечатку; запись NРА-Р-А означает, что ассоциат выражения — Р-А не допускает распечатки, или, другими словами, что не допускает распечатки выражение — Р-А-Р-А. То же самое означает и запись вида NP-Р-А-Р-А.
Утверждением будем называть любое выражение одного из следующих четырех типов: Р-X, NP-X, РА-X или NPA-X, где X — любое выражение. Утверждение Р-X мы будем называть истинным, если X допускает распечатку, и ложным, если X с допускает распечатки. Утверждение NP-X мы будем называть истинным, если X не допускает распечатки, и ложным, если X эту распечатку допускает, утверждение РА-X будет называться истинным, если ассоциат выражения X допускает распечатку, и ложным, если ассоциат этого X распечатки не допускает. Наконец, утверждение NA-X мы будем называть истинным, если ассоциат выражения X не допускает распечатки, и ложным, если ассоциат этого X распечатку допускает. Итак, мы дали точное определение истинности и ложности для утверждений всех четырех видов. Отсюда следует, что для любого выражения X справедливы:
Правило 1. Утверждение Р-X истинно тогда и только тогда, когда выражение X допускает распечатку (на машине).
Правило 2. Утверждение РА-X истинно тогда и только тогда, когда выражение X–X допускает распечатку.
Правило 3. Утверждение NP-X истинно тогда и только тогда, когда выражение X не допускает распечатки.
Правило 4. Утверждение NPA-X истинно тогда и только тогда, когда выражение X–X не допускает распечатки
Удивительное дело! Машина печатает утверждения, которые представляют собой не что иное, как суждения о том, что она сама может и что не может напечатать! В этом смысле машина говорит о себе (или точнее, печатает утверждения о самой себе).
Пусть теперь нам известно, что машина на 100 % точна, то есть она не может выдать нам ложное утверждение, печатая только истинные утверждения. Отсюда вытекает ряд следствий. Например, если машина в один прекрасный день напечатает утверждение Р-X, то, значит, она должна напечатать и выражение X, потому что раз она может напечатать утверждение Р-X, то, стало быть, это утверждение истинно, а это означает, что выражение X допускает распечатку. Значит, действительно, машина рано или поздно должна распечатать выражение X.
Аналогично, если машина выдаст нам утверждение РА-X, тогда (поскольку утверждение РА-X должно быть истинным) она должна напечатать нам также и выражение X–X.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
7. Пусть теперь нам даны условия G1 и G3.
а. Согласно условию G1, множество R именуемо в данной системе. Тогда, согласно условию G5, множество R* также допускает имя в рамках этой системы. Следовательно, существует такое число Н, при котором Ah = R*. Далее, по определению множества R* число х принадлежит R* в том и только том случае, если число х*х принадлежит множеству R. Поэтому для любого а это х принадлежит Ah в том и только том случае, если число х*х входит в множество R. В частности, если к качестве x выбратьh, то число h будет принадлежать, Ah, в том и только том случае, если число h*h входит в R. Далее, h принадлежит Ah в том и только том случае, если утверждение h Є Ah, истинно. С другой стороны, поскольку число h*h есть гёделев номер утверждения h Є Ah, то h*h входит в R в том и только в том случае, если утверждение h Є Ah опровержимо. Значит, утверждение h Є Ah истинно в том и только в том случае, если оно опровержимо. Отсюда следует, что данное утверждение либо истинно и опровержимо, либо ложно и неопровержимо. Однако оно не может быть истинным и опровержимым, поскольку наша система правильна по условию задачи; следовательно, оно должно быть ложным и неопровержимым. Наконец, раз это утверждение ложно, оно не может быть и доказуемым (опять же потому, что система правильна). Таким образом, утверждение h Є Ah, недоказуемо и неопровержимо (и, кроме того, оно ложно).
б. Пусть нам дано, что множество а10 — это К и что А5n при любом числе n совпадает с множеством An*. Значит, A50 есть множество R*. Тогда, согласно решению «а», если принять h = 50, то утверждение 50 Є A50 будет недоказуемым и неопровержимым. Кроме того, это утверждение будет ложным.
Машины, рассказывающие о себе
Рассмотрим теперь доказательство Гёделя с несколько иной точки зрения, которая позволяет увидеть основную идею особенно ярко.
Возьмем четыре символа Р, N, А, — , и рассмотрим всевозможные комбинации этих символов. Произвольную комбинацию указанных символов мы будем называть выражением. Например, выражением является комбинация Р-NA-Р; точно так же выражением будет комбинация — PN-А-Р-. Некоторым выражениям мы будем приписывать определенный смысл — такие выражения в дальнейшем будут называться утверждениями.
Предположим, что у нас имеется машина, которая может выдавать нам (распечатывать) одни выражения и не может выдавать другие. При этом те выражения, которые машина может напечатать, мы будем называть Допускающими распечатку. Предполагается, что любое выражение, которое может напечатать машина, рано или поздно обязательно будет ею напечатано. Если нам задано выражение X и мы хотим высказать суждение, что X допускает распечатку, то будем записывать это как Р-X. Так, например, запись Р-ANN означает, что выражение ANN допускает распечатку (при этом неважно, является ли это утверждение истинным или ложным). Если же мы хотим сказать, что выражение X не допускает распечатки, то будем писать NP-X. (Символ N — от англ. not — отрицание «не», а символ Р — от англ. printable — допускающий распечатку.) Таким образом, запись вида NP-X следует читать как «не допускающее распечатки X», или, что по существу то же самое, «выражение X не допускает распечатки».
Ассоциатом выражения X мы будем называть выражение X–X; при этом вместо слова «ассоциат» нами будет использоваться символ А (от англ. associate). Таким образом, если нам задано некоторое выражение X и мы хотим сказать, что ассоциат выражения X допускает распечатку, то будем записывать это как РА-X. Если мы теперь хотим сказать, что ассоциат утверждения X не допускает распечатки, то это будет записываться как NPA-X.
Читателя, быть может, удивляет, что мы используем тире в качестве своеобразного символа. В самом деле, почему, когда нам нужно высказать суждение о том, что выражение X допускает распечатку, вместо записи Р-X не писать просто РХ? Это делается для того, чтобы избежать определенной двусмысленности. В самом деле, что, например, может означать запись PAN, если мы откажемся от тире? Она может означать либо что ассоциат выражения N допускает распечатку, либо что допускает распечатку выражение AN. Если же мы пользуемся тире, то подобной двусмысленности не возникает. Так, если мы хотим сказать, что ассоциат выражения N допускает распечатку, то записываем этот факт как РА-N; если же хотим сказать, что допускает распечатку выражение AN, то пишем Р-AN. Предположим теперь, нам нужно сказать, что выражение — X допускает распечатку. Правильно ли будет записать эту фразу как Р-Х? Нет, ведь запись Р-X означает, что выражение X допускает распечатку. Поэтому чтобы сказать, что допускает распечатку выражение — X, нужно написать Р-X.
Рассмотрим еще несколько примеров: запись Р- означает, что «-» допускает распечатку, запись РА- означает, что выражение (ассоциат выражения-) допускает распечатку; запись Р- также означает, что «-» допускает распечатку; запись NРА-Р-А означает, что ассоциат выражения — Р-А не допускает распечатки, или, другими словами, что не допускает распечатки выражение — Р-А-Р-А. То же самое означает и запись вида NP-Р-А-Р-А.
Утверждением будем называть любое выражение одного из следующих четырех типов: Р-X, NP-X, РА-X или NPA-X, где X — любое выражение. Утверждение Р-X мы будем называть истинным, если X допускает распечатку, и ложным, если X с допускает распечатки. Утверждение NP-X мы будем называть истинным, если X не допускает распечатки, и ложным, если X эту распечатку допускает, утверждение РА-X будет называться истинным, если ассоциат выражения X допускает распечатку, и ложным, если ассоциат этого X распечатки не допускает. Наконец, утверждение NA-X мы будем называть истинным, если ассоциат выражения X не допускает распечатки, и ложным, если ассоциат этого X распечатку допускает. Итак, мы дали точное определение истинности и ложности для утверждений всех четырех видов. Отсюда следует, что для любого выражения X справедливы:
Правило 1. Утверждение Р-X истинно тогда и только тогда, когда выражение X допускает распечатку (на машине).
Правило 2. Утверждение РА-X истинно тогда и только тогда, когда выражение X–X допускает распечатку.
Правило 3. Утверждение NP-X истинно тогда и только тогда, когда выражение X не допускает распечатки.
Правило 4. Утверждение NPA-X истинно тогда и только тогда, когда выражение X–X не допускает распечатки
Удивительное дело! Машина печатает утверждения, которые представляют собой не что иное, как суждения о том, что она сама может и что не может напечатать! В этом смысле машина говорит о себе (или точнее, печатает утверждения о самой себе).
Пусть теперь нам известно, что машина на 100 % точна, то есть она не может выдать нам ложное утверждение, печатая только истинные утверждения. Отсюда вытекает ряд следствий. Например, если машина в один прекрасный день напечатает утверждение Р-X, то, значит, она должна напечатать и выражение X, потому что раз она может напечатать утверждение Р-X, то, стало быть, это утверждение истинно, а это означает, что выражение X допускает распечатку. Значит, действительно, машина рано или поздно должна распечатать выражение X.
Аналогично, если машина выдаст нам утверждение РА-X, тогда (поскольку утверждение РА-X должно быть истинным) она должна напечатать нам также и выражение X–X.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52