Изменения
→Теорема Геделя о неполноте
|statement= Любая непротиворечивая формальная система аксиом <tex>T</tex>, способная выражать утверждения о натуральных числах и доказывать простые арифметические факты, неполна {{---}} существуют утверждения о натуральных числах, которые она не может ни доказать, ни опровергнуть.
|proof=
# Предположим, что система <tex>T</tex> полна, т.е. доказывает или опровергает любое утверждение.
# Сформулируем и запишем на языке арифметики утверждение <tex>O</tex> = "машина Тьюринга <tex>M</tex> точно остановится, если запустить ее с данными <tex>D</tex>".
# Переберем все доказательства (<tex>P</tex> {{---}} истинно) и опровержения (<tex>\neg P</tex> {{---}} истинно) в системе <tex>T</tex>, чья длина совпадает с длиной <tex>O</tex>.
# Так как система <tex>T</tex> полна, рано или поздно мы найдем опровержение или доказательство утверждения <tex>O</tex>
# Поскольку система Система <tex>T</tex> доказывает не только истинные факты(так как она только непротиворечива), мы фактически решили проблему остановкит.Это очень простой способ доказательства теоремы Геделя о неполноте, но при этом он требует корректности <tex>T</tex> (тем не менее обычные системы аксиом арифметики всегда корректны)е."Перекроим" доказательство, используя только непротиворечивость: если доказываемое утверждение оказалось может быть ложным.# Тем не менее, мы все ещё фактически решили проблему остановки.
}}
