Рэймонд Смаллиан
Принцесса или тигр?
Стр. 119
Итак, все героические попытки Фергюссона не увенчались успехом, однако причина этого заключалась отнюдь не в недостатке авторской изобретательности. Мы не должны забывать о том, что он жил за несколько десятилетий до знаменитых открытий таких известных логиков, как Гёдель, Тарский, Клини, Тьюринг, Пост, Черч и другие ученые, о работах которых у нас вот-вот пойдет речь. Если бы Фергюссон дожил до этих открытий, то он понял бы, что неудачи его обусловлены исключительно тем, что он пытался создать нечто по сути своей совершенно невозможное! Поэтому, отдав должное Фергюссону и его коллегам Крейгу и Мак-Каллоху, распрощаемся с ними и перенесемся на три-четыре десятилетия вперед, в переломный 1931 год.
Решения
1. Одно из решений состоит в следующем: утверждение 75ЄА75 является истинным, но не может быть доказано машиной. И вот почему.
Допустим, что утверждение 75ЄА75 ложно. Тогда число 75 не принадлежит множеству А75- Следовательно, это число должно принадлежать множеству А25 (согласно свойству 2, множество Аn является дополнением множества ais)- Это означает (согласно свойству 3), что число 75*75 принадлежит множеству А8, поскольку 25=3X8-1-1, и, следовательно, машина может напечатать число 75*75. Иначе говоря, это означает, что утверждение 75еЛ?5 может быть доказано машиной. Таким образом, если бы утверждение 75ЄA?5 было ложным, то оно вполне могло бы быть доказано машиной. Однако нам известно по условию, что машина точна и никогда не доказывает ложные утверждения. Поэтому утверждение 75ЄA75 не может оказаться ложным, и, стало быть, оно должно быть истинным.
Далее, поскольку утверждение 75ЄА75 истинно, то число 75 действительно принадлежит множеству Аn. Поэтому оно не может принадлежать множеству А 25 (согласно свойству 2), и, следовательно, число 75 * 75 в свою очередь не может принадлежать множеству А8, поскольку если бы это было так, то тогда, согласно свойству 3, число 75 принадлежало бы множеству а25. Поскольку ясно, что число 75 * 75 не принадлежит множеству Ag, то утверждение 756А75 не может быть доказано машиной. Итак, утверждение 75ЄA75 является истинным, но оно недоказуемо с помощью машины.
2. Прежде чем рассматривать другие решения, установим следующий факт весьма общего свойства. Пусть для всего дальнейшего ключевым является множество К—это множество всех чисел х, для которых утверждение хЄАx недоказуемо машиной, или, что то же самое, множество таких чисел х, для которых число х*х не может быть напечатано машиной. Далее, множество А 75 как раз и есть такое множество К, потому что утверждение, что х принадлежит множеству Аn, равносильно утверждению, что х не принадлежит множеству A25, что в свою очередь равносильно утверждению, что число х*х не принадлежит множеству А8, где А8—это множество тех чисел, которые машина может напечатать. Итак, А 75=К. Но при этом и Аn=К, потому что утверждение, что некое число х принадлежит множеству An, равносильно утверждению, что число х*х принадлежит множеству А8 (согласно свойству 3, поскольку 73 = 3x24+1), что в свою очередь равносильно утверждению, что число х+х не принадлежит множеству А8 (согласно свойству 2). Таким образом, А7з— это множество всех тех чисел х, для которых число х*х не принадлежит множеству А8 или, что то же самое, множество всех чисел х, для которых утверждение хЄАx не может быть доказано машиной.
| 001 002 003 004 005 006 007 008 009 010 011 012 013 |
| 014 015 016 017 018 019 020 021 022 023 024 025 026 |
| 027 028 029 030 031 032 033 034 035 036 037 038 039 |
| 040 041 042 043 044 045 046 047 048 049 050 051 052 |
| 053 054 055 056 057 058 059 060 061 062 063 064 065 |
| 066 067 068 069 070 071 072 073 074 075 076 077 078 |
| 079 080 081 082 083 084 085 086 087 088 089 090 091 |
| 092 093 094 095 096 097 098 099 100 101 102 103 104 |
| 105 106 107 108 109 110 111 112 113 114 115 116 117 |
| 118 119 120 121 122 123 124 125 126 127 128 129 130 |
| 131 132 133 134 135 136 137 138 139 140 141 142 143 |