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

План Парадоксы самоприменимости Теорема Тарского о невыразимости истины Теорема Геделя о неполноте Теорема Геделя о недоказуемости непротиворечивости Недоказуемость «естественного» утверждения Программа Гильберта 2

3 Утверждение, которое вы сейчас видите на экране, – ложно.

4 Формализация Утверждение в формальном языке, говорящее о собственной ложности Ложность (истинность) можно понимать по-разному.

5 Арифметики Арифметика = «Настоящие» натуральные числа и операции. Можно рассматривать слова в алфавите 0,1 (алфавит B) и операции над ними, через которые определять арифметические операции. Можно рассматривать отношения вместо операций.

6 Арифметики Существует много структур, не изоморфных Настоящим натуральным числам (с операциями), но со всеми свойствами натуральных чисел. – то есть они имеют ту же теорию – обсуждалось раньше (нестандартные модели с бесконечно большими элементами...) Желаемое: Все свойства натуральных чисел могут быть выведены из некоторых Аксиом.

7 Арифметика Пеано Аксиомы, в добавление к аксиомам исчисления логики отношений Аксиомы Пеано (замыкания формул, т. е. впереди) 1. Аксиомы равенства для S, +, x, 2. S(x) = 0, S(x) = S(y) x = y, 3. x + 0 = x, x + S(y) = S(x + y), 4. x x 0 = 0, x x S(y) = x x y + x, 5. (Схема аксиом индукции) ( (х) u( (u) (S(u)))) u (u), для любой формулы. (У Джузеппе Пеано аксиомы были другие.) Этих аксиом оказывается достаточно для известных доказательств в теории чисел. 7

8 Арифметики Реальность: Не существует системы аксиом, из которых могут быть выведены все свойства («настоящих») натуральных чисел, записываемые в логике отношений (и только они). – в частности, не годится система аксиом Пеано – тема сегодня

9 Нам нужно в языке говорить о формулах самого языка. Структура – ансамбль слов в алфавите {0, 1}. Отношения введем постепенно. Язык логики отношений. Слова в алфавите языка логики отношений кодируются в алфавите {0, 1}. Задача. Придумать способ кодирования слов в любом алфавите словами в B. Цепочки слов – тоже кодируются. Задача. Придумать способ кодирования цепочек слов. Кодирование

10 Структура М (вариант арифметики) Область – слова в алфавите {0,1}. В сигнатуре есть 0,1 может быть операция приписывания слов, могут быть, кроме этого, +, x и др. Слова в алфавите {0,1} – термы (но могут быть и другие термы). Задача. Как обойтись в дальнейших рассуждений без функций, используя только символы для отношений. Условие на структуру: Выразима функция подстановки: Подст: Код слова, получаемого подстановкой вместо свободной переменной х второго аргумента в формулу, кодом которой является первый аргумент. Пусть Г – формула с одной свободной переменной х. Что такое Подст (код Г, код Г)? Это – код Г (код Г).

11 Гёделева диагональ Ф – какая-то формула с одной свободной переменной Г = Ф (Подст(x,x)) Г (код Г) = Ф (Подст (код Г, код Г)) = Ф (код Г (код Г)) Теорема Тарского. Не существует формулы Ф в заданной сигнатуре, выражающей свойство: «быть кодом истинного в М утверждения». Д. Предположим, такая формула Ф существует. Построим Г для Ф. Пусть: Г (код Г) – истинно. Тогда: Ф (код Г (код Г)) – истинно (Предпол.), Ф (код Г (код Г)) – ложно, т.е. Г (код Г) – ложно (см. выше). Пусть: Г (код Г) – ложно. Тогда: Ф (код Г (код Г)) – ложно (Предпол.), Ф (код Г (код Г)) – истинно, Г (код Г) – истинно.

