объявление: популярный рассказ про матлогику

[kobak]

Завтра в три часа дня я буду рассказывать в гимназии математическому клубу «Эратосфен» о том, что такое математическая логика. Постараюсь излагать так, чтобы было понятно совсем неподготовленным. Если кому-то интересно — приходите. Часика полтора порассказываю, а потом чай будем пить.

В примерной программе: парадокс Рассела, «Principia Mathematica», программа Гильберта, арифметика Пеано, первая теорема Гёделя, вторая теорема Гёделя, связь этих результатов с программированием и проблема останова (с доказательством, пожалуй), результаты типа Харрингтона-Кирби-Париса (конкретно: теорема Гудстайна и задача про Геракла и гидру), континуум-гипотеза в теории множеств, платонизм — и в качестве разговоров уже за чаем: искусственный интеллект и аргументы Пенроуза. Как-то так.

Тема вообще жутко интересная, если кто совсем не в курсе.

Comments

[kobak.livejournal.com]

Я посмотрю эту главу в "Доказуемом и недоказуемом", но вряд ли основную конструкцию доказательства можно сделать существенно проще: нужно вводить операцию подстановки в незамкнутую формулу её собственного номера, записывать формулу для такой операции, потом рассматривать некую открытую формулу, включающую в себя в частности и эту операцию, а потом целиком к этой формуле эту же операцию применять -- и тогда получится искомое гёделево утверждение. Это довольно запутанно.

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

А про циркуль и линейку я тогда напишу отдельно.

[ex-dmitri83798.livejournal.com]

"Я посмотрю эту главу в "Доказуемом и недоказуемом", но вряд ли основную конструкцию доказательства можно сделать существенно проще: нужно вводить операцию подстановки в незамкнутую формулу её собственного номера, записывать формулу для такой операции, потом рассматривать некую открытую формулу, включающую в себя в частности и эту операцию, а потом целиком к этой формуле эту же операцию применять -- и тогда получится искомое гёделево утверждение. Это довольно запутанно."

простое на мой взгляд доказательство есть в учебнике Шенфилда (Schoenfield). что в нём ещё хорошо, так это то, что оно концептуально интересно.

там сначала доказывается теорема Чёрча, что любое (непротиворечивое) расширение арифметики неразрешимо. потом доказывается утверждение, что любая рекурсивно аксиоматизируемая полная теория разрешима (архиполезное само по себе утверждение). из этого напрямую делается вывод, что любое рекурсивно аксиоматизированное расширение арифметики неполно (теорема Гёделя).

[kobak.livejournal.com]

Да, я знаю такой вариант рассуждений. Мне он не очень нравится, потому что он в каком-то смысле неконструктивный: гёделево утверждение здесь не предъявляется, в отличие от настоящего доказательства. Но интересно, да.

[ex-dmitri83798.livejournal.com]

да, неконсруктивный. но можно рассказать такое доказтельство, потому что оно проще и занимает меньше времени :) (если не вдаваться в технические детали), а потом сказать, что есть конструктивное доказательство, но формула, которую в нём конструируют, искусственная и является формулировкой парадокса лжеца.

[ex-dmitri83798.livejournal.com]

вот ещё нашёл красивое и простое рассуждение

http://en.wikipedia.org/wiki/Halting_problem#Relationship_with_G.F6del.27s_Incompleteness_Theorem

только они там на самом деле не теорему Гёделя доказывают, а неразрешимость логики первого порядка. но метод важен -- так можно доказать неразрешимость любой логики (что и делают). грубо говоря, если на языке какой-то логики можно написать "эта машина Тьюринга останавливается", то логика неразрешима.

[kobak.livejournal.com]

Да, именно так я и хотел детям рассказывать. От неразрешимости до неполноты один шаг.