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

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

Манин Ю.И. Доказуемое и недоказуемое — Советское радио , 1979. — 89 c.
Скачать (прямая ссылка): dokazuemoinedokazu1979.djvu
Предыдущая << 1 .. 28 29 30 31 32 33 < 34 > 35 36 37 38 39 40 .. 70 >> Следующая

78
б) если Р — имя Q, то ЕР — имя экспоната Q, т. е. имя выражения. Q^cQ^c.
9.3. Замечания, а) Если Р есть имя Q, то экспонат Q имеет по крайней мере два разных имени: ЕР, Таким обра-
зом, выражение может иметь несколько имен. Наоборот по имени выражение восстанавливается однозначно: имена имеют вил Ek >к
Мы будем писать N(Q) вместо «одно из имен Q».
б) Каждая формула имеет вид rN(Q) (или 1 rN(Q)). В следующем пункте мы ее интерпретируем как высказывание «выражение Q (не) обладает свойством Я», и естественно, что, говоря о Q, формула «называет Q по имени».
в) Выражение Е % Е % является одним из двух своих имен. Точно так же формула гЕ^гЕ ^ „говорит о себе самой“ (п. 9.5). Язык SELF и был сконструирован так, чтобы эти эффекты само-описания проявлялись при возможно более скромных выразительных средствах.
9.4. Стандартные интерпретации. Чтобы определить одну из стандартных интерпретаций языка SELF, выберем любое множество (свойство) R выражений языка и введем функцию истинности | |в на его формулах соглашением
Будем говорить, что формула ^-истинна (і?-ложна), если значение | |н на ней равно 1 (0).
9.5. Теорема о невыразимости.
Для любого свойства Я
Доказательство, а)’формула <2 = ~1/-?>{с ЬЕф Я-истинна гЕ >(< “1 гЕ >(</?-ложна ?2 ф. Я, ибо Е'^~1гЕ
есть имя экспоната 'гЕ, т. е. (?. Таким образом, (2 не может одновременно лежать в Я и быть истинной, что доказывает первую часть теоремы.
Связь с парадоксом лжеца становится ясной, если учесть, что С2 говорит о себе: «Я обладаю свойством ?».
б) Аналогично формула гЕ >{с гЕ >(< говорит о себе: «Я обладаю свойством Я» и потому не может одновременно лежать в Я и быть ^-ложной.
і-Нпті*=іґЛч®і*={
1, если QG#> Одиначе.
Я П {формулы} ф
Я-истинные формулы, Я-ложные формулы.
79
10. ЯЗЫК АРИФМЕТИКИ ШМУЛЬЯНА
10.1. в этом параграфе описан язык арифметики SAr и его стандартная интерпретация. Главное отличие SAr от LiAr состоит в возможности формировать «классовые термы» — имена некоторых множеств натуральных чисел. Точнее, если Р{х)—формула SAr с одной свободной переменной х, то выражение х(Р(х)) в SAr и_менует_ множество {x^N\P(x) истинно}, а выражение x(P(x))k, где fe-терм — имя целого числа k^l, именует высказывание «k удовлетворяет Р». Это расширение средств выражения в SAr по сравнению с LiAr не увеличивает класс подмножеств
в LWr, которые выразимы формулами, но приближает синтаксис /?3:1
S Аг к синтаксису SELF настолько, что позволяет имитировать доказательство теоремы 9.5.
Кроме того, алфавит SAr по сравнению с алфавитом LiSet несколько изменен и сокращен, но это сделано лишь для упрощения описаний синтаксиса и логику SAr не обедняет.
10.2. Алфавит SAr : х (переменная) ;' (штрих для формирования счетного множества переменных х, х', х",...); • (умножение—' операция ранга 2); f (возвышение в степень, как в АЛГОЛе,— операция ранга 2); = (равенство); | (связка — конъюнкция отрицаний) ; (,) — скобки; 1 (константа единица).
10.3. Синтаксис и интерпретация SAr. Из-за разрешения формировать классовые термы х(Р(х)) и формулы х(Р(х))к описание синтаксиса сложнее, чем в языках класса .2Y
Рекурсией по целому числу 1^0 мы определим две последовательности множеств выражений: Тм2* (термы- ранга =^21) и Флгг+1 (формулы ранга ^2i-)-l). (Попутно двойной индукцией — по рангу терма или формулы, а внутри множества TM2i, Фл2г-+1— по длине устанавливается лемма об однозначности чтения, на которую опираются определения в свободных (замкнутых) вхождений и функций истинности. Ничего нового по сравнению с § 1 здесь нет, и мы оставим эти детали читателю).
Параллельно с синтаксисом описывается стандартная интерпретация S Аг в N. Чтобы интерпретировать выражения со свободными переменными, нужно фиксировать точку I^NN=Ny(N\ ..., которую мы будем отождествлять с бесконечным вектором с натуральными координатами: на k-u месте находится значение k-i\ переменной (х ‘' ’' f (k — 1 штрих).
ао) Тмо — числовые термы: наименьшее множество выражений, содержащее переменные х, х', х",..., имена натуральных чисел Г, II, Г ГГ, ... н замкнутое относительно образования выражений (U) • (t2), (М t(*2), где ^еТм0.
Вместо х (k — 1 штрих) будем кратко писать xk\ вместо
1... 1 (k>l единиц) будем писать k.
80
^ Терм А интерпретируется как к (независимо от ?); — к-я координата Е; если ^ уже*определены, то [(/,) • (?2)]5 = [(г?,) I
I &)*] = (ф‘1
Вхождения выражений хк=х'у:’ в любой терм из Тм0, очевидно, не перекрываются. Все они считаются свободными.
б0) Фл1 — наименьшее множество выражений, содержащее все выражения вида (где /^Тмо) и замкнутое относительно образования выражений (Р)|(Р2), где Р^еФль
Иными словами Фл1 — логическое замыкание множества атомарных формул {/1=^2|^^Тм0}.
Выбор точки ? определяет значение истинности любой формулы Ре Фл1 рекурсией по числу вхождений связки
1^=^ 1(^=1ес™ *»“'?**
(0 иначе;
|(^) 1 (Р.)|©=[1’ 6СЛИ = =
10 иначе.
Все вхождения переменных в элементы Фл! не перекрываются и считаются свободными.
Пусть теперь /2И и множества Тм2?г_2, Фл2ц определены для вместе с интерпретациями и противопоставлением свободных замкнутых вхождений.
Предыдущая << 1 .. 28 29 30 31 32 33 < 34 > 35 36 37 38 39 40 .. 70 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed