Теорема Гёделя о неполноте гласит, что для любой непротиворечивой формальной системы, в рамках которой может быть выполнено определенное количество арифметики, существуют утверждения, которые нельзя ни доказать, ни опровергнуть. Тем самым устанавливая границы тому, что математика может доказать.
Английский перевод оригинальной статьи:
https://www.jamesrmeyer.com/ffgit/god...
В этом видео мы рассмотрим контекст для теоремы, поймем суть, о чем она, а затем пройдемся по полуформальному доказательству этого для тех, кто хотел бы покопаться немного глубже.
В начале 20-го века математики, такие как Дэвид Гилберт, Бертран Рассел, Альфред Норт Уайтхед, чувствовали, что, учитывая правильный набор аксиом формальной системы, любая математическая теория может быть доказана как истинная или ложная путем систематического применения эти аксиомы в цепочке логических операций. Именно здесь Курт Годел в своей работе 1931 года потряс основы математики, доказав, что для любой непротиворечивой формальной системы, в рамках которой может быть выполнено определенное количество арифметики, такой как арифметика Палео, существуют утверждения, которые невозможно доказать ни опровергнут.
Аксиоматическая система должна быть непротиворечивой, что означает, что ни утверждение, ни отрицание не могут быть получены путем простого следования другой последовательности аксиом и теорем.
И, наконец, упоминание «определенного количества арифметики» относится к возможности хотя бы перечислить теоремы языка. Так что очень простая система, которая не имеет вычислительной мощности, может на самом деле быть последовательной и полностью завершенной. Но тогда у него также не будет силы, необходимой для выражения даже простых вычислений.
Давайте теперь рассмотрим, как Годель доказал свою теорему. По сути, он построил законное, хорошо сформулированное математическое утверждение, которое подразумевало, что оно само не доказуемо.
Чтобы построить такое утверждение, мы начнем с этого лингвистического парадокса:
«Это утверждение не соответствует действительности»
Простое прочтение представляет проблему, так как, если мы предположим, что это утверждение верно, его значение предполагает противоположное. С другой стороны, если утверждение неверно, то подразумеваемое значение оказывается истинным, отсюда и парадокс.
Итак, что нужно сделать, чтобы построить подобное утверждение, но выразить его формально в математической записи?
Есть две неотложные проблемы. Прежде всего, слово «правда», как ни удивительно, не определяется аксиоматически. Числа и формулы не имеют свойства «true». Мы думаем об аксиомах как об истинных, и поэтому теоремы, которые вытекают из них, также будут истинными. Но тогда понятие истины все равно будет находиться за пределами самой системы.
Теорема Тарского о неопределимости:
https://en.wikipedia.org/wiki/Tarski%...
Другое проблемное слово - это. Это относится к самому утверждению, но оно еще не было определено. Это все равно, что сказать «Это видео ровно 16 минут и 9 секунд», не сделав видео.
Чтобы обойти эту проблему, Годель нашел способ преобразования утверждений, таких как теоремы и даже доказательства этих теорем, в натуральные числа как тип кодирования. Затем, перечислив кодировки определенных видов формул, он показал, что в этом списке есть натуральное число, соответствующее формуле, которая заявляет о своей собственной недоказуемости.
Кодирование Годеля устанавливает однозначное соответствие между уникальной последовательностью символов и некоторым уникальным номером. Это позволило Годелю преобразовать любое математическое утверждение, а также доказательство этого утверждения в два уникальных числа.
Примеры недоказуемых утверждений
https://en.wikipedia.org/wiki/Paris%E...
Дальнейшее чтение о теоремах Гёделя о неполноте:
https://plato.stanford.edu/entries/go...
Информация по комментариям в разработке