Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
2.1. Алфавит любого языка класса 21 разбивается на шесть попарно непересекающихся подмножеств. В следующей таблице
Алфавит языков
Подмножества алфавита Обозначения и названия
общие в Li Set в L, Аг
Связки и кванторы <—<• (равносильно; -»(следует); V (или неразделительное); Д (И); Н (Не); V(квантор общности); д (квантор существования)
Переменные %, у, г, и, V, . . . с индексами
Константы с . . . (с индексами) 0 (пустое множество) 0 (нуль) 1 (единица)
Операции рангов 1, 2, 3, . . . f, gr. • • • (с индексами) нет -)- (Сложение), ранг 2 • (умножение), ранг 2
Отношения (предикаты) рангов 1, 2, 3, . . . р, Ч, • • • (с индексами) е (быть элементом, ранг 2) =(равенство, ранг 2) = (равенство), ранг 2
Скобки ( (открывающая скобка); ) (закрывающая скобка)
11
перечислены: видовые названия элементов этих подмножеств, стандартные их обозначения в общем случае, специальные обозначения, принятые в этой книге для языков LjSet и LiAr. Вслед за этим мы описываем правила формирования отмеченных выражений и вкратце обсуждаем семантику.
Отмеченные выражения любого языка L* класса i?i делятся на два типа: термы и формулы. Те и другие определяются рекурсивно. Отмеченные тексты — выводы — определены в § 4 гл. II.
2.2. Определение
Множество термов — это наименьшее подмножество, выражений языка, удовлетворяющее двум условиям:
а) переменные и константы суть (атомарные) термы;
б) если / — операция ранга г, a U, ..., tr— термы, то f(U, ... ,.., tr) — терм.
В условии а) элемент отождествляется с последовательностью длины 1. Запятая не входит в алфавит, это — принадлежность сокращенной записи f(tu ..., t3), означает то же, что f(ti.hta). В § 1 гл. II объяснено, как однозначно дешифровать последовательности термов, несмотря на отсутствие знака-разделителя.
Если два множества выражений языка удовлетворяют условиям а), б), то и их пересечение удовлетворяет им. Поэтому определение множества термов корректно.
2.3. Определение.
Формулы — это наименьшее подмножество выражений языка, удовлетворяющее двум условиям:
а) если р — отношение ранга г, a tu ..., tT—термы, то p(ti, ... ..., tr) есть (атомарная) формула;
б) если Р, Q суть формулы (сокращенная запись!), х — переменная, то выражения (Ру—>(Q), (Р) —* (Q), (Р) V (Q). (Р)А{Q)> ~](Р)> Vх (А ’ 3-* (р) сУть формулы.
Из определений видно, что любой терм получается из атомарных термов за конечное число шагов, каждый из которых состоит в «применении символа операции» к полученным ранее термам. Это верно и для формул. В § 1, гл. II мы уточним это замечание.
Следующие первоначальные истолкования термов и формул даны для ориентировки и относятся к так называемым «стандартным моделям» (точные определения см. в § 2 гл. II).
2.4. Примеры и толкования, а) Термы служат названиями (обозначениями) объектов теории. Атомарные термы — это названия неопределенных (переменные) или конкретных (константы) объектов. Терм f{tt, ..., tr) есть обозначение объекта, получившегося в результате применения операции, обозначенной f, к объектам, обозначенным U, ..., tr. Вот примеры из LiAr
0 — обозначение нуля,
1 — обозначение единицы,
12
+(11)— обозначение двойки (1 -f- 1 =2 в обычной записи).
+(1 + 0 0) — обозначение тройки,
• (+00 + 00) — обозначение четверки (2X2—4!)-Так как эта нормализованная запись расходится с принятой в арифметике, мы будем обычно писать в LiAr tl + t2 вместо + 0+) и tvt2 вместо *0+)- Можно рассматривать это соглашение как очередную условность сокращенной записи: х — обозначение неопределенности целого числа, х+1 или + (xl)—обозначение следующего за ним числа.
В языке Li Set все термы атомарные:
х — обозначение неопределенного множества,
0 — обозначение пустого множества.
б) Формулы служат обозначениями высказываний (суждений, предложений ...) теории. Высказывание, переведенное на неформальный язык, может оказаться истинным, ложным или неопределенным (если оно относится к неопределенным объектам): см. точные определения в гл. II.
Атомарная формула p(U, ..., tT) в общем случае имеет примерно такой смысл: «упорядоченная r-ка объектов, обозначенных tu ..., tr, обладает свойством, обозначенным р». Вот примеры атомарных формул в ЦАг. Их общая структура= (/+) или в ненормализованной записи ti=h\
0=7, Т(0=Т), х+Т=у.
I Примеры неатомарных формул:
1 (х = 0)^^(х +1 — 1),
j yx((x = 0)Vn(-*-*=0)))-
J Атомарные формулы в ,L‘i Set: г/ех (у является элементом х),
j у=х, х=0, а также 0^у, х<=0 и т. п. Нормализованная запись,
I конечно, должна была бы иметь вид е (ху) и т. п.
I Некоторые неатомарные формулы:
] ЯХ(ЧУ(~\ (#&*))): существует такое х, что ни одно у не является
1 его элементом. Неформально это означает «существует пустое
множество». Еще раз напомним, однако, что неформальное толкование подразумевает некоторую стандартную интерпретацию, которая будет явно введена в гл. II.
у у (у&~~+у(Ех) ? 2 есть подмножество х.
Это—пример очень употребительного приема сокращенной записи: в формуле слева опущены четыре скобки. Мы не будем точно описывать, какие скобки разрешается опускать: их восстановление
