RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления





Для просмотра файлов Вам могут потребоваться






Летняя школа «Современная математика», 2010
19 июля 2010 г. 09:30, г. Дубна
 


Теорема Гёделя — синтаксическая версия

В. А. Успенский
Видеозаписи:
Windows Media 541.2 Mb
Flash Video 905.8 Mb
MP4 905.8 Mb

Количество просмотров:
Эта страница:2312
Видеофайлы:1088

В. А. Успенский


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке

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

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017