12 Гёделева диагональ Ф – формула с одной свободной переменной Г = Ф (Подст(x,x)) Г (код Г) = Ф (Подст (код Г, код Г)) = Ф (код Г (код Г)) Пусть в нашей структуре М для всякого исчисления над алфавитом {0,1} выразимо свойство «быть кодом по родимого (выводимого) в этом исчислении слова». Теорема Гёделя о неполноте. Не существует исчисления, порождающего в точности истинные в нашей структуре формулы. Д. Пусть такое исчисление существует, и Ф выражает свойство «быть кодом по родимого слова». Пусть: Г (код Г) – истинна. Тогда: она выводима. Ф (код Г (код Г)) – истинно, Ф (код Г (код Г)) – ложно, Г (код Г) – ложно. Противоречие Пусть: Г (код Г) – ложна. Тогда: она не выводима. Ф (код Г (код Г)) – ложно, Ф (код Г (код Г)) – истинно, Г (код Г) – истинно. Противоречие

Комментарий Предположение: Пусть в нашей структуре М для всякого исчисления над алфавитом {0,1} выразимо свойство «быть кодом по родимого (выводимого) в этом исчислении слова». «Структура достаточно богата» Породимость исчислением = Породимость грамматикой – достаточно нескольких простых отношений. Все интересные для описания математики структуры достаточно богаты.

Теорема Геделя о неполноте Другое доказательство Задача. Множество истинных формул – не породило. Подсказка. Всякое породилое множество можно выразить в («достаточно богатой») арифметике. Задача. Как из этих соображений получить Т. Геделя?

Теорема Геделя о неполноте Программа Гильберта Не истинность, а доказуемость Теорема Геделя, иная формулировка – Существуют утверждения такие, что не доказуемо ни утверждение, ни его отрицание.

16 Программа Гильберта. Полнота. Невозможна, в силу Теоремы Геделя о неполноте. Непротиворечивость. Доказательство невозможности получить противоречие надежными, «финитными» средствами (как невозможность получить какую-то позицию в шахматной игре). Пусть в нашей структуре М для всякого исчисления над алфавитом {0,1} выразимо свойство «быть кодом выводимого в этом исчислении слова». Пусть Ф выражает свойство «быть кодом выводимого слова». Аксиоматическая теория – исчисление, получаемое добавлением к исчислению логики отношений каких-то аксиом. Формула Непр = Ф (код 0), здесь 0 – Ложь, из нее выводится все.

Вторая теорема Гёделя о неполноте. Не существует непротиворечивой аксиоматической теории, в которой выводимо утверждение о ее непротиворечивости. То есть Непр - невыводимо. Задача. Как может выглядеть доказательство? Таким образом, непротиворечивость не может быть установлена не только «финитными» средствами, но даже средствами самой теории.

18 Соотношение с обычной арифметикой Сигнатура приписывания не менее естественна, чем сигнатура сложения и умножения. В рассматриваемой сигнатуре могут быть +, x. Подстановка и выводимость («быть кодом выводимой формулы») могут быть выражены через приписывание, а приписывание – через +, x. Приписывание несущественно расширяет арифметику.

Программа Гильберта Арифметика Пеано не полна. Теория множеств (она будет сформулирована) – не полна (или противоречива). Доказательство непротиворечивости невозможно. Возможна ли математика?

Естественные недоказуемые утверждения Важные теоремы и проблемы теории чисел, комбинаторики, математической логики, теории вычислений и т. д. можно формулировать в арифметике. Постепенно для них удается найти доказательства, решения и т. д. Теорема Геделя показывает, что иногда это может быть и не так – возможны утверждения, для которых доказательство или опровержение (в теории Пеано) не будет найдено никогда. Однако в теореме Геделя утверждение «диагональное», «само применимое», «специально построенное», говорит что-то о самой теории и доказуемости и т. д. Есть ли «естественные» утверждения арифметики, не доказуемые и не опровержимые? 20

