Введение в математическую логику и теорию алгоритмов Алексей Львович Семенов Лекция 8

22 План Логика отношений Выразимость Невыразимость Теорема Свенониуса

Сигнатура: имя двухместного отношения = Аксиомы: u (u=u) – рефлексивность, u,v (u=v v=u) – симметричность, u,v,w (u=v v=w u=w) – транзитивность. 3 Теория равенства

4 Теории с равенством. Нормальные структуры Теория Г называется теорией с равенством, если (1) Г содержит аксиомы теории равенства, (2) для каждого имени отношения P, входящего в Г, в теории Г имеется аксиома u 1,..., u k,v 1,...,v k ( (u 1 =v 1... u k =v k ) ( P(u 1,...,u k ) P(v 1,...,v k ) ) ). Структура сигнатуры с равенством называется нормальной, если имени = Зн сопоставляет совпадение предметов (обычное равенство).

Преобразование структуры в нормальную Пусть M = – модель теории с равенством Г, Определим M ' =, где D ' – множество классов эквивалентности на D по отношению, являющемуся значением символа =, Для каждого P из Зн ' (P)(A 1,...,A k ) = 1 Зн(P)(a 1,...,a k ) = 1 для каких-то a i A i. Задача. (1) Определение корректно (не зависит от выбора a 1,...,a k ) (2) M ' – нормальная структура, (3) для любой формулы (x 1,..., x k ) M ' (A 1,...,A k ) M (a 1,..., a k ), a i A i. Доказательство (3) – индукция по построению. 5

6 Пространства определимости Считаем, что языке есть равенство и структуры - нормальные. Отношение R(X) определимо в структуре S = – существует формула логики отношений сигнатуры, задающая в структуре S отношение R. (R – n-местное отношение, все свободные переменные формулы имеют номера не больше n.) Дано множеств отношений P на A (без имен). Выберем в P конечное подмножество. Дадим отношениям из него имена, составляющие какое-то множество, построим структуру. Возникает множество определимых в ней отношений. Множество всех получаемых так отношений – замыкание P, или пространство определимости, порожденное P. Отношение включения, пересечения – обычные теоретико- множественные. Операция объединения – замыкание теоретико- множественного объединения (аналогично линейным подпространствам) и т.д. Пространства определимости «бескоординатны». 6

77 Пространства отношений Как доказать определимость? –Предъявить формулу –Мы определяли экспоненту через сложение и умножение. Как доказать неопределимость? –Невозможность сложнее установить. –Иррациональность корня из двух, несчетность континуума. Задача: Можно ли определить порядок целых чисел через сложение? –Смена знака сохраняет сложение и не сохраняет порядок. –Что значит «сохраняет»?

8 Автоморфизмы Z,+Неопределимость порядка через сложение: автоморфизм – смена знака φ(x) = - x Можно ли определить сложение через порядок ? Z, –сдвиг (+1): φ(x) = x+1 Как быть в случае натуральных чисел? –Есть ли автоморфизмы у, например? 8

9 Джузеппе Пеано – Марио Пьери – Конец XIX – начало XX столетия, Италия Основания арифметики и геометрии 1908 Точка и сфера Полная аксиоматизация Евклидовой геометрии на основе понятий точки и равноудаленности двух точек от третьей

10 Алессандро Падоа – Конец XIX – начало XX столетия, Италия Основания арифметики и геометрии 1900 Международный философский конгресс Эссе алгебраической теории целых чисел, предваряемое логическим введением во всякую дедуктивную теорию Второй международный конгресс математиков Новая система определений для Евклидовой геометрии

11 Падоа Параллель между –аксиоматическим методом, при котором теоремы выводятся из аксиом и –определением одних понятий из других Метод Падоа, 1900 Чтобы доказать, что система неопределенных символов не сводится к системе недоказанных предложений [аксиом], необходимо и достаточно найти, для каждого из неопределенных символов интерпретацию системы неопределенных символов, которая удовлетворяет системе недоказанных предложений [аксиом] и которая удовлетворяет ей при изменении смысла только этого символа

е, Польша (Россия, Пруссия) Основания логики Польская школа логики: Стан Ислав Лесневский, Ян Лукасевич, Вацлав Серпинский… Адольф Линденбаум – 1941, Поняры Альфред Тарский –

13 Геометрия Примитивными понятиями Геометрии Тарского являются: Точка Два отношения между точками: –Трехместное отношение «лежать между» –Четырехместное отношение: «конгруэнтность пар точек» Использование метода Падоа Линденбаум и Тарский: в геометрии не существует семейства бинарных отношений (между точками), через которое можно определить все отношения. Выбор Пьери одного трехместного отношения является, в некотором смысле, оптимальным.

14 ТЕОРЕМА СВЕНОНИУСА Пусть M = – счетная структура.Следующие два условия эквивалентны: (i) R не определимо в, (ii) существует счетное элементарное расширение M = структуры M и автоморфизм, не сохраняющий R. Т. е., метод автоморфизмов универсален. Вопрос. Как связаны Зн символов из { R } на A и A. Ларс Свенониус

