Научная литература
booksshare.net -> Добавить материал -> Математика -> Манин Ю.И. -> "Доказуемое и недоказуемое " -> 20

Доказуемое и недоказуемое - Манин Ю.И.

Манин Ю.И. Доказуемое и недоказуемое — Советское радио , 1979. — 89 c.
Скачать (прямая ссылка): dokazuemoinedokazu1979.djvu
Предыдущая << 1 .. 14 15 16 17 18 19 < 20 > 21 22 23 24 25 26 .. 70 >> Следующая

Приведем теперь образцы спектральных аксиом.
Аксиомы равенства. Пусть Ь — язык класса 3?\, в алфавите которого есть отношение ранга два = . Мы будем писать t1 = /2 вместо = (У2) •
Если Р — формула, х — переменная, t — терм, мы будем обозначать через Р(х, ?) —результат подстановки / в Р вместо любой части свободных вхождений х в Р, не связывающих I.
4.6. Предложение.
а) Формулы
?= ?; гх = ^ ^ —11: гх = = tl — tx = г'з; х=4 -* (Р (х, х) —
— Р(х, 0)
ср-истинны для любой интерпретации Ь, в которой ф( = ) есть равенство.
б) Все формулы пункта а) выводимы из множества АхЬ у у{х — х\х переменная} у {х—у—*(Р{х, х)—Р(х, г/)), Р атомарные} Формулы этого списка, за исключением АхЬ, называются аксиомами равенства.
в) Пусть ф—любая интерпретация Ь во множестве М, для которой аксиомы равенства истинны. Тогда ф( = ) есть отношение эквивалентности в М, совместимое с интерпретациями всех отношений и операций Ь в М. Если обозначить через ф' очевидную интерпретацию Ь в фактор-множестве АГ=Л4/ф( = ), то <р'( = ) есть равенство, иТЬ, — Т^,Ь.
Набросок доказательства, а) ф-истинность устанавливается без труда. Ограничимся последней формулой. Пусть она ложна в точке Тогда |*=/|(|) = 1, |^((?) = 1, |Р(х,
46
^)|(!)=0. Первое утверждение означает, что х^—?. Но тогда |Р| (I) = \Р(Х> '01(1) ло предложению ,2.10, вопреки второму и третьему равенству.
б) Вывод Ь — Ь-.х—х (аксиома равенства); уд;(л; = л:) (Сеп); ух(х=х) —-I—/ (логическая „аксиома специализации“); /=/ (МР).
Вывод ^ =
1) х=у-+(х=х-+у=х) (аксиома равенства для = в качестве Р);
2) (3->((Р-^(<2-*-Р))-^(Р-^Р)), где Р есть х—у, 0. есть х—х, Я есть у=х (тавтология);
3) х=х (аксиома равенства);
4) (Р^(С^Р))^(Р+Р) (МР к (2) и (3));
5) х=у-+у=х (МР к (1) и (4)).
Дальше нужно дважды применить Сеп, аксиому специализации и МР, чтобы вывести из (5) формулу ^=/2—^2=^; замена 1Х на Ь и наоборот дает вывод <2=*1-^1=4; конъюнкция этих формул выводится по лемме 4.4; наконец, тавтология (??1=/2-»-*2= = 1]) Д {Ь2='11-^)41 = = —^2=/Д вместе с МР дает тре-
буемое.
Вывод третьей и четвертой формул п.4.6а мы оставляем читателю. Существование вывода четвертой формулы доказывается индукцией по числу связок и кванторов в Р; Р представляется з виде |<3, 1или у.х(2, дх(2; предполагается, что для С, С},, С}2 вместо Р вывод уже построен; он достраивается для Р (см. Мендельсон (2, с. 87 —88]).
г) Из ф-истинности аксиом равенства следует ф-истинность формул п. 4.6а, так как они выводимы. Первые три формулы п. 4.6 в применении к трем разным переменным х, у, г показывают тогда, что отношение ф( = ) на М рефлексивно, симметрично и транзитивно.
Действительно, пусть X, У, Ъ — три любые элемента М, ? (Е — такая точка, что х" = X, у^ — У, — 2, ^ — отношение
ф(=) на М.ш-истияность формул п.4.6а означает, что X Х\
х^у^^у^х; х^у и у^г^х^г.
Совместимость ~ с ф-интерпретацией всех отношений и операций на М по определению означает следующее.
Пусть р — отношение, ф(Р)=Л4г—его интерпретация. Если {Х\, . . ., Хг) ^ф (р) И Х'г~Х{, ТО (Дь .. ., Х'г, . . ., Хг) еф (/7).
Пусть / — операция, фД) : Мг-+М — ее интерпретация. Еслн Ф(/) (Хь .. „ Хг) =У и Х'^Хи то хрф (Хи Х'и ..., ХГ)~У' ~У.
Проверка совместимости использует ф-ИСТИННОСТЬ последней формулы п. 4.6а в подходящей точке ?еМ, если взять в качестве Р формулы р(хи ..., хг) и {(хи ..., хг) —у соответственно, в ка-
47
честве 2 переменную х'г, В качестве л: переменную Хг И ПОЛОЖИТЬ х^Х» х^ = Х,1, у1 = У.
Из совместимости следует, что можно построить интерпретацию ф' языка Ь в М'—М!~, для которой ф'(р) =ф(р)тос1 ~, ф'(/)=, = ф(/)тос1 ~, ф( = )—равенство. Из последней формулы п. 4.6а будет тогда вытекать, что все ф-истинные формулы останутся ф'-истинными, и наоборот.
В дальнейшем, говоря о специальных аксиомах любого языка 2?\ с символом —, мы будем молчаливо включать в их число аксиомы равенства для =. Модели, в которых они интерпретируются как равенство, мы будем называть нормальными.
Специальные аксиомы арифметики
4.7. Предложение.
Следующие формулы истинны в стандартной интерпретации языка ЦАг и называются специальными аксиомами ЬДг:
а) аксиомы равенства-,
б) аксиомы сложения:
х+0=х; ху=ух; (х + г/) + г=д: + (р + г); х-\-г = у-\-г— х = у\
в) аксиомы умножения:
х? 0 = 0; х-Т=х-, х-у — у-х-, (х-у)-г — х-(у-г).
г) аксиома дистрибутивности: х-{у-\-г)=х-у~\-х-г-,
д) аксиомы индукции:
Р (0) Д ух (Р (х) —? Р (х -ф- 1)) —<• ухР (х), где Р — любая формула языка.
Доказательство тривиально, и мы оставляем его читателю. Отметим лишь, что «доказательство» истинности аксиом индукции само использует индукцию как метаязыковое рассуждение.
Комментарии, а) В п. 4.7,6—г мы записали обычные аксиомы коммутативного полукольца для сокращения формальных выводов: любое неформальное вычисление, использующее только эти аксиомы, может быть без труда превращено в формальный вывод его результата в Ь\Ат.
Э. Мендельсон [2 гл. 3] приводит более слабую систему аксиом и затем показывает, как из нее выводятся наши формулы. Это занимает 5—6 страниц текста и является в основном данью исторической традиции, восходящей к Пеано.
Предыдущая << 1 .. 14 15 16 17 18 19 < 20 > 21 22 23 24 25 26 .. 70 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed