Теоремы о превосходстве
Сразу хочу предупредить, по вопросу теоремы Гёделя я консультировался с целой кучей людей, каждый из которых утверждал, что он прекрасно понимает математику - уж точно получше меня. И что логика у него гарантированно железная.
То есть прекрасно понимающими математику людьми с железной логикой авторитетно установлено, что если у вас есть хоть малейшие сомнения в состоятельности доказательства теоремы Гёделя, то математику вы не понимаете вообще, с логикой у вас проблемы и, не исключено, вы ещё и тупой.
Поскольку же я дальше буду использовать исключительно метод доказательства Гёделя, имейте всё это в виду: если вы усомнитесь в истинности сказанного, то см. выше.
Но для начала вкратце перескажу доказательство первой теоремы Гёделя о неполноте и суть выводов из оного.
Предположим, что мы решили доказывать теоремы из области формальной арифметики и, возможно, ещё какой-то математики при помощи специального автомата. Этот специальный автомат занимается вот чем: он берёт данное ему выражение, а потом пытается его преобразовать всеми возможными способами и всеми их комбинациями, кои возможные способы преобразования заданы через произвольную «систему аксиом».
Если автомат вдруг находит такую последовательность преобразований, которая в конечном счёте превращает данное ему выражение в true, то мы считаем, что мы получили доказательство истинности этого выражения. А если нашли цепочку, которая выражение превращает в false, то доказана ложность оного. Если же не нашли ни того, ни другого, то ну, ой - нельзя из этой системы аксиом доказать ни истинность, ни ложность данного выражения.
Теперь давайте сделаем функцию canProve, которая пользуется этим автоматом, чтобы попытаться найти означенную цепочку преобразований для переданного ей выражения, и если такая найдена, то говорит нам «true». Дескать, такая цепочка есть, поэтому истинность вашего выражения доказать возможно. А если цепочка не нашлась, или же нашлась цепочка, которая превращает выражение в false, то canProve говорит нам «false» - невозможно доказать истинность вашего выражения.
Может показаться, что причём тут формальная арифметика? Чистая логика же и операции над строками!
Однако Гёдель придумал очень хитрый способ кодирования выражений в числа.
Очень хитрый - потому что не догадался, что любой конечный текст это уже и так число: любой текст ведь можно записать в файл, а файл - это последовательность битов, то есть число в двоичной системе счисления.
Ну а если мы в функцию передаём числа, то это уже математика - не смотри, что в текстовом виде цифры ничем не отличаются от букв и любых других значков, а последовательность бит, как уже было сказано, всегда является числом, но при этом вполне может быть и закодированным текстом, независимо от того, математические выражения в нём или «Евгений Онегин».
В общем, этот очень важный момент с кодированием в числа и обратно хитровывернутым способом мы пропустим: будем просто помнить, что это - математика, поскольку мы как бы незримо туда-сюда каждый раз кодируем.
А раз математическое утверждение будет доказывать автомат, то и он тоже математический, а не какой попало.
Так вот, возьмём эту вашу функцию canProve и попытаемся её озадачить вот таким вот утверждением.
Утверждение 1:
canProve(утверждение 1) == false
Ну или, если записать это на разговорном языке…
Утверждение 1:
Этот ваш автомат не сможет доказать утверждение 1.
Теперь смотрите.
Если автомат сможет доказать утверждение 1, то тем самым он докажет утверждение о том, что он не может доказать утверждение 1.
А если автомат не сможет доказать утверждение 1, то утверждение 1 истинно - ведь в нём как раз и говорится, что автомат не сможет доказать утверждение 1.
Иными словами, как ни поверни, а утверждение 1 этот автомат доказать не может.
Не смотри, что вывод оказывается одним и тем же при любом исходе, а потому, получается, от исхода не зависит - это неважно. Важно то, что не может.
Причём, поскольку систему аксиом мы тут никак не оговаривали, он не может доказать его при использовании любой системы аксиом. В том числе, при использовании той, на базе которой он сам построен.
Раз так, то, значит, чего ни делай, а всё равно не все утверждения сможет этот автомат для перебора доказать. По крайней мере, если система аксиом непротиворечива, и потому автомат не может положить на всё болт, сказав нам: «ваши умопостроения меня вообще не волнуют - я всё равно нашёл доказательство, и потому я могу это доказать».
Иными словами,
Существуют такие утверждения, которые принципиально не может доказать непротиворечивый автомат.
Или же…
Существуют такие утверждения, которые принципиально не могут быть доказаны никакой механической комбинацией правил преобразования.
Однако смотрите, автомат не сможет доказать утверждение 1, но мы-то в это время как раз доказали, что он не сможет! Как вам такое?
Поскольку же утверждением как раз и было «автомат не сможет», то истинно то, что этот автомат принципиально не может доказать однозначно истинное утверждение, какой бы ни была непротиворечивая система аксиом, им используемая.
Таким образом,
Любая непротиворечивая система аксиом неполна.
В легендах этот вывод превратился во что-то типа «вы ничего не докажете, наука не работает», но понимающие люди понимают: нет, это не о тщете и суетности научного метода, а о том, что чисто механически совсем даже не всё можно доказать.
Ну, во всяком случае, сам Гёдель в этой теореме видел аргумент против того, чтобы всё в математике запрограммировать и автоматизировать. Дескать, не-не-не-не-не, без человека с его полётом воображения всё равно никуда - никакие автоматы с математикой не справятся. Мы, правда, нашли всего одно такое утверждение, и сочли его «математическим» только потому, что его можно и числом тоже записать (как и всего «Евгения Онегина», например). Да и доказать его истинность, как оказалось, возможно, но мало ли что? Если одно такое есть и автомат его доказать в принципе не мог, то это значит, что такие утверждения существуют: истинные, но недоказуемые механически.
Однако я думаю, что Гёдель не туда копал: не сам тезис теоремы надо использовать, а метод её доказательства - тогда пространство умопомрачительных выводов значительно расширится.
Что я вам сейчас, после столь длинного описания диспозиции, и продемонстрирую.
Давайте возьмём вот такое утверждение…
Утверждение 1:
Гёдель не сможет доказать утверждение 1.
Как мы помним, это утверждение можно записать в виде чего-то похожего на формулу с функцией canGödelProve, а можно в виде числа (поскольку любой текст можно, а это - тоже текст). Поэтому сие - математическое утверждение, что сразу же прибавляет ему дополнительных очков авторитетности.
Теперь смотрите, всё раскручивается точно так же, как и в прошлый раз.
Если Гёдель докажет утверждение 1, то он тем самым докажет, что Гёдель не сможет доказать утверждение 1.
Если же Гёдель не сможет доказать утверждение 1, то оно, значит, истинно - ведь в нём же как раз и говорится, что Гёдель его не сможет доказать. И значит, истинно то, что Гёдель не сможет доказать утверждение 1.
То есть, чего Гёдель ни делай, а доказать это утверждение ему принципиально не суждено.
Кто-то подумает, что я клоню к тому, что Гёдель - это тоже автомат: ведь это автоматы доказывать не могут, а люди могут. Но нет, я совсем не к тому.
Я к тому, что Гёдель утверждение 1 доказать не сможет, но я-то только что доказал истинность этого утверждения.
Таким образом, мы можем сформулировать ещё одну теорему, которую я, чтобы её из-за слишком сильного сходства не путали с «теоремой Гёделя о неполноте», назову…
Теорема Лекса 1 (о превосходстве меня над Гёделем)
Существуют такие суждения, истинность которых принципиально не может доказать Гёдель, а я могу.
Однако, право слово, пока что как-то мелковато - превосходство меня всего лишь над Гёделем.
Давайте лучше рассмотрим вот такое утверждение.
Утверждение 2:
Никакой человек, если он не я, не сможет доказать утверждение 2.
Как легко догадаться, это утверждение тоже истинно: если кто-то, кроме меня, докажет утверждение 2, то он докажет, что никто, кроме меня, это утверждение доказать не сможет, а если никто, кроме меня, не сможет это утверждение доказать, то, значит, то, что в нём утверждается, истинно.
В свою очередь, я опять доказал истинность этого утверждения, что подводит нас ко второй теореме о превосходстве.
Теорема Лекса 2 (о превосходстве меня над всеми остальными)
Существуют такие суждения, истинность которых принципиально не может доказать никто, кроме меня.
Всё по фен-шую, в общем. То есть по матлогике, я имел в виду. Но одно меня смущает: всё выглядит так, будто бы и я, и Гёдель тут как бы случайно. Кажется, кого сюда ни подставь, а всё равно всё будет сходиться.
Давайте попробуем.
Утверждение 3:
Произвольная группа людей А не сможет доказать утверждение 3.
Если кто-то из группы А сможет, то он докажет истинность того, что никто из группы А не сможет. А если никто действительно не сможет, значит утверждение истинно.
При этом все остальные люди могут повторить написанное в предыдущем абзаце и тем самым доказать истинность утверждения 3.
Хм. Опять всё сошлось.
Теорема Лекса 3 (о превосходстве кого угодно над кем угодно)
Существуют такие суждения, истинность которых принципиально не может доказать произвольная группа людей, а другие люди могут.
Не, ну то, что я круче Гёделя и всех людей вообще - тут всё понятно: это ж всё-таки я.
Однако по третьей теореме Лекса получается, что логика в принципе субъективна что ли? Как и математика?
Получается ведь, что есть суждения (которые, как мы знаем, математические - ведь их можно преобразовать в число), возможность доказательства истинности которых зависит от того, кто это доказывает? Одни, значит, в принципе не смогут некое математическое суждение доказать, а другие запросто докажут? И так для любой пары людей? И для любых произвольных групп оных?
Эвон как оно вышло. Но что делать, матлогика неумолима: если доказали, то доказали. Мы ведь не хотим, чтобы нас обозвали непонимающими логику.
Теорема Лекса 4 (о субъективности логики)
Логика и, в частности, математическая логика принципиально зависят от личностей тех, кто их использует.
Однако хотелось бы всё-таки закончить это повествование на оптимистической ноте. Для коей цели мы сейчас нагнём заодно с логикой и математикой и все естественные науки тоже.
Рассмотрим такое утверждение…
Утверждение 5:
Произвольная группа людей А не сможет поставить серию экспериментов, доказывающих утверждение 5.
Дальше вы уже знаете: если кто-то поставит, то докажет утверждение 5, а если никто не сможет поставить, то утверждение 5 истинно, поскольку именно об этом и говорит. А раз группы произвольные, то, ну вы поняли - для любых групп одни могут, а другие принципиально не могут.
Из этого, как легко догадаться, выводится дополнение к четвёртой теореме Лекса.
Теорема Лекса 5 (о субъективности всех естественных наук)
Все естественные науки принципиально зависят от личностей тех, кто их использует.
Гуманитарии, кстати, сейчас если радуются, то зря радуются.
Утверждение 6:
Произвольная группа людей А не сможет доказать утверждение 6 вообще никаким способом.
Ну, теперь-то никто не ушёл обиженным. Слава богу.
doc-файл
То есть прекрасно понимающими математику людьми с железной логикой авторитетно установлено, что если у вас есть хоть малейшие сомнения в состоятельности доказательства теоремы Гёделя, то математику вы не понимаете вообще, с логикой у вас проблемы и, не исключено, вы ещё и тупой.
Поскольку же я дальше буду использовать исключительно метод доказательства Гёделя, имейте всё это в виду: если вы усомнитесь в истинности сказанного, то см. выше.
Но для начала вкратце перескажу доказательство первой теоремы Гёделя о неполноте и суть выводов из оного.
Предположим, что мы решили доказывать теоремы из области формальной арифметики и, возможно, ещё какой-то математики при помощи специального автомата. Этот специальный автомат занимается вот чем: он берёт данное ему выражение, а потом пытается его преобразовать всеми возможными способами и всеми их комбинациями, кои возможные способы преобразования заданы через произвольную «систему аксиом».
Если автомат вдруг находит такую последовательность преобразований, которая в конечном счёте превращает данное ему выражение в true, то мы считаем, что мы получили доказательство истинности этого выражения. А если нашли цепочку, которая выражение превращает в false, то доказана ложность оного. Если же не нашли ни того, ни другого, то ну, ой - нельзя из этой системы аксиом доказать ни истинность, ни ложность данного выражения.
Теперь давайте сделаем функцию canProve, которая пользуется этим автоматом, чтобы попытаться найти означенную цепочку преобразований для переданного ей выражения, и если такая найдена, то говорит нам «true». Дескать, такая цепочка есть, поэтому истинность вашего выражения доказать возможно. А если цепочка не нашлась, или же нашлась цепочка, которая превращает выражение в false, то canProve говорит нам «false» - невозможно доказать истинность вашего выражения.
Может показаться, что причём тут формальная арифметика? Чистая логика же и операции над строками!
Однако Гёдель придумал очень хитрый способ кодирования выражений в числа.
Очень хитрый - потому что не догадался, что любой конечный текст это уже и так число: любой текст ведь можно записать в файл, а файл - это последовательность битов, то есть число в двоичной системе счисления.
Ну а если мы в функцию передаём числа, то это уже математика - не смотри, что в текстовом виде цифры ничем не отличаются от букв и любых других значков, а последовательность бит, как уже было сказано, всегда является числом, но при этом вполне может быть и закодированным текстом, независимо от того, математические выражения в нём или «Евгений Онегин».
В общем, этот очень важный момент с кодированием в числа и обратно хитровывернутым способом мы пропустим: будем просто помнить, что это - математика, поскольку мы как бы незримо туда-сюда каждый раз кодируем.
А раз математическое утверждение будет доказывать автомат, то и он тоже математический, а не какой попало.
Так вот, возьмём эту вашу функцию canProve и попытаемся её озадачить вот таким вот утверждением.
Утверждение 1:
canProve(утверждение 1) == false
Ну или, если записать это на разговорном языке…
Утверждение 1:
Этот ваш автомат не сможет доказать утверждение 1.
Теперь смотрите.
Если автомат сможет доказать утверждение 1, то тем самым он докажет утверждение о том, что он не может доказать утверждение 1.
А если автомат не сможет доказать утверждение 1, то утверждение 1 истинно - ведь в нём как раз и говорится, что автомат не сможет доказать утверждение 1.
Иными словами, как ни поверни, а утверждение 1 этот автомат доказать не может.
Не смотри, что вывод оказывается одним и тем же при любом исходе, а потому, получается, от исхода не зависит - это неважно. Важно то, что не может.
Причём, поскольку систему аксиом мы тут никак не оговаривали, он не может доказать его при использовании любой системы аксиом. В том числе, при использовании той, на базе которой он сам построен.
Раз так, то, значит, чего ни делай, а всё равно не все утверждения сможет этот автомат для перебора доказать. По крайней мере, если система аксиом непротиворечива, и потому автомат не может положить на всё болт, сказав нам: «ваши умопостроения меня вообще не волнуют - я всё равно нашёл доказательство, и потому я могу это доказать».
Иными словами,
Существуют такие утверждения, которые принципиально не может доказать непротиворечивый автомат.
Или же…
Существуют такие утверждения, которые принципиально не могут быть доказаны никакой механической комбинацией правил преобразования.
Однако смотрите, автомат не сможет доказать утверждение 1, но мы-то в это время как раз доказали, что он не сможет! Как вам такое?
Поскольку же утверждением как раз и было «автомат не сможет», то истинно то, что этот автомат принципиально не может доказать однозначно истинное утверждение, какой бы ни была непротиворечивая система аксиом, им используемая.
Таким образом,
Любая непротиворечивая система аксиом неполна.
В легендах этот вывод превратился во что-то типа «вы ничего не докажете, наука не работает», но понимающие люди понимают: нет, это не о тщете и суетности научного метода, а о том, что чисто механически совсем даже не всё можно доказать.
Ну, во всяком случае, сам Гёдель в этой теореме видел аргумент против того, чтобы всё в математике запрограммировать и автоматизировать. Дескать, не-не-не-не-не, без человека с его полётом воображения всё равно никуда - никакие автоматы с математикой не справятся. Мы, правда, нашли всего одно такое утверждение, и сочли его «математическим» только потому, что его можно и числом тоже записать (как и всего «Евгения Онегина», например). Да и доказать его истинность, как оказалось, возможно, но мало ли что? Если одно такое есть и автомат его доказать в принципе не мог, то это значит, что такие утверждения существуют: истинные, но недоказуемые механически.
Однако я думаю, что Гёдель не туда копал: не сам тезис теоремы надо использовать, а метод её доказательства - тогда пространство умопомрачительных выводов значительно расширится.
Что я вам сейчас, после столь длинного описания диспозиции, и продемонстрирую.
Давайте возьмём вот такое утверждение…
Утверждение 1:
Гёдель не сможет доказать утверждение 1.
Как мы помним, это утверждение можно записать в виде чего-то похожего на формулу с функцией canGödelProve, а можно в виде числа (поскольку любой текст можно, а это - тоже текст). Поэтому сие - математическое утверждение, что сразу же прибавляет ему дополнительных очков авторитетности.
Теперь смотрите, всё раскручивается точно так же, как и в прошлый раз.
Если Гёдель докажет утверждение 1, то он тем самым докажет, что Гёдель не сможет доказать утверждение 1.
Если же Гёдель не сможет доказать утверждение 1, то оно, значит, истинно - ведь в нём же как раз и говорится, что Гёдель его не сможет доказать. И значит, истинно то, что Гёдель не сможет доказать утверждение 1.
То есть, чего Гёдель ни делай, а доказать это утверждение ему принципиально не суждено.
Кто-то подумает, что я клоню к тому, что Гёдель - это тоже автомат: ведь это автоматы доказывать не могут, а люди могут. Но нет, я совсем не к тому.
Я к тому, что Гёдель утверждение 1 доказать не сможет, но я-то только что доказал истинность этого утверждения.
Таким образом, мы можем сформулировать ещё одну теорему, которую я, чтобы её из-за слишком сильного сходства не путали с «теоремой Гёделя о неполноте», назову…
Теорема Лекса 1 (о превосходстве меня над Гёделем)
Существуют такие суждения, истинность которых принципиально не может доказать Гёдель, а я могу.
Однако, право слово, пока что как-то мелковато - превосходство меня всего лишь над Гёделем.
Давайте лучше рассмотрим вот такое утверждение.
Утверждение 2:
Никакой человек, если он не я, не сможет доказать утверждение 2.
Как легко догадаться, это утверждение тоже истинно: если кто-то, кроме меня, докажет утверждение 2, то он докажет, что никто, кроме меня, это утверждение доказать не сможет, а если никто, кроме меня, не сможет это утверждение доказать, то, значит, то, что в нём утверждается, истинно.
В свою очередь, я опять доказал истинность этого утверждения, что подводит нас ко второй теореме о превосходстве.
Теорема Лекса 2 (о превосходстве меня над всеми остальными)
Существуют такие суждения, истинность которых принципиально не может доказать никто, кроме меня.
Всё по фен-шую, в общем. То есть по матлогике, я имел в виду. Но одно меня смущает: всё выглядит так, будто бы и я, и Гёдель тут как бы случайно. Кажется, кого сюда ни подставь, а всё равно всё будет сходиться.
Давайте попробуем.
Утверждение 3:
Произвольная группа людей А не сможет доказать утверждение 3.
Если кто-то из группы А сможет, то он докажет истинность того, что никто из группы А не сможет. А если никто действительно не сможет, значит утверждение истинно.
При этом все остальные люди могут повторить написанное в предыдущем абзаце и тем самым доказать истинность утверждения 3.
Хм. Опять всё сошлось.
Теорема Лекса 3 (о превосходстве кого угодно над кем угодно)
Существуют такие суждения, истинность которых принципиально не может доказать произвольная группа людей, а другие люди могут.
Не, ну то, что я круче Гёделя и всех людей вообще - тут всё понятно: это ж всё-таки я.
Однако по третьей теореме Лекса получается, что логика в принципе субъективна что ли? Как и математика?
Получается ведь, что есть суждения (которые, как мы знаем, математические - ведь их можно преобразовать в число), возможность доказательства истинности которых зависит от того, кто это доказывает? Одни, значит, в принципе не смогут некое математическое суждение доказать, а другие запросто докажут? И так для любой пары людей? И для любых произвольных групп оных?
Эвон как оно вышло. Но что делать, матлогика неумолима: если доказали, то доказали. Мы ведь не хотим, чтобы нас обозвали непонимающими логику.
Теорема Лекса 4 (о субъективности логики)
Логика и, в частности, математическая логика принципиально зависят от личностей тех, кто их использует.
Однако хотелось бы всё-таки закончить это повествование на оптимистической ноте. Для коей цели мы сейчас нагнём заодно с логикой и математикой и все естественные науки тоже.
Рассмотрим такое утверждение…
Утверждение 5:
Произвольная группа людей А не сможет поставить серию экспериментов, доказывающих утверждение 5.
Дальше вы уже знаете: если кто-то поставит, то докажет утверждение 5, а если никто не сможет поставить, то утверждение 5 истинно, поскольку именно об этом и говорит. А раз группы произвольные, то, ну вы поняли - для любых групп одни могут, а другие принципиально не могут.
Из этого, как легко догадаться, выводится дополнение к четвёртой теореме Лекса.
Теорема Лекса 5 (о субъективности всех естественных наук)
Все естественные науки принципиально зависят от личностей тех, кто их использует.
Гуманитарии, кстати, сейчас если радуются, то зря радуются.
Утверждение 6:
Произвольная группа людей А не сможет доказать утверждение 6 вообще никаким способом.
Ну, теперь-то никто не ушёл обиженным. Слава богу.
doc-файл