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

2 Равномощность Множества x и y равномощны (Sm(x, y)), если существует взаимно однозначная функция, отображающая x на y, то есть f (IFunc(f) x = Dom(f) y = Ra(f)). Sm(x, y) – отношение эквивалентности. Для любых двух множеств одно равномощно подмножеству другого.

3 Теорема Кантора Множество x не равномощно P(x). Д. Пусть f взаимно однозначная функция, отображающая x на P(x). Пусть a = {y | y x y f(y)}. Должно найтись такое z x, что a = f(z). Если z a, то z f(z)= a. Если z a = f(z), то z a. Противоречие.

4 Возможна ли счетная модель теории множеств? Теорема Лёвенгейма – Сколема Отображения? Не все «внешние» отображения оказываются «внутренними».

5 Первая проблема Гильберта Гипотеза континуума: Между мощностью натурального ряда и мощностью множества всех подмножеств натурального ряда нет промежуточных.

6 Возможности для математики Математика содержит ZF. 1. Математика противоречива, в ней выводится A A. Тогда в ней выводится всё что угодно, так как (A A) B – тавтология. 2. Математика непротиворечива, и это можно математически доказать, пользуясь особо надежными рассуждениями (надежда Гильберта). 3. Оказалось, что (2) невозможно (Гёдель).

7 Непротиворечивость расширений теории множеств Если теория множеств непротиворечива, то к ней можно добавлять континуум-гипотезу или её отрицание и можно добавлять аксиому выбора или её отрицание, и она не станет противоречивой. Возможность добавления аксиомы выбора и континуум-гипотезы – Гёдель, Возможность добавления отрицаний (недоказуемость Аксиомы выбора и Гипотезы континуума) – Коэн, 1963 (форсинг), Вопенка, 1965 (булевозначные модели). Независимость аксиомы (гипотезы) – возможность принять либо её, либо её отрицание. Невыводимость = возможность принять отрицание.

8 Аксиома выбора Для всякого множества S существует функция выбора, т. е. функция, отображающая всякое непустое подмножество S в его элемент (выбирающая этот элемент). Интуитивная правдоподобность. Меньшая очевидность, чем у других аксиом. Полезность. Парадоксальность следствий. Как же «на самом деле»? Не вытекает ли AC из других аксиом? Аксиома выбора для счётных множеств.

9 Независимость Аксиома параллельности (единственность) – Меньшая очевидность, чем у других аксиом – Полезность. Попытки доказать – Геометрия Лобачевского (отрицание Акс. Параллельности) – Модель Клейна В обычной геометрии Точки (точки) Прямые (хорды – интервалы) Аксиомы, кроме параллельности, выполнены. Аксиома параллельности – ложна. Независимость Что сделал Лобачевский? Николай Иванович Лобачевский Феликс Клейн

Независимость Аксиома выбора? Независимость аксиомы бесконечности Аксиома бесконечности: s ( u ( u s v(v u) ) u ( u s v ( v s w ( w v (w u w = u) ) ) ) ) Словесная формулировка аксиомы бесконечности: существует такое множество s, что оно содержит пустое множество и вместе с каждым элементом u содержит элемент v = u {u} (каждый элемент v либо совпадает с u, либо является элементом u ). 10

Независимость З. Построить модель, в которой аксиома бесконечности ложна, а все остальные аксиомы ZF истинны. Направление решения: Предполагаем, что у ZF существует модель M. Строим интерпретацию теории множеств: в модели M выделяем класс M и задаем на этом классе два двухместных отношения M и = M. В структуре I = выполнены все аксиомы, кроме аксиомы бесконечности. 11

Независимость аксиомы бесконечности В структуре M существует элемент ω = {0, 1, 2, … } = = {, { }, {,{ }}, … }. Следующий элемент: S(x) = x {x}. Индуктивное определение отношения F на ω : – (1) F(0) =, – (2) F(n + 1) = F(n) P(F(n)). По индукции: F является функцией, единственна, определена на всем ω и возрастает. Положим: – = { F(n) | n ω }. M – это, – отношения M и = M – ограничения соответствующих отношений на M: Тогда x M y x y, x = M y x = y. Ни ω, ни не включены в M. 12

Независимость аксиомы бесконечности 13

Итоги. Вопросы и ответы Что такое математика? – Доказуемо – породило в конкретном исчислении: исчисление отношений + аксиомы теории множеств ZF – Мы можем принимать или отрицать некоторые важные утверждения – Аксиому выбора, Континуум гипотезу 14

Итоги Что такое вычислимость и породилость? – Примеры и наблюдения вычисления конкретным алгоритмом, доказательства в конкретном исчислении, Индуктивное определение конкретного понятия – Базовое понятие, не формализуемое в теории множеств Понятие действия – Вычислимость и породилость попадают в теорию множеств, если принять Тезис Черча и тезис об исчислениях Грамматики Алгоритмы Маркова 15

Итоги Логика высказываний. Формулы и функции. Что такое математическая структура? – Множество с отношениями Определимость, истинность Положительные результаты – Модальная логика и Исчисление для нее – Логика отношений. Породимость множества общезначимых формул. Исчисление – Разрешимость истинности для поля действительных чисел, элиминация кванторов – Определимость вычислимости в арифметике 16

Итоги Классы моделей и теории – Существование модели у теории, в которой не доказуемо противоречие Неопределимость – Существование автоморфизмов элементарных расширений – Теорема Свенониуса 17

Итоги Отрицательные результаты – Неопределимость истинности в структуре, где определима подстановка – Не существование исчисления для истин в структуре, где определима подстановка и породилость – Теорема Геделя Программа Гильберта – Доказательство непротиворечивости и полноты «надежными средствами» – невозможно 18

Итоги Вычислимость Сложность объекта, как минимальная длина описания Переборные задачи. Существование универсальной переборной задачи. Проблема перебора. 19

Методы Диагональ. Самоприменимость Челнок, объединение возрастающих цепей Разбор случаев Моделирование. Универсальность 20