Итак, утверждение 75ЄA75 является истинным, но оно недоказуемо с помощью машины.
2. Прежде чем рассматривать другие решения, установим следующий факт весьма общего свойства. Пусть для всего дальнейшего ключевым является множество К — это множество всех чисел х, для которых утверждение х Є Аx недоказуемо машиной, или, что то же самое, множество таких чисел х, для которых число х*х не может быть напечатано машиной. Далее, множество А75 как раз и есть такое множество К, потому что утверждение, что х принадлежит множеству Аn, равносильно утверждению, что х не принадлежит множеству A25, что в свою очередь равносильно утверждению, что число х*х не принадлежит множеству А8, где А8 — это множество тех чисел, которые машина может напечатать. Итак, А75 = К. Но при этом и Аn = К, потому что утверждение, что некое число х принадлежит множеству An, равносильно утверждению, что число х*х принадлежит множеству А8 (согласно свойству 3, поскольку 73 = 3x24+1), что в свою очередь равносильно утверждению, что число х+х не принадлежит множеству А8 (согласно свойству 2). Таким образом, А75 — это множество всех тех чисел х, для которых число х*х не принадлежит множеству А8 или, что то же самое, множество всех чисел х, для которых утверждение х Є Аx не может быть доказано машиной. Следовательно, А73 — это то же самое множество чисел, что и A75 поскольку оба они тождественны множеству К. Более того, для любого заданного числа n, для которого Аn = К, утверждение n Є А* должно быть истинным, но недоказуемым с помощью машины. Это можно показать буквально с помощью тех же самых рассуждений, что и в рассмотренном нами частном случае n = 75 (в еще более общей форме эти рассуждения приведены в следующей главе). Тем самым мы получаем, что утверждение 73 Є А73 — это еще один пример истинного утверждения, кодовый номер которого машина напечатать не может.
3. Для любого числа n множество А9n должно совпадать с множеством n. В самом деле, множество А9n есть дополнение множества A3n, а множество А3n в свою очередь есть дополнение множества n; следовательно, множество А9n совпадает с Аn, Это означает, что множество A675 совпадает с множеством A75, и, стало быть, утверждение 675 Є А675 — это есть еще одно решение задачи. Аналогично утверждение 2175 Є A2175также является решением. Таким образом, мы получаем, что существует бесконечно много истинных утверждений, которые машина Фергюссона доказать не может: например, для любого n, которое равно произведению 75 на некоторое кратное числа 9 или произведению 73 на произвольное кратное числа 9, утверждение n Є А, является истинным, но недоказуемым посредством этой машины.
Доказуемость и истина
Крупной вехой в истории математической логики стал 1931 г. Именно в этом году Гёдель опубликовал знаменитую теорему о неполноте. Свою эпохальную работу он начинает следующими словами:
«Развитие математики в направлении все большей точности привело к формализации целых ее областей, в связи с чем стало возможно проводить доказательства, пользуясь небольшим числом чисто механических правил. В настоящий момент наиболее исчерпывающими системами являются, с одной стороны, система аксиом, предложенная Уайтхедом и Расселом в работе «Princlpia Mathematica», а с другой — система Цермело—Френкеля в аксиоматической теории множеств. Обе эти системы настолько обширны, что в них оказывается возможным формализовать все методы доказательства, используемые сегодня в математике, — иначе говоря, все эти методы могут быть сведены к нескольким аксиомам и правилам вывода. Поэтому, казалось бы, разумно предположить, что указанных аксиом и правил вполне хватит для разрешения всех математических проблем, которые могут быть сформулированы в пределах данной системы. Ниже будет показано, что дело обстоит не так. В обеих упомянутых системах имеются сравнительно простые задачи из теории обычных целых чисел, которые не могут быть решены на базе этих аксиом».
Далее Гёдель объясняет, что такая ситуация обусловлена отнюдь не какими-то специфическими особенностями двух упомянутых систем, но имеет место для обширного класса математических систем.
Что имеется в виду под «обширным классом» математических систем? Это выражение интерпретировалось по-разному, и соответственно по-разному обобщалась теорема Гёделя. Как ни странно, одно из самых простых и доступных для неспециалиста объяснений остается наименее известным. Это тем более удивительно, что на такое объяснение указывал и сам Гёдель во вводной части своей первой работы. К нему мы сейчас и обратимся.
Рассмотрим систему аксиом со следующими свойствами. Прежде всего пусть у нас имеются имена для различных множеств положительных целых чисел, причем все эти «именуемые», или допускающие наименование, множества мы можем расположить в виде бесконечной последовательности А1, А2…, An… (точно так же, как в системе Фергюссона, рассмотренной в предыдущей главе). Назовем число n индексом именуемого множества А, если А=n. (Таким образом, если, например, множества А2, А7 и A13 совпадают между собой, то тогда числа 2, 7 и 13 — это все индексы одного и того же множества.) Как и для системы Фергюссона, с каждым числом х и с каждым числом у мы связываем утверждение, записываемое в виде х Є Ау, которое называется истинным, если х принадлежит А у, и ложным, если х не принадлежит Ау. Однако в дальнейшем мы не предполагаем, что утверждения типа х Є Ау являются единственно возможными утверждениями в данной системе, поскольку могут существовать и другие. Предполагается также, что любое возможное утверждение обязательно классифицируется либо как истинное, либо как ложное.
Каждому утверждению в данной системе присваивается некий кодовый номер, который мы будем называть геделевым номером, причем гёделев номер утверждения x Є АУ будем обозначать х*у. (Теперь уже нет нужды предполагать, что число х*у состоит из цепочки единиц миной х, за которой следует цепочка нулей длиной у; cам Гёдель фактически использовал совсем другую кодовую нумерацию. Можно пользоваться самыми разными видами кодовой нумерации, и какой вид оказывался более удобным — это зависит от конкретного вида рассматриваемой нами системы. Так или иначе, для доказательства той общей теоремы, которую мы скоро докажем, нет необходимости вводить какую-то конкретную гёделеву нумерацию.)
Определенные утверждения в данной системе принимаются как аксиомы; кроме того, вводятся также некие специальные правила, по которым можно на основании этих аксиом доказывать различные другие утверждения. Таким образом, в данной системе имеется иполне определенное свойство утверждения, называемое его доказуемостью.
Далее предполагается, что система правильна в том смысле, что каждое доказуемое в этой системе утверждение является истинным;
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 53 54 55 56
2. Прежде чем рассматривать другие решения, установим следующий факт весьма общего свойства. Пусть для всего дальнейшего ключевым является множество К — это множество всех чисел х, для которых утверждение х Є Аx недоказуемо машиной, или, что то же самое, множество таких чисел х, для которых число х*х не может быть напечатано машиной. Далее, множество А75 как раз и есть такое множество К, потому что утверждение, что х принадлежит множеству Аn, равносильно утверждению, что х не принадлежит множеству A25, что в свою очередь равносильно утверждению, что число х*х не принадлежит множеству А8, где А8 — это множество тех чисел, которые машина может напечатать. Итак, А75 = К. Но при этом и Аn = К, потому что утверждение, что некое число х принадлежит множеству An, равносильно утверждению, что число х*х принадлежит множеству А8 (согласно свойству 3, поскольку 73 = 3x24+1), что в свою очередь равносильно утверждению, что число х+х не принадлежит множеству А8 (согласно свойству 2). Таким образом, А75 — это множество всех тех чисел х, для которых число х*х не принадлежит множеству А8 или, что то же самое, множество всех чисел х, для которых утверждение х Є Аx не может быть доказано машиной. Следовательно, А73 — это то же самое множество чисел, что и A75 поскольку оба они тождественны множеству К. Более того, для любого заданного числа n, для которого Аn = К, утверждение n Є А* должно быть истинным, но недоказуемым с помощью машины. Это можно показать буквально с помощью тех же самых рассуждений, что и в рассмотренном нами частном случае n = 75 (в еще более общей форме эти рассуждения приведены в следующей главе). Тем самым мы получаем, что утверждение 73 Є А73 — это еще один пример истинного утверждения, кодовый номер которого машина напечатать не может.
3. Для любого числа n множество А9n должно совпадать с множеством n. В самом деле, множество А9n есть дополнение множества A3n, а множество А3n в свою очередь есть дополнение множества n; следовательно, множество А9n совпадает с Аn, Это означает, что множество A675 совпадает с множеством A75, и, стало быть, утверждение 675 Є А675 — это есть еще одно решение задачи. Аналогично утверждение 2175 Є A2175также является решением. Таким образом, мы получаем, что существует бесконечно много истинных утверждений, которые машина Фергюссона доказать не может: например, для любого n, которое равно произведению 75 на некоторое кратное числа 9 или произведению 73 на произвольное кратное числа 9, утверждение n Є А, является истинным, но недоказуемым посредством этой машины.
Доказуемость и истина
Крупной вехой в истории математической логики стал 1931 г. Именно в этом году Гёдель опубликовал знаменитую теорему о неполноте. Свою эпохальную работу он начинает следующими словами:
«Развитие математики в направлении все большей точности привело к формализации целых ее областей, в связи с чем стало возможно проводить доказательства, пользуясь небольшим числом чисто механических правил. В настоящий момент наиболее исчерпывающими системами являются, с одной стороны, система аксиом, предложенная Уайтхедом и Расселом в работе «Princlpia Mathematica», а с другой — система Цермело—Френкеля в аксиоматической теории множеств. Обе эти системы настолько обширны, что в них оказывается возможным формализовать все методы доказательства, используемые сегодня в математике, — иначе говоря, все эти методы могут быть сведены к нескольким аксиомам и правилам вывода. Поэтому, казалось бы, разумно предположить, что указанных аксиом и правил вполне хватит для разрешения всех математических проблем, которые могут быть сформулированы в пределах данной системы. Ниже будет показано, что дело обстоит не так. В обеих упомянутых системах имеются сравнительно простые задачи из теории обычных целых чисел, которые не могут быть решены на базе этих аксиом».
Далее Гёдель объясняет, что такая ситуация обусловлена отнюдь не какими-то специфическими особенностями двух упомянутых систем, но имеет место для обширного класса математических систем.
Что имеется в виду под «обширным классом» математических систем? Это выражение интерпретировалось по-разному, и соответственно по-разному обобщалась теорема Гёделя. Как ни странно, одно из самых простых и доступных для неспециалиста объяснений остается наименее известным. Это тем более удивительно, что на такое объяснение указывал и сам Гёдель во вводной части своей первой работы. К нему мы сейчас и обратимся.
Рассмотрим систему аксиом со следующими свойствами. Прежде всего пусть у нас имеются имена для различных множеств положительных целых чисел, причем все эти «именуемые», или допускающие наименование, множества мы можем расположить в виде бесконечной последовательности А1, А2…, An… (точно так же, как в системе Фергюссона, рассмотренной в предыдущей главе). Назовем число n индексом именуемого множества А, если А=n. (Таким образом, если, например, множества А2, А7 и A13 совпадают между собой, то тогда числа 2, 7 и 13 — это все индексы одного и того же множества.) Как и для системы Фергюссона, с каждым числом х и с каждым числом у мы связываем утверждение, записываемое в виде х Є Ау, которое называется истинным, если х принадлежит А у, и ложным, если х не принадлежит Ау. Однако в дальнейшем мы не предполагаем, что утверждения типа х Є Ау являются единственно возможными утверждениями в данной системе, поскольку могут существовать и другие. Предполагается также, что любое возможное утверждение обязательно классифицируется либо как истинное, либо как ложное.
Каждому утверждению в данной системе присваивается некий кодовый номер, который мы будем называть геделевым номером, причем гёделев номер утверждения x Є АУ будем обозначать х*у. (Теперь уже нет нужды предполагать, что число х*у состоит из цепочки единиц миной х, за которой следует цепочка нулей длиной у; cам Гёдель фактически использовал совсем другую кодовую нумерацию. Можно пользоваться самыми разными видами кодовой нумерации, и какой вид оказывался более удобным — это зависит от конкретного вида рассматриваемой нами системы. Так или иначе, для доказательства той общей теоремы, которую мы скоро докажем, нет необходимости вводить какую-то конкретную гёделеву нумерацию.)
Определенные утверждения в данной системе принимаются как аксиомы; кроме того, вводятся также некие специальные правила, по которым можно на основании этих аксиом доказывать различные другие утверждения. Таким образом, в данной системе имеется иполне определенное свойство утверждения, называемое его доказуемостью.
Далее предполагается, что система правильна в том смысле, что каждое доказуемое в этой системе утверждение является истинным;
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 53 54 55 56