Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
Рг: у« (и& *—* 4° (о©*—о€г0)).
т. е. «2 есть множество всех подмножеств ?/».
Далее,
((ы&Лу°1 *—*? РР ®РгУ)-
Это значит (с учетом Р3, определившей г): «если и — любое подмножество у, т. е. множество открытых подмножеств х, то объединение гю всех этих подмножеств ппинадлежит у, т. е. открыто». Окончательная формула может выглядеть так:
Следующие наблюдения над ней будут отражены в точных определениях в § 1 и 2 гл. II.
Буквы х, у во всех Р{ используются в одном и том же значении, тогда как г играет разные роли: в Р1 это подмножество х, а в Рз и Рь — множество подмножеств х. Мы можем позволить себе это потому, что как только мы «связали» г квантором у, скажем, в Ри г перестала обозначать индивидуальное, хотя и неопределенное множество, а стала временным обозначением «любого множества». Коль скоро «область действия» квантора у кончилась, г можно использовать в новом значении. Чтобы «освободить» г для дальнейшего употребления, у 2 поставлен и перед Рг+Р,
Переводы арго — Ц Аг
3.12.АУ<г/“ :дг(г/==(х-|--г:)-}-1). Учесть, что переменные суть имена (неопределенных) неотрицательных целых чисел.
3.13. “х— делитель ул: дг (у—х-г).
3.14. “х — простое]|число“: „I <хвЛ(“у— делитель хи—>(у — = Т\/у = Х)).
3.15. “Большая теорема Ферма“:
умух-у-^у" (“ 2 < и “ Д “х“, + хи2 == х“3 “-* “х,хгх3 = 0“).
Неясно, как написать в ЦАг формулу хи\-\-хи%=хиг. Конечно, для каждого конкретного и=1, 2, 3, ..., в ЦАг есть соответствующая атомарная формула, но как сделать и переменной? Это не тривиальная задача. Только недавно было доказано, что можно найти такую атомарную формулу р(х, и, у, ги ..., гп), что утверждение дг, ... дгл р(х, ..., гп) в области натуральных чисел равносильно у~хи. После этого хц1+хи2=х“3 можно будет перевести хоть так:
“Xй!=у,-“ Л1“х"2=у2? Д “хн3 = у3“ Д ух + уг = у%.
2*
19
Существование такой р — нетривиальный теоретико-числовой факт, так что здесь сама возможность перевода становится математической задачей.
3.16. «Гипотеза Римана». Для понимания этого примера необходимо некоторое знакомство с аналитической теорией чисел.
Дзета-функция Римана % (з) определена в полуплоскости Ие 5 > 1 рядом
2 п~3. Она мероморфно продолжается на всю комплексную плоскость значе-
П= 1
ний в. Гипотеза Римана состоит в утверждении, что нетривиальные нули ? (я) лежат на прямой ї}е5=1/2. В таком виде, конечно, гипотеза Римана не переводится на язык ЦАг. Однако известен ряд чисто арифметических утверждений, доказуемо эквивалентных гипотезе Римана. Простейшее из них, возможно, формулируется так.
Пусть р(я)—функция Мебиуса на целых числах ^1: она равна 0, если п делится на квадрат, и (—1)% где т — число простых делителей п, в противном случае.
Тогда имеем
Гипотеза Римана ф:=?> Vs > ОдУ > х'
2 Ия) <у1/2+* )•
I «=1 I
Справа не цел лишь показатель степени, но е можно заставить пробегать лишь числа вида 1/г, г^\, г — целое, и затем возвести требуемое неравенство в степень 2г. Формулу
<^+г
уже можно перевести на язык ПАг, хотя и не совсем тривиально.
Два последних примера мы привели для того, чтобы показать, насколько сложными могут быть задачи, формулируемые на языке ЦАг, несмотря на кажущуюся простоту его выразительных средств и семантики.
В заключение этого параграфа сделаем несколько замечаний о языках высших порядков.
3.17. Языки высших порядков. Пусть 11— любой язык первого порядка. Его выразительные средства принципиально ограничены в одном важном отношении: нет возможности говорить о произвольных свойствах объектов теории, т. е. о произвольных подмножествах множества всех объектов. Синтаксически это отражается в запрете формулировать выражения, скажем, вида ур(р(х)), где р — отношение ранга 1. Отношения обозначают фиксированные, а не переменные свойства.
Правда, некоторые свойства выразимы с помощью неатомарных формул. Скажем, в 1ЛАг вместо «х четно» можно написать дг/(х= (1 +1) -у). Однако имеется континуум подмножеств целых чисел, но всего счетное множество выразимых свойств (§ 2 гл. II),
?так что заведомо не все свойства выразимы формулами. Стало ?•быть, запрещенное выражение у р{р(х)) полностью нельзя заменить никакой последовательностью выражений Pi(x), Pi{x), Рз(х), ...
Языки, в которых допускаются кванторы по свойствам и (или) но функциям (а также, возможно, по свойствам свойств и т. д.), называются языками высших порядков. Один такой язык L2Real -мы рассмотрим в гл. III для иллюстрации метода форсинга Коэна н упрощенном варианте.
Тем не менее такого же расширения выразительных возможностей можно достичь, оставаясь в классе языков 3?\. Действительно, в языке Ц Set можно говорить о любых подмножествах любых множеств, т. е. о свойствах, и свойствах свойств и свойствах систем свойств ... (с трансфинитным продолжением), не выходя за пределы формализма первого порядка. Кроме того, любой конкретный ориентированный язык высшего порядка, предназначенный для описания структурированных множеств, можно перевести на язык L't Set, сохранив смысл и истинность в стандартной интерпретации. (Видимым исключением были бы языки для описания классов Геделя—Бернайса и «больших» категорий, но они, кажется, осуждены оставаться языками первого порядка при нынешнем уровне понимания парадоксов.)