Еще о логике отношений В сигнатуре могут иметься и имена объектов (а не только имена отношений). Задача. Построить логику (формулы, семантика). Th(M) – множество утверждении ̆, истинных в M, возможно, содержащих имена элементов из D. Пусть M = D,Σ,Зн, D 1 D. Подструктура M 1 = D 1,Σ,Зн 1, отображение Зн 1 является ограничением Зн на D 1, объекты с теми же именами те же. M 1 – элементарная подструктура M : M Φ(a) M 1 Φ(a) для любых формул Φ и наборов a = D 1 *. M – элементарное расширение M 1. Обозначение M 1 M Очевидно M эквивалентна M 1. З. M 1 изоморфно элем. расширению M M 1 модель Th(M). 15

16 Доказательство Задача. отношение транзитивно. Задача. Пусть M 0 · · · M n... – цепочка структур. Определить структуру i M i Утверждение 1. Пусть M 0 · · · M n... – цепочка структур. Тогда для любого j : M j i M i. Доказательство (Задача) Индукция по построению формулы. Как и в критерии элементарного расширения, нетривиален случай… (Все, что есть в пределе, возникло до предела.) Доказательство (ii) (i). Задача. Если определимо, то сохраняется при автоморфизмах. Идея: если R(x) выражается в M формулой (в сигнатуре ), то в M оно выражается той же формулой… 16

17 Доказательство (i) (ii). Будем строить M M 0 M 1 · · · M n... и конечные биекции φ 0 φ 1... φ n..., φ i : M i M i. В процессе построения нам потребуется нумерация элементов структур M i, будем их нумеровать так, что {a,..., a,... } – все элементы M 0, {a,..., a,... } – все элементы M i \ M i1. (Последовательность счетных множеств и нумерацию можно заготовить заранее.) Перебирая элементы в порядке номеров мы получим все множество i M i. Отображения φ i будут удовлетворять условию: (*) если {a 1,..., a m } – область определения φ i, а Q(x 1,..., x m ) – произвольная формула в сигнатуре, то M i Q(a 1,..., a m ) Q(φ i (a 1 ),..., φ i (a m )). Т. е. φ i – «частичноый изоморфизм». Заметим, что из (*) следует взаимная однозначность φ i, поскольку равенство входит в сигнатуру.

18 Шаг 0. структура M 0. n – число аргументов отношения R. Пусть Q 1, …,Q k,… – все n-местные формулы в сигнатуре. Добавим имена a, b ; Th(M) {Q i (a) Q i (b) | i } {¬ R(a) R(b)} непротиворечива. Иначе (теорема компактности) для некоторого k : ( ) M x, y (( k i = 1 (Q i (x) Q i (y)) R(x) R(y)) Множество M n разбивается на 2 k подмножеств, где все Q 1,…,Q k постоянны (для x, y из одного подмножества посылка истинна). (**) утверждает, что отношение R постоянно на каждом из этих подмножеств. Задача. Тогда R определимо. 18

19 Шаг 0. структура M 0. Итак, Th(M) {Q i (a) Q i (b) | i } {¬ R(a) R(b)} имеет модель M 0, M M 0 в ней a, b – получают значения. Определим φ 0 так, чтобы φ 0 (Зн a) =Зн b. Выполнено условие (*) – частичноый изоморфизм, не сохраняющий R. Дальше несохранение будет получаться автоматически в силу последнего утверждения. Мы не будем слишком последовательны в обозначениях для имен и для объектов. 19

20 Шаг i. Поочередно расширяем область определения и область значения отображения. Строим M i+1 и φ i+1. i – четно, e – первый элемент M i, не входящий в область определения { e 1,..., e m } отображения φ i. Пусть Q = Q 1,...,Q k,... – все (m + 1)-местные формулы в. Обозначения j = (M i Q j (e 1,..., e m,e)) (0, A)= A, (1, A) = A, (как для д.н.ф.) Теория Th(M i ) {( j, Q j (φ i (e 1 ),..., φ i (e m ), b)) | j } непротиворечива (здесь b – новое имя объекта). Иначе M i ¬( x ( k j = 1 ( j, Q j (φ i (e 1 ),…, φ i (e m ), x)))) для некоторого k. По индуктивному предположению (*) - φ i частично. изоморф. : M i ¬ ( x ( k j = 1 ( j, Q j (e 1,..., e m,x)))), но M i k j = 1 ( j, Q j (e 1,..., e m, e)). Итак, есть модель - M i+1. Положим φ i+1 = φ i { }, где d – значение имени b.

21 Задача. Построение для нечетного i. Рассмотреть первый элемент не из образа φ i. В качестве структуры M возьмем объединение структур M i, а в качестве отображения φ – объединение отображений φ i. Задача. утверждение (ii) выполнено. Д. почему изоморфизм… Задача. 1. Высказать гипотезу обо всех подпространствах определимости порядка рациональных чисел 2. Применить теорему Свенониуса для доказательства гипотезы Задача. То же для отношения следования целых чисел. (Семенов – Сопрунов) 21