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

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

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

2.6. пример: стандартная интерпретация LiAr. Это — интерпретация во множестве N целых неотрицательных чисел, при которой О, 1 интерпретируются как 0, 1 соответственно; +, •, = как сложение, умножение и равенство соответственно.
2.7. Пример: стандартная интерпретация LiSet. Это — интерпретация в универсуме фон Неймана V (см. приложение), при которой 0 интерпретируется как пустое множество, е как отношение •«быть элементом», = как равенство.
Все примеры перевода в гл. I относились к этим стандартным •интерпретациям. Связь образцов перевода с нынешними определениями такова. Пусть П (лс, у, г) высказывание на арго о неопределенных множествах х, у, z из V; Р(х, у, г) —перевод П на язык L'i Set. Тогда для любой точки интерпретирующей х, у, z как имена множеств у%, г* из универсума фон Неймана, имеем
П {х1, у1, zl) истинно ф=:ф|Р(х, у, г)! (9=1.
Таким образом, каждая формула выражает некоторое свойство объектов интерпретационного множества:
2.8. Определение.
Множество SsAfr, r^l, называется ф-выразимым (формулой Р <в языке L' относительно интерпретации ф), если существуют такие переменные Хи . . ., Хг, что
|Р|,(9=1ф==ф(*;...........^)gs.
Проникновение в структуру множеств:
Ф-истинных формул в языке L;
<р-'выразимых множеств в \JMr
rsjl
принадлежит к числу важнейших задач о формальных языках.
2.9. Пример. Выразимые посредством L;Ar множества относи тельно стандартной интерпретации — это наименьший класс мяо жеств в U Nr, который
/Сз1
а) содержит все множества вида {(ku ..., kr)\F(kh ..., kr)=0}<=Nr,
где F пробегает многочлены с целыми коэффициентами;
б) замкнут относительно конечных пересечений, объединени и дополнений (в своем Nr); ___
в) замкнут относительно проекций ргг-: Nr-^Nr~l (додразуме вается, что число переменных языка бесконечно):
i !»•••» kr') = (k1,.., ki + 1t , k^j.
32
В самом деле, множества типа а) выражаются атомарными формулами №х=Лр2, где —терм, отвечающий сумме всех одночленов Я с положительными коэффициентами, а Н2— с отрицательными.
Далее, если 51? 5гСЛГг выразимы формулами Я„ Рг с одинаковыми свободными переменными, то 5^52 выразимо Я,ДЯ2, 5^5, выразимо Я, V Р2* Л^7>5, — формулой. ~| Я,- Наконец, множество ^гг (5,) выразимо формулой дхг (Я,).
Связки —, <—»? и квантор у не дают ничего нового, ибо, не меняя выражаемого множества, их можно заменить комбинацией уже рассмотренных логических операций: ух на "| дх Д и т. п.
Это — лишь первоначальное описание арифметических, т. е. цАг-выразимых множеств. Из него непосредственно нельзя усмотреть выразимости многих конкретных множеств например множества простых чисел в N (см. пример 3.14 гл. I), множества неполных частных при разложении У2 в непрерывную дробь или множества пар {(г, г-я цифра в десятичном разложении я)} с; А2.
Однако, как мы покажем в § 11, «номера истинных формул арифметики» образуют еще гораздо более сложное множество, и оно невыразимо.
Приведем теперь несколько простых технических результатов.
2.10. Предложение.
Пусть Я—формула в языке Ь, <р— его интерпретация в М, 5, М. Предположим, что для всех переменных х, имеющих свободные вхождения в Я, х*, совпадает с х*\ Тогда |Я| (Е) =
=!ри^)-
2.11. Следствие.
Замкнутые формулы Я в любой интерпретации определены в отношении истинности: | Я | (?) не зависит от ?.
Доказательство, а) Пусть ? — некоторый терм и пусть для любой переменной х, входящей в t, имеем х' = х^' • Тогда лемма 1.4 и индукция по длине 1 дают Я = ^ •
б) Утверждение 2.10 верно для атомарных формул Р вида р(к, ..., (г) ? В самом деле,
|Р|(^)=/1, если .......
(О, в противном случае
и аналогично для |Р|(|')- Но если | и совпадают на всех переменных, входящих (обязательно свободно) в Р, то тем более они совпадают на всех переменных, входящих в ({, и по условию а) имеем ^ = Д, 1=1, ..., г. Значит, 1^1(5) = |Д|(Г).
3-1 33
в) Проведем теперь индукцию по общему числу связок и кванторов в Р. Если Р имеет вид "1(2 или то вывод 2.10 для Р из 2.10 для С}, <3,, <За.
Пусть теперь Р имеет вид ух ((?) и 2.10 верно для (2 (случай дх (С2) разбирается аналогично или сводится к ух заменой дх на Пух--))-
Имеем по определению
Разрешим в правых частях этих равенств изменять т| и туг также по всем переменным, не входящим свободно в Q. Утверждения после слова «если» останутся i истинными или ложными в этой более широкой области значений, если они были истинны или ложны раньше по индуктивному предположению для Q. Но тогда т) и т)' будут пробегать одинаковые области значений, потому что с, н с,'. отличаются как раз по переменным, не входящим свободно в Q, и еще по х.
Предложение доказано.
Следующий почти очевидный факт лежит в основе многих явлений, свидетельствующих о неадекватности формальных языков интуитивным представлениям (ср. ниже «Парадокс Сколема»):
2.12. Предложение.
Мощность. Мощность класса <р-выразимых множеств не превышает
x0-f- card ({константы} (J {операции} U {отношения} L)
(card обозначает мощность).
Доказательство. Если в языке < переменных, то в нем не более к, card ({константы} U {операции} (J {отношения}) формул. Если же множество переменных несчетно, то каждое выразимое множество может быть (выражено формулой, переменные которой входят в раз навсегда фиксированное счетное подмножество переменных.
Предыдущая << 1 .. 8 9 10 11 12 13 < 14 > 15 16 17 18 19 20 .. 70 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed