Разные варианты выбора неопределяемых понятий. Система аксиом Тарского (по-видимому, самая простая из известных). Роль аксиом непрерывности с точки зрения различия логики первого и второго порядков. Модели и синтаксические интерпретации формальных теорий. Несколько классических интерпретаций, в том числе взаимная интерпретируемость гиперболической и евклидовой геометрии, элементарной геометрии Тарского и элементарной теории поля вещественных чисел, интерпретация теории поля вещественных чисел в арифметике натуральных чисел. Теоремы Тарского о полноте аксиоматики и о существовании алгоритма, распознающего истинность утверждений элементарной геометрии.

Гипотеза Римана может быть сформулирована как утверждение об определителях некоторых матриц, элементы которых задаются через коэффициенты разложения дзета-функции Римана в ряд Тейлора. Оказалось, что в распределении собственных чисел этих матриц можно увидеть некоторые закономерности, позволяющие сформулировать новые гипотезы. В докладе будет показано много «картинок» и компьютерная анимация, раскрывающая «тайную жизнь дзета-функции Римана».

В докладе рассмотрены два класса объектов, имеющих различную природу, но неожиданным образом аналогичные по своим свойствам. С одной стороны, так называемые алгебры доказуемости, возникающие при изучении свойств формальной доказуемости в арифметических теориях. С другой стороны, топологические пространства, наделённые одной или несколькими разреженными топологиями, то есть такими, что любое непустое подмножество X имеет хотя бы одну изолированную точку.

В середине XIX века были сделаны открытия, которые в корне изменили алгебру и привели к ее окончательному отделению от арифметики. История открытия алгебры кватернионов и булевой алгебры.

В 1900 году великий немецкий математик Давид Гильберт сформулировал свои знаменитые Математические проблемы. В десятой из них он просил найти алгоритм для распознавания наличия решений у произвольных диофантовых уравнений. Семьдесят лет спустя было установлено, что такого алгоритма не существует. Техника, развитая для доказательства этого, позволила получить ещё много интересных результатов, например, построить многочлен с целыми коэффициентами, множество всех положительных значений которого (принимаемых при произвольных целочисленных значениях переменных) есть в точности множество всех простых чисел.

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

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

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

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

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