Введение в математическую логику и теорию алгоритмов презентация

∀u,v (u=v ⇒ v=u) – симметричность,
∀u,v,w (u=v ∧ v=w ⇒ u=w) – транзитивность.

Теория равенства

если
(1) Г содержит аксиомы теории равенства,
(2) для каждого имени отношения P, входящего в Г,
в теории Г имеется аксиома
∀u1,. . ., uk,v1, . . .,vk ((u1=v1 ∧ . . . ∧ uk=vk) ⇒ (P(u1,. . .,uk) ⇔ P(v1,. . .,vk))).

Структура сигнатуры с равенством называется нормальной, если имени “=“ Зн сопоставляет совпадение предметов (обычное равенство).

теории с равенством Г,
Определим M'= , где
D' – множество классов эквивалентности на D по отношению, являющемуся значением символа =,
Для каждого P из Σ Зн'(P)(A1,. . .,Ak) = 1 ⇔ Зн(P)(a1,...,ak) = 1 для каких-то ai ∈ Ai.
Задача.
(1) Определение корректно (не зависит от выбора a1,...,ak) (2) M' – нормальная структура,
(3) для любой формулы Φ(x1,. . . , xk)
M' ⊨ Φ(A1,. . . ,Ak) ⇔ M ⊨ Φ(a1,. . . , ak), ai ∈ Ai.
Доказательство (3) – индукция по построению.

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

доказать неопределимость?
Невозможность сложнее установить.
Иррациональность корня из двух, несчетность континуума.
Задача: Можно ли определить порядок целых чисел через сложение?
Смена знака сохраняет сложение и не сохраняет порядок.
Что значит «сохраняет»?

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

столетия, Италия
Основания арифметики и геометрии

1908 Точка и сфера
Полная аксиоматизация Евклидовой геометрии на основе понятий точки и равноудаленности двух точек от третьей

и геометрии

1900

Международный философский конгресс
Эссе алгебраической теории целых чисел, предваряемое логическим введением во всякую дедуктивную теорию

Второй международный конгресс математиков
Новая система определений для Евклидовой геометрии

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

Вацлав Серпинский…

Адольф Линденбаум
12.06.1904 – 1941, Поняры

Альфред Тарский
14.01.1901 – 26.10.1983

«лежать между»
Четырехместное отношение: «конгруэнтность пар точек»

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

> –
счетная структура .Следующие
два условия эквивалентны:
(i) R не определимо в ,
(ii) существует счетное элементарное расширение
M′ = < A′, Σ ⋃ { R } >
структуры M и
автоморфизм < A′, Σ > , не сохраняющий R.
Т. е., метод автоморфизмов универсален.
Вопрос. Как связаны Зн символов из Σ ⋃ { R } на A и A′ .

Ларс Свенониус
1927 - 27.09.2010

не только имена отношений).
Задача. Построить логику (формулы, семантика).
Th(M) – множество утверждений, истинных в M , возможно, содержащих имена элементов из D.
Пусть M = ⟨D,Σ,Зн⟩, D1 ⊆ D.
Подструктура M1 = ⟨D1,Σ,Зн1⟩, отображение Зн1 является ограничением Зн на D1, объекты с теми же именами те же.
M1 – элементарная подструктура M : M ⊨ Φ(a) ⇔ M1 ⊨ Φ(a) для любых формул Φ и наборов a = < a1, ..., ak > ∈ D1* . M – элементарное расширение M1. Обозначение M1 ≺ M
Очевидно M эквивалентна M1.
З. M1 изоморфно элем. расширению M ⇔ M1 модель Th(M).

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

M0 ≺ M1 ≺ · · · ≺ Mn ≺ . . . и конечные биекции φ0 ⊂ φ1 ⊂ . . . ⊂ φn ⊂. . . , φi : Mi → Mi.
В процессе построения нам потребуется нумерация элементов структур Mi, будем их нумеровать так, что
{a< 0, 0 >, . . . , a< 0, n >, . . . } – все элементы M0,
{a< i, 0 >, . . . , a< i, n >, . . . } – все элементы Mi \ Mi−1. (Последовательность счетных множеств и нумерацию можно заготовить заранее.) Перебирая элементы в порядке номеров мы получим все множество ⋃i Mi .
Отображения φi будут удовлетворять условию:
(*) если {a1, . . . , am} – область определения φi , а
Q(x1, . . . , xm) – произвольная формула в сигнатуре Σ, то
Mi ⊨ Q(a1, . . . , am) ≡ Q(φi(a1), . . . , φi(am)). Т. е. φi –
«частичный изоморфизм».
Заметим, что из (*) следует взаимная однозначность φi,
поскольку равенство входит в сигнатуру Σ.

Пусть Q1, …,Qk ,… – все n-местные формулы в сигнатуре Σ. Добавим имена a, b ;
Th(M) ⋃ {Qi (a) ≡ Qi (b) | i } ⋃ {¬ R(a) ≡ R(b)} непротиворечива.
Иначе (теорема компактности) для некоторого k :
(∗∗) M ⊨ ∀ x, y ((∧ki = 1 (Qi (x) ≡ Qi (y)) → R(x) ≡ R(y)) Множество Mn разбивается на 2k подмножеств, где все Q1,… ,Qk постоянны (для x, y из одного подмножества посылка истинна). (**) утверждает, что отношение R постоянно на каждом из этих подмножеств.
Задача. Тогда R определимо.

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

Строим Mi+1и φi+1.
i – четно, e – первый элемент Mi, не входящий в область определения { e1, . . . , em} отображения φi.
Пусть Q = Q1, . . . ,Qk, . . . – все (m + 1)-местные формулы в Σ.
Обозначения αj= (Mi ⊨ Qj (e1, . . . , em ,e))
(0, A)= ¬A, (1, A) = A, (как для д.н.ф.)
Теория Th(Mi) ⋃ {(αj, Qj (φi (e1), . . . , φi (em), b)) | j } непротиворечива (здесь b – новое имя объекта). Иначе
Mi ⊨ ¬(∃x (∧kj = 1 (αj, Qj (φi (e1),… , φi (em), x)))) для некоторого k.
По индуктивному предположению (*) - φi частичн. изоморф. :
Mi ⊨ ¬(∃x (∧kj = 1 (αj, Qj (e1, . . . , em ,x)))), но
Mi ⊨ ∧kj = 1 (αj, Qj (e1, . . . , em , e)).
Итак, есть модель - Mi+1. Положим φi+1 = φi ⋃ {< e, d >}, где d – значение имени b.

образа φi.
В качестве структуры M′ возьмем объединение структур
Mi, а в качестве отображения φ – объединение
отображений φi.

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