Илья Мещерин: Теорема Гёделя (начало доказательства)

В Кочерге продолжается цикл семинаров по теории алгоритмов — науке, которая является свзующим звеном между программированием и абстрактной математикой. Это область с огромным числом нерешенных вопросов, в числе которых одна из проблем тысячелетия — проблема «P=NP?». За прошедшие встречи мы уже успели обсудить основы теории множеств и логики предикатов, машины Тьюринга и проблему остановки, доказали неразрешимость проблемы равенства слов в полугруппах и как следствие — теорему Чёрча о неразрешимости исчисления предикатов. Более подробный список рассказанного, а также задачи по темам лекций и ссылки на литературу есть на странице http://mesyarik.ru/18/kocherga_algori...
На этой встрече мы наконец сформулируем и начнем доказывать одно из наиболее знаменитых утверждений в данной области — теорему Гёделя о неполноте формальной арифметики. Для понимания необязательно знать материал всех предыдущих лекций, но желательно разбираться в основах логики в целом (понимать, как устроены булевы функции, что такое кванторы, предикаты, свободные и связанные переменные, логическое следствие и равносильность). Остальные нужные понятия напомним или определим по ходу дела. Ведущий — Илья Мещерин, студент 6 курса кафедры дискретной математики МФТИ, студент Школы анализа данных Яндекса. kocherga.timepad.ru/event/636898 vk.com/kocherga_math?w=wall-103194586_84