1 29.10.2014 Введение в математическую логику и теорию алгоритмов Алексей Львович Семенов Лекция 5. - презентация

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

2 2 Истинность. Обозначения M = – структура, M (a 1,..., a k ) означает, что истинна в M, если вместо свободных переменных x i подставлены элементы a i. Векторные обозначения: a - набор (цепочка) элементов a 1,..., a k, D* = {Λ} D D 2 … Фиксируем сигнатуру. Все имена отношений из этой сигнатуры. D и Зн могут меняться – утверждение, т. е. замкнутая (без свободных переменных) формула, M означает, что формула истинна в M.

3 Модель теории. Семантические свойства. Теория – множество утверждений Структура M – модель теории Г, если M для любой Г. Замкнутая формула семантически следует из теории Г, если формула истинна в любой модели теории Г. Обозначение: Г. Теория, у которой есть модель, называется совместной (или семантически непротиворечивой). Теория, у которой нет моделей, называется несовместной (или семантически противоречивой). Теория Г семантически полна, если для любого утверждения в той же сигнатуре Г или Г. Будем опускать слово «семантически». 3

4 Примеры теорий u 1,...,u n v (v=u 1... v=u n ) Структуры, содержащие не более n элементов. Задача. Бывают ли теории, у которых нет бесконечных моделей, но для каждого натурального n есть модель, содержащая n элементов? 4

5 Линейный порядок u (¬R(u, u)) – антирефлексивность u,v (R(u,v) R(v,u) u = v) – трихотомия u,v,w ((R(u,v) R(v,w)) R(u,w)) – транзитивность, Будем писать < вместо R Следствие из аксиом: u,v (u

6 Линейный порядок без наибольшего элемента u (¬(u < u)) u,v (u < v v < u u = v) u,v,w ((u < v v < w) u < w)) u v (u < v) Примеры моделей: Q

7 Теория Γ Q. Плотный линейный порядок без первого и последнего элемента. u (¬(u < u)) u,v (u < v v < u u = v) u,v,w ((u < v v < w) u < w) u,v (u < v ( w (u < w < v))) – плотность u v (v < u) – неограниченность снизу u v (u < v) – неограниченность сверху Задачи Какие бывают модели? Можно ли что-то добавить, чтобы отделить Q < от R < (т.е., чтобы первая структура была моделью, а вторая – нет)? 7

