Тезис Геделя. Теорема Черча — страница 6

  • Просмотров 3091
  • Скачиваний 331
  • Размер файла 4
    Кб

формальные системы называются корректными. Формальная система называется консистентной, если она не может доказать одновременно какое-то утверждение и его отрицание, т.е. доказать противоречие. Неконсистентная формальная система — это плохо и практически бесполезно, т.к. можно легко показать, что из доказательства противоречия можно получить доказательство чего угодно. Неконсистентная формальная система доказывает вообще

любое утверждение, так что ничего интересного в ней нет. Если система корректна, то она автоматически консистентна: ведь она доказывает только истинные утверждения, а какое-то утверждение и его отрицание не могут одновременно быть истинными: одно из них будет истинным, а другое ложным. Заметим, однако — это важно! — что "консистентность", как и "доказуемость" есть свойство синтаксическое, не зависящее от смысла формул

и их интерпретации; а вот корректность системы есть свойство семантическое, требующее понятия "истинности". Наконец, формальная система называется полной, если для любого утверждения φ она может доказать либо φ, либо ¬φ ("не-φ"). Доказательство ¬φ называется также опровержением φ ; таким образом, полная система может либо доказать, либо опровергнуть любою утверждение. В некотором смысле она "на все

вопросы даёт ответ". Что ни скажешь про натуральные числа — она сможет либо доказать это, либо опровергнуть. Это свойство полноты – тоже синтаксическое, не пользующееся понятием "истинности". Теперь мы можем определить три формулировки теоремы Гёделя о неполноте следующим образом: 1. Пусть T — "подходящая" (см. выше) формальная система, и предположим также, что T — корректная система. Тогда множество утверждений,

которые T может доказать, и множество истинных утверждений не совпадают (а так как все доказуемые с помощью T утверждения истинны, отсюда сразу следует, что есть истинные утверждения, недоказуемые в T). 2. Пусть T — "подходящая" формальная система, и предположим опять, что T корректна. Тогда мы можем построить конкретное утверждение G (называемое "гёделевым утверждением"), обладающее следующим свойством: G истинно, но

недоказуемо в T. 3. Пусть T — "подходящая" формальная система, и предположим, что T консистентна. Тогда T не является полной системой, т.е. существует утверждение G такое, что T не может его ни доказать, ни опровергнуть; более того, мы можем построить такое конкретное G (называемое "гёделевым утверждением"). Неполнота системы T утверждается в качестве результата только в третьей версии, но легко видеть, что она сразу следует из