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

Презентация на тему Введение в математическую логику и теорию алгоритмов, предмет презентации: Разное. Этот материал содержит 21 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

Слайды и текст этой презентации

Слайд 1
Текст слайда:

*

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

Алексей Львович Семенов

Лекция 8


Слайд 2
Текст слайда:

План

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


Слайд 3
Текст слайда:


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

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


Слайд 4
Текст слайда:

Теории с равенством. Нормальные структуры

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

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


Слайд 5
Текст слайда:

Преобразование структуры в нормальную

Пусть M = – модель теории с равенством Г,
Определим 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) – индукция по построению.


Слайд 6
Текст слайда:

Пространства определимости

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


Слайд 7
Текст слайда:

Пространства отношений

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


Слайд 8
Текст слайда:

Автоморфизмы

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


Слайд 9
Текст слайда:

Джузеппе Пеано 27.08.1858 – 20.04.1932

Марио Пьери
22.06.1860 – 01.03.1913

Конец XIX – начало XX столетия, Италия
Основания арифметики и геометрии

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


Слайд 10
Текст слайда:

Алессандро Падоа
14.10.1868 – 25.11.1937


Конец XIX – начало XX столетия, Италия
Основания арифметики и геометрии

1900

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

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


Слайд 11
Текст слайда:

Падоа

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


Слайд 12
Текст слайда:

1920-1930-е, Польша (Россия, Пруссия) Основания логики

Польская школа логики: СтанИслав Лесневский, Ян Лукасевич, Вацлав Серпинский…

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

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


Слайд 13
Текст слайда:

Геометрия

Примитивными понятиями Геометрии Тарского являются:
Точка
Два отношения между точками:
Трехместное отношение «лежать между»
Четырехместное отношение: «конгруэнтность пар точек»

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


Слайд 14
Текст слайда:

ТЕОРЕМА СВЕНОНИУСА

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

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


Слайд 15
Текст слайда:

Еще о логике отношений

В сигнатуре могут иметься и имена объектов (а не только имена отношений).
Задача. Построить логику (формулы, семантика).
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).


Слайд 16
Текст слайда:

Доказательство

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



Слайд 17
Текст слайда:


Доказательство (i) ⇒ (ii).
Будем строить 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,
поскольку равенство входит в сигнатуру Σ.


Слайд 18
Текст слайда:


Шаг 0. структура M0.
n – число аргументов отношения R.
Пусть 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 определимо.


Слайд 19
Текст слайда:


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


Слайд 20
Текст слайда:


Шаг i. Поочередно расширяем область определения и область значения отображения. Строим 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.


Слайд 21
Текст слайда:


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

Задача. утверждение (ii) выполнено.
Д. почему изоморфизм…

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


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика