Высказывания математического языка (в том числе, содержащие переменные, от значения которых зависит истинность утверждений) можно записывать на формальном языке математической логики. (Например, можно использовать значок ∀ вместо выражения «для всех».) Однако даже и без точного описания языка математической логики (которое, впрочем, будет дано) можно понять, что значит объяснить (выразить) одно из свойств чисел через другое, например, выразить свойство «быть простым числом» через свойство «делиться». В лекции будут рассмотрены примеры задач, относящихся к выразимости и невыразимости. Среди высказываний математического языка можно выделить те, которые не содержать переменных и называть их утверждениями. Было бы хорошо иметь общий способ, пусть даже и очень громоздкий, который про любое утверждение, касающееся чисел (или иных математических объектов) и отношений между ними, позволяет установить, истинно оно или ложно. Будут приведены примеры, когда такой способ есть, и когда его нет.

«Качественная» теория алгоритмов (не касающаяся понятия сложности вычислений) может быть построена на интуитивном представлении о том, что такое алгоритм. Такого представления, при некотором его уточнении, оказывается достаточно для того, чтобы доказать первые базовые теоремы теории алгоритмов. В лекции будет приведено указанное уточнение, определено понятие вычислимости и понятие породимости («выводимости в формальной системе»), доказано несколько теорем, другие теоремы — предложены в качестве задач. Будут приведены и примеры т.н. «уточнения понятия алгоритма». Для понимания лекции желательно умение читать по-русски, знание латинского алфавита и представление о натуральном ряде.

Попытки дать математические определения понятий формального доказательства, истинности, формализованной деятельности по инструкции привели к построению математической логики и теории алгоритмов — области математики, результаты которой сформировали и продолжают формировать основы информатики и влиять на практическое использование цифровых технологий. Важнейшие результаты данной области, наряду с указанными определениями — это результаты о невозможности, в свою очередь тесно связанные с результатами об универсальности и диагональными конструкциями.

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

Все мы знаем, что математика доказывает импликации. Другими словами, мы доказываем не то, что какое-то утверждение верно, а то, что оно следует из принятых нами аксиом. Но при этом часто недооценивается, насколько сильно можно поменять набор аксиом. Одно из базовых понятий математики, на которых видна степень условности выбора конкретного набора аксиом – понятие множества. Сначала оно казалось совершенно очевидным. К сожалению, этот подход привёл к противоречиям. После этого стали развиваться разные способы работать со множествами не приходя к парадоксам. Понятие множества используется во многих разделах математики, из-за чего работать со множествами обычно учат постепенно, по кусочкам добавляя факты как естественные и самоочевидные основы, пока не получится теория, носящая имя ZFC. Из-за этого часто оказывается заметён под ковёр тот факт, что ZFC лишь один из возможных вариантов и что замена оснований теории множеств совсем не обязана рушить другие разделы математики. Курс будет посвящён рассказу о том, что может быть проблемой при пользовании какой-то аксиоматикой и сколь разнообразны варианты. Предварительные требования будут изменены в соответствии со знаниями и интересами аудитории; я надеюсь, что обозначения →, ∀, ∨, ∈, ∈, ∪, … всё же всем знакомы и привычны настолько, что ошибочно кажутся понятными.

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

Классическая логика высказываний исходит из предположения о том, что любые высказывания либо истинны, либо ложны. Логика доказуемости отражает более глубокую картину мира, осознанную после теорем Гёделя о неполноте: истинность высказывания, вообще говоря, не равносильна его доказуемости. Можно ли — и если да, то как — говорить на уровне логики о доказуемости или недоказуемости высказываний, наряду с их истинностью или ложностью? Программа: Логика высказываний и её модели. Модальная логика, модели Крипке. Логика Гёделя-Лёба GL. Теорема о полноте логики GL по Крипке на конечных деревьях. Формальная арифметика Пеано. Гёделева нумерация. Теорема о неподвижной точке. Формулы доказуемости и непротиворечивости. Теоремы Гёделя, Россера и Лёба. Доказуемость как модальность: арифметическая интерпретация логики GL. Замкнутые модальные формулы, последовательность Тьюринга, локальная рефлексия. Существование и единственность модально определимых неподвижных точек (теорема де Йонга).

Вычислимая функция f:N→N называется доказуемо рекурсивной в данной формальной теории T, если существует алгоритм её вычисления такой, что в T можно доказать утверждение «для любого x существует y такой, что f(x)=y». В математической логике такие функции изучаются по двум причинам. Во-первых, для данной программы нас часто интересует доказательство её корректности, в частности вопрос о том, завершает ли она работу при любых исходных данных. С другой стороны, варьируя функцию f мы можем ставить для теории T сколь угодно сложные (вплоть до невыполнимости) задачи на доказательство. Тем самым, доказуемо рекурсивные функции могут быть использованы для изучения различных формальных теорий. Такой подход приводит к наиболее впечатляющим на сегодняшний день примерам недоказуемых комбинаторных утверждений. Мы начнем с понятия машины Тьюринга и вычислимой функции. Разберемся, как формальная арифметика может говорить о вычислениях. Поймем, что для любых разумных систем аксиом T их запас доказуемо рекурсивных функций никак не может исчерпывать все вычислимые всюду определенные функции. Отсюда выведем первую теорему Гёделя о неполноте.

Теорема Гёделя о неполноте — едва ли не самая знаменитая теорема математики. Она утверждает, что какие бы способы доказывания ни предложить, в любом достаточно богатом языке найдутся истинные, но не доказуемые утверждения. Богатство языка есть его способность выражать факты. Оказывается, что для целей теоремы Гёделя богатство языка достаточно понимать как его способность выражать принадлежность натуральных чисел перечислимым множествам.

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