8 Теория Γ N : Дискретный линейный порядок с наименьшим элементом. 1. u (¬(u < u)) 2. u,v (u < v v < u u = v) 3. u,v,w ((u < v v < w) u < w) 4. u v (u < v) 5. u (0 < u u = 0) 6. u ( v (u < v ( w (u < w (v=w v

9 Изоморфизм «Одинаковость» структур Изоморфизм множеств – равномощность Структуры M 1 = D 1, Σ, Зн 1 и M 2 = D 2, Σ, Зн 2 Взаимно однозначное отображение ψ: D 1 на D 2. Для любых a D 1 *, P Σ Зн 1 (P)(a) Зн 2 (P)(ψ(a)). Задачи: Изоморфны ли структура положительных и всех рациональных чисел с порядком? Изоморфны ли две любые счетные модели Γ Q ? Бывают ли модели теории Γ Q, равномощные R, но не изоморфные R < ? 9

10 Теории и структуры M – структура Th M – теория структуры = множество утверждений, истинных в структуре M. Теория класса структур = множество утверждений, истинных в каждой структуре класса Пусть m – класс структур, – теория. Определим отображения: Th (m) – теория класса структур m, Mod ( ) – класс всех моделей теории. Th, Mod – соответствие Галуа (анти-монотонное). Тогда m Mod ( ) Th (m). 10

11 Эквивалентность Структуры M 1 и M 2 (элементарно) эквивалентны, если Th M1 = Th M2. Задача. Почему изоморфные структуры эквивалентны? Индукцией по построению (не обязательно замкнутой) формулы Φ: M 1 Φ(a) M 2 Φ(ψ(a)) Задача. Бывают ли эквивалентные неизоморфные структуры? 11

12 Подструктура. Элементарная подструктура и элементарное расширение 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 эквивалентна M 1. Бывают ли такие структуры M и M 1, что (1) M 1 – подструктура M, и (2) M 1 эквивалентна M, но (3) M 1 не является элементарной подструктурой M? 12

13 Критерий Тарского – Воота Пусть M 1 = D 1,Σ,Зн 1 – подструктура структуры M = D,Σ,Зн, D 1 D. Следующие два условия эквивалентны: (1) M 1 – элементарная подструктура структуры M (2) для любой формулы Φ(x,y) и любого набора a D 1 * если M Φ(a,b) для некоторого b D, то M Φ(a,b) для некоторого b D 1. Доказательство (1) (2) - тривиально. Именно: M Φ(a,b) для некоторого b D M u Φ(a,u) M 1 u Φ(a,u)) M 1 Φ(a,b) для некоторого b D 1 M Φ(a,b). 13

14 Критерий Тарского – Воота (2) (1). Индукция по построению M 1 Φ(a) M Φ(a), a D 1 * Рассмотрим случай, когда Φ = u Ψ(x,u). M 1 u Ψ(a,u) M 1 Ψ(a,b) для некоторого b M 1 M Ψ(a,b) M u Ψ(a,u). M u Ψ(a,u). M Ψ(a,b) для некоторого b M M Ψ(a,b) для некоторого b M 1 M 1 Ψ(a,b) M 1 u Ψ(a,u) Задача. Провести полное доказательство критерия Тарского – Воота. 14

15 Теорема Ле ̈ венгейма – Сколема об элементарной подмодели. Т. Любая бесконечная структура с конечной или счетной сигнатурой содержит счетную элементарную подструктуру. Д. Строим цепь M 0 M 1... счётных подструктур M. M 0 произвольно. (Для M i = D,Σ,Зн пишем M i вместо D.) На i -ом шаге берем все формулы Φ(x,y), все a M i *. Если M Φ(a,b), для какого-то b M, помещаем в M i+1 это b. M = M i – счетное множество. Задача. Как определяется D для M ? Доказать что M – элементарная подструктура. Еще один метод – «Объединение цепи». 15

16 Туральф Альберт Скулем (Thoralf Albert Skolem), Леопольд Лёвенгейм Leopold Löwenheim –

17 Теорема компактности Т. (Гедель, Анатолий Иванович Мальцев) Если любое конечное подмножество теории совместно, то теория совместна. Как доказать теорему компактности? Следствие. Если утверждение является следствием теории, то это утверждение является следствием некоторого конечного подмножества данной теории. Задача. Вывести следствие из теоремы компактности. 17 А.И. Мальцев ( )

18 Полные теории Γ – Γ Φ или Γ ¬Φ для любого утверждения Φ. Задача. Почему любую совместную теорию можно расширить до полной? Задача. Th M – полна. Задача. Теория полна тогда и только тогда, когда две любые модели теории эквивалентны. Задача. Являются ли теории Γ Q, Γ N полными? Существуют ли у них неизоморфные счетные модели? 18

19 Теорема Лёвенгейма – Сколема об элементарном расширении. Теорема. Для любой бесконечной структуры с конечной или счётной сигнатурой существует элементарное расширение сколь угодно большой мощности. Доказательство. Расширяем структуру. M =, сигнатура M содержит имена для всех элементов из D, сопоставление Зн естественно продолжено до Зн'. Th M (M) – теория соответствующей структуры, M элементарно вложима в модели этой теории. Новые имена предметов {c} – произвольной мощности, Г = Th M (M) {c d}. Г совместна (компактность). Мощность модели Г не меньше мощности множества новых имен. 19