Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
Определение 1.6, в частности, устанавливает правила гигиены при перемене обозначений. Если в данной формуле мы хотим назвать неопределенный объект х другим именем у, то обязательно нужно позаботиться о том, чтобы х не фигурировало в тех частях формулы, где это имя у было уже использовано в качестве обозначения произвольного неопределенного объекта под знаком квантора. Иными словами, х не должен связывать. Более того, если мы хотим сказать, что х получился посредством каких-то операций ИЗ других неопределенных объектов (х=терм ОТ Ух, ..., уп), то имена у и ..., уп не должны быть связаны.
Близкая параллель к этим правилам из языка анализа: вместо
X X
Г f (у) йу можно спокойно написать (* / (г) йг, но не следует писать
1 1
X
^!(х)йх: переменная х связана “в области действия знака /( ) й( )“. 1
2. ИНТЕРПРЕТАЦИЯ; ИСТИННОСТЬ; ВЫРАЗИМОСТЬ
2.1. Пусть задан язык Ь класса 3? 1 и некоторое множество (или класс) М. Задать интерпретацию языка Ь в М — значит указать способ придания смысла формулам Е как высказываниям об элементах М.
29
Точнее говоря, интерпретация ф языка Ь в М состоит из набора отображений, которые сопоставляют термам и формулам языка элементы М или структуры над М (в смысле Бурбаки). Эти отображения делятся на первичные, которые собственно и определяют интерпретацию, и вторичные, которые естественно и однозначно восстанавливаются по первичным. Сами эти отображения, а иногда и их значения мы также будем называть интерпретациями.
Перейдем к систематическим определениям. Элементы алфавита Б будем иногда называть символами. Обозначение интерпретации ф мы будем включать в обозначения связанных с ней отображений или опускать его в зависимости от контекста.
2.2. Первичные отображения.
а) Интерпретация констант есть отображение множества символов констант (алфавита Б) в М, которое символу с ставит в соответствие ф(с)е.И.
б) Интерпретация операций есть отображение множества символов операций (алфавита Б), которое каждому символу / ранга г ставит в соответствие функцию ф(/) на МХ ... ХМ=МГ со значениями в М.
в) Интерпретация отношений есть отображение множества символов отношений (алфавита Б), которое каждому символу р ранга г ставит в соответствие подмножество ф (р)^Мг.
Вторичные отображения. Интуитивно, мы хотим интерпретировать переменные как имена «общего элемента» множества М, которым можно придавать конкретные значения из М. Терм Цхи ... хг) мы хотим интерпретировать как функцию ф(/) от г аргументов, пробегающих значения из М и т. п.
Чтобы дать точное определение, введем интерпретационный класс М:
М=класс всех отображений в М множества символов переменных в алфавите Б. __
Таким образом, каждая точка ставит в соответствие лю-
бой переменной х ее значение ф(х) (|)е.М, которое мы чаще будем обозначать просто х|.
Это позволяет рассматривать переменные как функции на М со значениями в М. Более общо:
2.3. Интерпретация термов есть сопоставление каждому терму ^ функции ф(/) на М со значениями в М. Оно определяется индуктивно следующими соглашениями:
а) если с — константа, то ф(с) есть постоянная функция со значением, которое определено первичным отображением;
б) если х — переменная, то ф(х) есть ф(х) (?) как функция от
в) если t=4(t^, ..., и), то для всех
Ф(0Ш=Ф(0(<р(*1)(5). .... ф(<п)(Ш.
30
где <р(^)Ш определены по индуктивному предположению, а <р (/) : МГ-^М заданы первичным отображением.
Вместо ср(0(|) мы будем для краткости писать иногда А
2.4. Интерпретация атомарных формул. Всякой формуле Р языка L' при интерпретации <р приписывается ее функция истинности |Р|,. Это — функция на интерпретационном классе М, принимающая только значения 0 («ложь») и 1 («истина»). Для атомарных формул она определяется так:
1 p(t OI,©=/1’ если(^ tyetiP).
[О иначе.
Интуитивно высказывание р об именах ti, ..., tr объектов из М становится истинным, если объекты, названные именами tu ..., tr, удовлетворяют отношению, именем которого является это высказывание.
2.5. Интерпретация формулы. На неатомарных формулах функция истинности определяется индуктивно следующими соотношениями (скобки и указание на <р и \ для краткости опущены):
[P^Q| = |P||Q|+(1_|P|)(1_|Q|):
Р-<—>-Q истинна, когда либо Р и Q обе истинны, либо Р и Q обе ложны;
|P^Q|=1_|P| + |/>||Q|;
P->Q ложна, только когда Р истинна, a Q ложна;
PVQ!=max(l^l* IQI):
P\/Q ложна, только когда обе Р, Q ложны;
[РД Q|=min(|P|, | Q |):
PДQ истинна, только когда обе Р, Q истинны;
ПР| = 1_|Р,:
“1Р ложна, только когда Р истинна.
Наконец, при введении кванторов происходит следующее. Пусть 1<=М, х — некоторая переменная. Назовем изменением \ по х любую точку 1'^М, для которой у^ — у^', если у — любая переменная, отличная от х. Тогда
|ухР | (?) = min | Р | (?'); | gхР | (?) =max | Р | (?'),
где I' пробегает все изменения по х.
Корректность определений 2.3—2.5 обеспечивает лемма об однозначном чтении.
Мы будем называть формулу Р ^-истинной, если |РЦ$)=1 для всех ? G М. Интерпретация <р (или М) называется моделью множества формул е, если все элементы е ф-ИСТИННЫ.
