Научная литература
booksshare.net -> Добавить материал -> Математика -> Смаллиан Р.М. -> "Принцесса или тигр " -> 57

Принцесса или тигр - Смаллиан Р.М.

Смаллиан Р.М. Принцесса или тигр — Мир , 1985. — 224 c.
Скачать (прямая ссылка): ladyorthetiger1985.pdf
Предыдущая << 1 .. 51 52 53 54 55 56 < 57 > 58 59 60 61 62 63 .. 73 >> Следующая

может: например, для любого п, которое равно произведению 75 на некоторое кратное числа 9 или произведению 73 на произвольное кратное числа 9, утверждение п?.Ап является истинным, но недоказуемым посредством этой машины,
1 < Доказуемость
X и истина
Крупной вехой в истории математической логики стал 1931 г. Именно в этом году Гёдель опубликовал знаменитую теорему о неполноте. Свою эпохальную работу * он начинает следующими словами:
«Развитие математики в направлении все большей точности привело к формализации целых ее областей, в связи с чем стало возможно проводить доказательства, пользуясь небольшим числом чисто механических правил. В настоящий момент наиболее исчерпывающими системами являются, с одной стороны, система аксиом, предложенная Уайтхедом и Расселом в работе «Рппс/рш МаШетайса», а с другой—система Цермело — Френкеля в аксиоматической теории множеств. Обе эти системы настолько обширны, что в них оказывается возможным формализовать все методы доказательства, используемые сегодня в математике,— иначе говоря, все эти методы могут быть сведены к нескольким аксиомам и правилам вывода. Поэтому, казалось бы, разумно предположить, что указанных аксиом и правил вполне хватит для разрешения всех математических проблем, которые могут быть сформулированы в пределах данной системы. Ниже будет показано, что дело обстоит не так. В обеих упомянутых системах имеются сравнительно простые задачи
* «?ber formal unentscheidbare S?tze der «Principia Mathematica» und verwandter Systeme I» («О формально неразрешимых предложениях «Принципов математики» и других родственных систем»), Monatshefte f?r Mathematik und Physik, 38, 173—198.
175
из теории обычных целых чисел, которые не могут быть решены на базе этих аксиом»*.
Далее Гёдель объясняет, что такая ситуация обусловлена отнюдь не какими-то специфическими особенностями двух упомянутых систем, но имеет место для обширного класса математических систем.
Что имеется в виду под «обширным классом» математических систем? Это выражение интерпретировалось по-разному, и соответственно по-разному обобщалась теорема Гёделя. Как ни странно, одно из самых простых и доступных для неспециалиста объяснений остается наименее известным. Это тем более удивительно, что на такое объяснение указывал и сам Гёдель во вводной части своей первой работы. К нему мы сейчас и обратимся.
Рассмотрим систему аксиом со следующими свойствами. Прежде всего пусть у нас имеются имена для различных множеств положительных целых чисел, причем все эти «именуемые», или допускающие наименование, множества мы можем расположить в виде бесконечной последовательности А\, Аъ, ... , Ап, ... (точно так же, как в системе Фергюссона, рассмотренной в предыдущей главе). Назовем число п индексом именуемого множества А, если А=А„. (Таким образом, если, например, множества Л2, А1 и Ап совпадают между собой, то тогда числа 2, 7 и 13—это все индексы одного и того же множества.) Как и для системы Фергюссона, с каждым числом х и с каждым числом у мы связываем утверждение, записываемое в виде хЕ Ау, которое называется истинным, если х принадлежит Ау, и ложным, если х не принадлежит Ау. Однако в дальнейшем мы не предполагаем, что утверждения типа хЕАу являются единственно возможными утверждениями в данной системе, поскольку могут существовать и другие. Предполагается также, что любое возможное утверждение обязательно классифицируется либо как истинное, либо как ложное.
Каждому утверждению в данной системе присваивается некий кодовый номер, который мы будем называть
* Выборочный перевод автора.
гёделевым номером, причем гёделев номер утверждения хЕАу будем обозначать х*у, (Теперь уже нет нужды предполагать, что число х*у состоит из цепочки единиц длиной х, за которой следует цепочка нулей длиной у; сам Гёдель фактически использовал совсем другую кодовую нумерацию. Можно пользоваться самыми разными видами кодовой нумерации, и какой вид оказывается более удобным—это зависит от конкретного вида рассматриваемой нами системы. Так или иначе, для доказательства той общей теоремы, которую мы скоро докажем, нет необходимости вводить какую-то конкретную гёделеву нумерацию.)
Определенные утверждения в данной системе принимаются как аксиомы; кроме того, вводятся также некие специальные правила, по которым можно на основании этих аксиом доказывать различные другие утверждения. Таким образом, в данной системе имеется вполне определенное свойство утверждения, называемое его доказуемостью. Далее предполагается, что система правильна в том смысле, что каждое доказуемое в этой системе утверждение является истинным; отсюда, в частности, следует, что если утверждение хЕАу доказуемо в данной системе, то число х действительно является элементом множества А у.
Пусть Р—это набор гёделевых номеров всех доказуемых в данной системе утверждений. Пусть опять же для любого множества чисел А его дополнение обозначается символом А (это множество всех чисел, не принадлежащих А). Наконец, через А* мы будем обозначать множество всех чисел х, для которых число х*х принадлежит А. При этом нас будут интересовать системы, для которых выполняются следующие три условия бь О2 и Оз:
Предыдущая << 1 .. 51 52 53 54 55 56 < 57 > 58 59 60 61 62 63 .. 73 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed