теорема геделя на коленке
Вот набросок простого и элегантного, на мой взгляд, подхода к доказательству знаменитой теоремы Гёделя о неполноте. Мы стремимся доказать, что любая достаточно мощная непротиворечивая формальная теория T (т.е. набор аксиом, из которых мы, пользуясь логикой, доказываем теоремы), неизбежно неполна: есть такое утверждение S, что T не доказывает ни S, ни его отрицание not-S.
Сначала небольшое вступление. Представим все возможные утверждения о чем угодно - о числах, о геометрии, о любых объектах, о которых можно рассуждать логически. Если мы хотим найти доказательства многих из них, нам нужно начать с каких-то аксиом (скажем, "2+2=4" и другие в том же духе, если мы хотим доказывать что-то про числа, ту же теорему Ферма). Представьте, что мы строим теорию T, добавляя к ней аксиому за аксиомой. Каждый раз, когда мы добавили новую аксиому, сразу много новых утверждений S, которые до этого были вне досягаемости, становятся внезапно доказуемыми. Но нам недостаточно, мы добавляем еще и еще аксиомы, и каждый раз "захватываем" много новых теорем S. Однако, если мы слишком пожадничаем, в какой-то момент мы сможем доказать слишком много - и какое-то S, и его отрицание not-S. Это будет означать, что мы дошли до противоречия: наша теория Т стала противоречивой (или "неконсистентной"). Противоречивая теория доказывает вообще все, что угодно - любую истину и любую ложь - и поэтому ни на что не годна. Этого мы не хотим. Однако можно надеяться, что если мы подберем, умно и тщательно, правильные аксиомы, то мы сможем "захватить" максимум: для любого утверждения S мы докажем либо S, либо not-S. По каждому возможному вопросу S наша теория T будет "иметь свое мнение": либо согласна - доказала S - либо не согласна - "опровергла" S, то есть доказала его отрицание.
Гедель в 1931 году доказал, что этот идеал в принципе недостижим. По мере того, как мы добавляем аксиомы в T, после того, как мы переходим определенный порог способности T доказывать интересные утверждения, она становится неизбежно неполной: всегда будут такие S, что мы не сможем доказать ни S, ни not-S, сколько бы мы ни гнались и не добавляли новых аксиом.
(разумеется, мы запрещаем себе схитрить и сказать что-то вроде "давайте добавим все истинные утверждения как аксиомы одним махом" - это жульничество, потому что мы тогда не знаем априори, что считать аксиомой, а что нет. С аксиомами все должно быть четко и понятно, что аксиома, а что нет).
Теперь набросок доказательства, которое использует понятие алгоритма или программы (но уметь программировать не нужно, чтобы его понять). Сначала надо сформулировать, что значит "переходим определенный порог способности T", туманно написанное выше. Возьмем любую программу P, которая запускается с входными данными I, работает какое-то время, заканчивает работу и выдает выходные данные O. В такой ситуации мы требуем от нашей теории T способность доказать два вида утверждений:
- "P, запущенная на I, останавливается и выдает O"
- "неверно, что P, запущенная на I, останавливается и выдает O' ", для любого неправильного варианта выходных данных O', отличающегося от настоящего O.
Это не очень строгие требования, и очень легко построить формальные теории T, способные их выполнить. Тут есть всякие технические детали, которые мы опустим; например, если наша формальная теории T говорит "на языке" натуральных чисел, то нужно сначала придумать, как "кодировать" программы P и данные I или O с помощью чисел; и как именно определить на формальном языке утверждения, написанные выше. Но в целом это просто. Главная причина, если в двух словах, того, что это просто - это что если P действительно отработала на I и выдала O, можно представить доказательство этого факта, состоящее из подробного описания работы программы, шаг за шагом, от начала до конца. Тогда теория T всего лишь должна доказать, что это описание действительно отвечает всем правилам и заканчивается на O, и что не может быть другого описания, заканчивающегося на O', потому что оно должно будет разойтись на каком-то шаге от правильного описания, а как ему разойтись, если программа все та же P, данные все те же I, и программа делает строго свою работу шаг за шагом?
Итак, предположим, что формальная теория T умеет доказывать такие утверждения, и предположим, что она непротиворечива. Напишем программу P, которая делает следующую работу:
Получив входные данные I, программа P перебирает все возможные строки текста, начиная от пустой строки или одной буквы/одного символа, потом все строки из двух символов и так далее до бесконечности. Каждую строку она проверяет: является ли эта строка доказательством в теории T одного из двух утверждений:
- "программа I, запущенная на входных данных I, останавливается и выдает 1". Если программа P находит доказательство этого утверждения, она останавливается и выдает 0.
- not-"программа I, запущенная на входных данных I, останавливается и выдает 1", то есть отрицание предыдущего. Если P находит доказательство этого утверждения, она останавливается и выдает 1.
P ищет с помощью T ответ на вопрос "что будет, если программу I запустить и дать ей собственный исходный код, верно ли, что I тогда остановится и скажет "1"? Если T доказывает, что такое случится, то P выдает 0, если T доказывает обратное, то P выдает 1.
Теперь следите за руками. Что будет, если запустить программу P и дать ей как входные данные собственный код P? Тогда программа P будет искать доказательство утверждения "P, запущенная на P, останавливается и выдает 1", или его отрицания. Назовем это утверждение W. Программа P ищет доказательство W или not-W. Найдет ли она их?
- предположим, P найдет доказательство W. Тогда по определению P, она должна остановиться и выдать 0. Но мы знаем, что в таком случае - раз P в реальности выдает 0 - теория T должна доказывать "неверно, что P запущенная на P, выдает 1", а это как раз not-W. Выходит, что T противоречива, она доказывает и W и not-W, а мы предположили, что это не так. Значит, не может быть.
- предположим, P найдет доказательство not-W. Тогда по определению P, она должна остановиться и выдать 1, но тогда мы требуем от T уметь доказать "P, запущенная на P, выдает 1", а это W. Опять выходит, что T доказывает и W, и not-W, а этого не может быть.
Вывод: P не найдет ни доказательство W, ни доказательство not-W, и поэтому вообще не остановится (так и будет перебирать до бесконечности все более длинные строки текста). Это единственная возможность, исходя из того, что T непротиворечива. Но тогда T не доказывает ни W, ни not-W: если бы такое доказательство было, P бы наткнулась на него рано или поздно. Значит, мы доказали, что хотели: Т неполная теория, причем мы нашли конкретное утверждение W - его в принципе можно выписать, если захотеть, хотя оно будет очень длинное - которое T не может ни доказать, ни опровергнуть. Это значит, что наше доказательство "конструктивное", так говорят в математике, когда могут не просто доказать существование чего-то, но даже привести конкретный пример.
Всё.
Сначала небольшое вступление. Представим все возможные утверждения о чем угодно - о числах, о геометрии, о любых объектах, о которых можно рассуждать логически. Если мы хотим найти доказательства многих из них, нам нужно начать с каких-то аксиом (скажем, "2+2=4" и другие в том же духе, если мы хотим доказывать что-то про числа, ту же теорему Ферма). Представьте, что мы строим теорию T, добавляя к ней аксиому за аксиомой. Каждый раз, когда мы добавили новую аксиому, сразу много новых утверждений S, которые до этого были вне досягаемости, становятся внезапно доказуемыми. Но нам недостаточно, мы добавляем еще и еще аксиомы, и каждый раз "захватываем" много новых теорем S. Однако, если мы слишком пожадничаем, в какой-то момент мы сможем доказать слишком много - и какое-то S, и его отрицание not-S. Это будет означать, что мы дошли до противоречия: наша теория Т стала противоречивой (или "неконсистентной"). Противоречивая теория доказывает вообще все, что угодно - любую истину и любую ложь - и поэтому ни на что не годна. Этого мы не хотим. Однако можно надеяться, что если мы подберем, умно и тщательно, правильные аксиомы, то мы сможем "захватить" максимум: для любого утверждения S мы докажем либо S, либо not-S. По каждому возможному вопросу S наша теория T будет "иметь свое мнение": либо согласна - доказала S - либо не согласна - "опровергла" S, то есть доказала его отрицание.
Гедель в 1931 году доказал, что этот идеал в принципе недостижим. По мере того, как мы добавляем аксиомы в T, после того, как мы переходим определенный порог способности T доказывать интересные утверждения, она становится неизбежно неполной: всегда будут такие S, что мы не сможем доказать ни S, ни not-S, сколько бы мы ни гнались и не добавляли новых аксиом.
(разумеется, мы запрещаем себе схитрить и сказать что-то вроде "давайте добавим все истинные утверждения как аксиомы одним махом" - это жульничество, потому что мы тогда не знаем априори, что считать аксиомой, а что нет. С аксиомами все должно быть четко и понятно, что аксиома, а что нет).
Теперь набросок доказательства, которое использует понятие алгоритма или программы (но уметь программировать не нужно, чтобы его понять). Сначала надо сформулировать, что значит "переходим определенный порог способности T", туманно написанное выше. Возьмем любую программу P, которая запускается с входными данными I, работает какое-то время, заканчивает работу и выдает выходные данные O. В такой ситуации мы требуем от нашей теории T способность доказать два вида утверждений:
- "P, запущенная на I, останавливается и выдает O"
- "неверно, что P, запущенная на I, останавливается и выдает O' ", для любого неправильного варианта выходных данных O', отличающегося от настоящего O.
Это не очень строгие требования, и очень легко построить формальные теории T, способные их выполнить. Тут есть всякие технические детали, которые мы опустим; например, если наша формальная теории T говорит "на языке" натуральных чисел, то нужно сначала придумать, как "кодировать" программы P и данные I или O с помощью чисел; и как именно определить на формальном языке утверждения, написанные выше. Но в целом это просто. Главная причина, если в двух словах, того, что это просто - это что если P действительно отработала на I и выдала O, можно представить доказательство этого факта, состоящее из подробного описания работы программы, шаг за шагом, от начала до конца. Тогда теория T всего лишь должна доказать, что это описание действительно отвечает всем правилам и заканчивается на O, и что не может быть другого описания, заканчивающегося на O', потому что оно должно будет разойтись на каком-то шаге от правильного описания, а как ему разойтись, если программа все та же P, данные все те же I, и программа делает строго свою работу шаг за шагом?
Итак, предположим, что формальная теория T умеет доказывать такие утверждения, и предположим, что она непротиворечива. Напишем программу P, которая делает следующую работу:
Получив входные данные I, программа P перебирает все возможные строки текста, начиная от пустой строки или одной буквы/одного символа, потом все строки из двух символов и так далее до бесконечности. Каждую строку она проверяет: является ли эта строка доказательством в теории T одного из двух утверждений:
- "программа I, запущенная на входных данных I, останавливается и выдает 1". Если программа P находит доказательство этого утверждения, она останавливается и выдает 0.
- not-"программа I, запущенная на входных данных I, останавливается и выдает 1", то есть отрицание предыдущего. Если P находит доказательство этого утверждения, она останавливается и выдает 1.
P ищет с помощью T ответ на вопрос "что будет, если программу I запустить и дать ей собственный исходный код, верно ли, что I тогда остановится и скажет "1"? Если T доказывает, что такое случится, то P выдает 0, если T доказывает обратное, то P выдает 1.
Теперь следите за руками. Что будет, если запустить программу P и дать ей как входные данные собственный код P? Тогда программа P будет искать доказательство утверждения "P, запущенная на P, останавливается и выдает 1", или его отрицания. Назовем это утверждение W. Программа P ищет доказательство W или not-W. Найдет ли она их?
- предположим, P найдет доказательство W. Тогда по определению P, она должна остановиться и выдать 0. Но мы знаем, что в таком случае - раз P в реальности выдает 0 - теория T должна доказывать "неверно, что P запущенная на P, выдает 1", а это как раз not-W. Выходит, что T противоречива, она доказывает и W и not-W, а мы предположили, что это не так. Значит, не может быть.
- предположим, P найдет доказательство not-W. Тогда по определению P, она должна остановиться и выдать 1, но тогда мы требуем от T уметь доказать "P, запущенная на P, выдает 1", а это W. Опять выходит, что T доказывает и W, и not-W, а этого не может быть.
Вывод: P не найдет ни доказательство W, ни доказательство not-W, и поэтому вообще не остановится (так и будет перебирать до бесконечности все более длинные строки текста). Это единственная возможность, исходя из того, что T непротиворечива. Но тогда T не доказывает ни W, ни not-W: если бы такое доказательство было, P бы наткнулась на него рано или поздно. Значит, мы доказали, что хотели: Т неполная теория, причем мы нашли конкретное утверждение W - его в принципе можно выписать, если захотеть, хотя оно будет очень длинное - которое T не может ни доказать, ни опровергнуть. Это значит, что наше доказательство "конструктивное", так говорят в математике, когда могут не просто доказать существование чего-то, но даже привести конкретный пример.
Всё.