21 Истинное, но не доказуемое в PA утверждение Червь Беклемишева Червём будем называть произвольную цепочку натуральных чисел. Нос червя – последний элемент цепочки. Голова червя – максимальный конец цепочки(включая нос), все элементы которого не меньше носа. Хвост червя – оставшаяся начальная часть последовательности (хвост может быть пустым). В примерах голова – красная (нос – тёмно-красный), хвост – зелёный: (а) (б) (в) (г)

22 Истинное, но не доказуемое в PA утверждение Эволюция червя Эволюция червя происходит по шагам. После каждого шага заново определяем, где у червя хвост, голова, нос. Если нос равен 0, то отрезаем его, и на следующем шаге цепочка становится на 1 короче. Если на (k-1)-м шаге нос не равен 0, то на k-м шаге к голове червя приделываем ещё k копий головы и в каждой из (k+1) копий нос уменьшаем на 1. Пример 1:Пример 2: w 0 = 0w 0 = 1 w 1 = w 1 = 0 0 w 2 = 0 w 3 =

23 Истинное, но не доказуемое в PA утверждение Эволюция червя. Пример 3. w 0 = 2 w 1 = 1 1 w 2 = w 3 = w 4 = w 5 = w 6 = w 7 = w 8 = w 9 = w 10 = w 11 = w 23 = 1 0 w 24 = 1 w 25 = … w 50 = 0 w 51 =

24 Истинное, но не доказуемое в PA утверждение Эволюция червя. Пример 4. w 0 = 3 w 1 = 2 2 w 2 = w 3 = w 4 = w 5 = w 6 = (212120) 3 ( ) 7 w 7 = (212120) 3 ( ) w 8 = (212120) 3 ( ) 6 ( ) 9 w 9 = (212120) 3 ( ) 6 ( ) w 10 = (212120) 3 ( ) 6 ( ) 8 ( ) 11...

25 Истинное, но не доказуемое в PA утверждение Утверждение. Любой червь в процессе эволюции рано или поздно (но скорее поздно, чем рано) исчезнет (превратится в пустую цепочку). Задача. Доказать утверждение. Утверждение. Предыдущее утверждение истинно, но не доказуемо в арифметике Пеано PA.

26 Теорема Гёделя Пропасть между доказуемостью и истинностью, между математикой и реальностью

В 1999 году "Time magazine" провозгласил Гёделя величайшим математиком XX века и включил его в список "Ста великих людей столетия". 27

28

1930 Вена, Венский кружок Курт Гедель (род. 1906) Диссертация Геделя (1929) – теорема о полноте

1930 Kurt Gödel Теорема о неполноте (лето 1930), разговор во вторник, 26 августа, в Cafe Reichsrat, в котором участвует Карнап (рассказавший об этом в своем дневнике) и, возможно, еще пара членов Венского кружка.

1930 Д. Гильберт родился (в 1862 г.) под Кенигсбергом (Wehlau – Знаменск), возможно, в самом Кенигсберге (Калининграде). 5-7 сентября International Conference on the Epistemology of the Exact Sciences (Königsberg). – В нем участвуют виднейшие специалисты по логике и основаниям математике (в частности, члены Венского кружка. 5 сентября Доклад Дж. Фон Неймана о Программе Гильберта 6 сентября выступление Геделя с теоремой о полноте – Воспринято, как очевидное (так мы исчисление и строили). 7 сентября заключительный круглый стол. Замечание Геделя с теоремой о неполноте. – Не замечено никем, кроме фон Неймана. 8 сентября – открытие Съезда немецких ученых и врачей. Знаменитое выступление Гильберта: в математике не может быть непознаваемого, всякая проблема будет решена.

1930 Не верьте тем, кто сегодня философствуют и предсказывают падение культуры и неизбежность непознаваемого (ignorabimus). Для нас, как и для всех естественных наук, не существует непознаваемого. Нашим девизом должно быть: Мы должны знать - мы будем знать! Задача. Как быть?