Как доказать недоказуемость

В 19 веке Георг Кантор пришел к поразительному открытию, что бесконечностей бесконечно много, причем разных. Он научился их сравнивать и создал арифметики для этих бесконечностей – арифметику ординальных чисел и арифметику кардинальных чисел.

Он создал теория множеств из аксиом которой Давид Гильберт и другие пытались вывести всю остальную математику.

Они считали, что любое утверждение является либо истинным либо ложным и его истинность или ложность всегда можно доказать из аксиом теории – в конечном счете из аксиом теории множеств.

Однако в 1930 Курт Гедель сформулировал и доказал знаменитые теоремы о неполноте, говорящие, что это не так. 

В рамках любой аксиоматической системы существуют утверждения, которые нельзя ни доказать, ни опровергнуть исходя из данных аксиом. Обычно это интерпретируют как то, что теорема на самом деле верна, но ее верность просто невозможно доказать. Или наоборот, утверждение на самом деле ложно, но опять же доказать это в рамках данной теории невозможно.

Это такой платоновский подход, философская точка зрения реализма. Математическая теорема живет в платоновском мире идей. Она либо верна, либо нет. Просто для ее доказательства могут потребоваться новые математические инструменты, выходящие за рамки исходной теории. И математики посредством своей математической интуиции находят такие инструменты. Выходят за рамки существующих теорий.

Однако известна и противоположная точка зрения – антиреализм или номинализм — и согласно ей истинность или ложность утверждений понятие относительное. И главное в математической теории – это самосогласованность, то есть непротиворечивость, а не истинность или ложность конкретных высказываний. Непротиворечивость означает, что мы не можем доказать истинность какого-то утверждения и одновременно доказать его ложность, из тех-же самых аксиом.

В случае недоказуемого выражения по Геделю мы можем принять его за истину и получить непротиворечивую теорию. А можем принять то же самое утверждение за ложь и тоже получить непротиворечивую теорию.

Вы можете подумать, что такого не может быть. Однако существует довольно много примеров таких теорий.

Возьмем теорию групп. У нее есть набор аксиом, которым удовлетворяет группа. Для каждого элемента группы должен существовать обратный, существование единичного элемента, ассоциативность и т.д.

Но скажем утверждение, что для двух элементов группы a*b=b*a нельзя доказать из аксиом теории групп.

Вы можете принять данное утверждение за истину и получите теорию абелевых групп.

Но вы также можете принять a*b≠b*a и получите теорию неабелевых групп. Обе теории непротиворечивы. Группы в обеих теориях удовлетворяют аксиомам теории групп. Просто в одной утверждение, что элементы группы коммутируют истинно, а в другой то же самое утверждение ложно. Это утверждение независимо от аксиом группы. Его нельзя ни доказать ни опровергнуть и вы можете допустить его истинность, а можете и его ложность.

Примерно то же самое происходит в теории множеств. Недоказуемое по Геделю высказывание можно принять за истинность и получить непротиворечивую теорию, а можно принять за ложь и тоже получить непротиворечивую теорию.

Отличие от групп в том, что на основе теории множеств пытаются строить всю математику. И получается что можно получать разные математики с противоположными утверждениями.

На практике довольно сложно доказать недоказуемость высказывания в теории множеств. Надо доказать, что математика получается непротиворечивой при верности этого высказывания, и также является непротиворечивой когда то же самое утверждение считается ложным. Но Пол Коэн развил технику, называемую forcing, которая позволяет это сделать. За нее он получил Филдсовскую медаль.

Пожалуй, самым известным из недоказуемых утверждений является континуум-гипотеза. Она говорит, что между счетной бесконечностью целых чисел и несчетной бесконечностью действительных чисел не существует никаких других промежуточных бесконечностей. Георг Кантор безуспешно пытался ее доказать. Считается, что это внесло свой вклад в появлении у него психических проблем.

Курт Гедель доказал, что теория множеств в аксиоматике Цермело — Френкеля совместно с истинностью континуум-гипотезы является непротиворечивой теорией.

Однако Пол Коэн в 1963 доказал, что что теория множеств в аксиоматике Цермело — Френкеля совместно с отрицанием континуум-гипотезы также непротиворечива.

То есть можно построить математику в которой между бесконечностью целых чисел и бесконечностью действительных нет промежуточных бесконечностей. А можно построить математику где они есть. Причем в этот промежуток можно поместить бесконечность разных бесконечностей. И теория тоже будет непротиворечиворечивой.

Про континуум-гипотезу конечно можно сказать, что она касается бесконечностей и на практике нам все равно сколько бесконечностей можно запихнуть между двумя другими бесконечностями.

Однако есть и более интуитивные недоказуемые утверждения, например, аксиома выбора. Она по-сути утверждает, что из каждого непустого множества можно выбрать по одному элементу. Сторонники платоновской философии реализма могут сказать, что эта аксиома тривиально верна. Ее верность просто очевидна. Математическая интуиция говорит нам о ее верности. И современная стандартная аксиоматика теории множеств ZFC включает в себя аксиому выбора.

Однако Пол Коэн доказал, что и математика где аксиома выбора неверна также является непротиворечивой.

Антиреалисты и номиналисты могут сказать, что это людям аксиома выбора интуитивна, а скажем плазмоидам Майкла Атьи, живущим на планете газового гиганта, интуитивно утверждение, что аксиома выбора неверна.

В математике даже есть понятие абсолютности: формула называется абсолютной, если она верна в каждой из моделей определенного класса. Но как оказывается многие утверждения не абсолютны. Например, понятие счетности неабсолютно.

Вот интересный пост Скота Ааронсона на эту тему. Ааронсон известный computer scientist, поэтому верит, что мы живем в матрице и все пытается объяснить в понятиях вычислений.

Модели в теории множеств он сравнивает с воображаемыми мирами по типу фильма Матрица.

Say what? The models are mistaken about something as basic as their own size, about how many sets they have? Yes. The models will be like The Matrix (the movie, not the mathematical object), or The Truman Show. They’re self-contained little universes whose inhabitants can never discover that they’re living a lie—that they’re missing sets that we, from the outside, know to exist. The poor denizens of the Matrix will never even be able to learn that their universe—what they mistakenly think of as the universe—is secretly countable! And no Morpheus will ever arrive to enlighten them, although—and this is crucial to Cohen’s proof in particular—the inhabitants will be able to reason more-or-less intelligibly about what would happen if a Morpheus did arrive.

Incidentally, once we realize that it’s possible to build self-consistent yet “fake” mathematical universes, we can ask the question that, incredibly, the Matrix movies never ask. Namely, how do we know that our own, larger universe isn’t similarly a lie? The answer is that we don’t! As an example—I hope you’re sitting down for this—even though Cantor proved that there are uncountably many real numbers, that only means there are uncountably many reals for us. We can’t rule out the possibly that God, looking down on our universe, would see countably many reals.

Видно, что Скот придерживается платоновской философии реализма. Он говорит, что несмотря на то, что непротиворечивых математик можно придумать много, человек посредством своей математической интуиции может заглянуть в платоновский мир идей и определить какая из них верная. Ну и как сторонник теории симуляции вселенной, он применяет к ней все эти идеи из теории множеств. Он говорит, что у тех, кто моделирует наш мир может быть другая математика, но она все равно объективно существует в платоновском мире идей. И мы даже можем заглянуть в эту другую математику тех, кто создал Матрицу.

Однако существование непротиворечивых математик можно объяснить и с позиции номинализма, не прибегая к гипотезе, что мы живем в Матрице. Если вся математика — это просто изобретение человеческого ума, то нет ничего удивительного, что существуют другие математики. Сама математика относительна. Относительна относительно человека.