Achtung! У вас проблемы в математике

На самом деле это у нас у всех эти проблемы уже лет 150, и они фундаментальные. Но всем похуй это никому не мешает, как ни странно. Сейчас я про них вкратце расскажу. Кто знает, тот и так знает, но кому-то может быть новым и интересным.

Будет 9 постов.

Начнём с подоплёки. Всё началось с работ Кантора по новому направлению – теории множеств. С введения в теорию множеств по Кантору сейчас начинаются занятия по матану в универе, теперь это база для бесконечных последовательностей, потом рядов, потом… Но так было не всегда. Когда его работы появились, произошёл существенный раскол среди величайших математиков того времени.

С одной стороны, необходимость такого формализма была, так как дифференциальное и интегральное исчисление уже было развито, но понятие предела всё ещё было недостаточно хорошо определено. Кантор показал, например, что есть счётные и несчётные множества, и бесконечности бывают разные. Это прекрасно, но вытекающие теоремы вели к ряду парадоксов и вообще бесконечности по Кантору – это бесовские штучки. Изначально «нефанатами» теории множеств были выдающиеся математики, такие как Леопольд Кронекер или Анри Пуанкаре.

В Proceedings of the Fourth International Congress of Mathematicians, Rome, 1908, 167-182; the Bulletin des sciences mathématiques, (ser. 2), vol. 32, 1908, 168-190 есть ссылка на цитату Пуанкаре из его эссе L'Avenir des Mathématiques

Цитата

Но случилось так, что мы столкнулись с некоторыми парадоксами, некоторыми кажущимися противоречиями, которые порадовали бы Зенона из Элеи и школу Мегары ..... Я, со своей стороны, думаю, и не только я, что важно никогда не вводить объекты, которые нельзя полностью определить в ограниченном количестве слов.

Со временем, начиная с 1880-х (когда Пуанкаре познакомился с теорией Кантора и ввёл термин Mengenlehre - теория множеств) его мнение изменилось, и к 1885 он уже воспринимал её с энтузиазмом. В то же время, он занял, как считал, прагматическую, психологическую позицию в защиту математической интуиции и не допускал существования какой-либо мощности бесконечного вполне упорядоченного множества, отличной от мощности множества натуральных чисел (ℵ0). Это была сторона интуиционистов.

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

«Никто не сможет изгнать нас из рая, который создал Кантор!» - писал Д.Гильберт. Он с большим энтузиазмом хотел создать в математике новую надёжную систему доказательств, которая разрешила бы накопленные к концу 19 века проблемы. То есть, символьный логический язык со строгим набором операций над этими символами. В целом, идея была ещё из Древней Греции, когда из аксиом (утверждения, принятые за истину) научились посредством логических рассуждений выводить новые истинные утверждения. На языке, который хотел создать Гильберт, можно было бы перевести все логические и математические утверждения.

И в 1913 году Альфред Уайтхед и Бертран Рассел написали фундаментальный трёхтомник PRINCIPIA MATHEMATICA (Основания математики). Это титанический труд, читать его – вывих мозга (поверьте, даже если вы учили матан на мехмате или аналогичном факультете). В ней на 768 странице (стр. 88 второго тома) вот в таком виде доказывается, что 1+1=2. Далее идёт математический юмор: «Приведённое выше предложение иногда бывает полезным». Ха-ха.

Также была разработана аксиоматическая система теория множеств Цермело-Френкеля. Гёдель (о котором будет позже) как-то написал:

Цитата

Эти две системы настолько развиты, что в них можно формализовать все методы доказательства, которые в настоящее время используются в математике, то есть свести эти методы доказательства к нескольким аксиомам и правилам дедукции.

И потом он доказал, что это кажущееся истинным утверждение ложно. Собственно, мы пришли к сути.

Дэвид Гильберт, когда шёл на большую конференцию в 1930, он думал, правильная формальная математика обладает всеми тремя свойствами:
- Полнота математики. То есть, возможность доказать любое истинное утверждение.
- Непротиворечивость математики. То есть, не может ли быть так, что ты можешь доказать одновременно «X истинно» и «не-X тоже истинно»? Правильная математика такого допускать не должна.
- Разрешимость математики. То есть, существует алгоритм, который тебе скажет, следует ли некое интересующее тебя утверждение из аксиом.

Гильберт в своей речи на этой конференции провозгласил слоган «Мы должны знать – и мы будем знать».

Но уже за день до выступления Д.Гильберта логик Курт Гёдель докладывал, что он нашёл ответ на первый вопрос о полноте. И ответ был «нет»: «полная формальная система математики невозможна». В следующем 1931 году вышла его работа «О формально неразрешимых предложениях Principia Mathematica и связанных с ними систем I» в Monatshefte für Mathematik und Physik.

Гёдель ввёл свою систему нотации. Он сначала пронумеровал все цифры, базовые математические операции, знаки и т.п. из Principia Mathematica, таким образом что можно в этой системе записать уравнения, логические утверждения и т.п. Затем, посредством введённой операции «арифметизации» он получает так называемые гёделевы номера (детальнее можно посмотреть в оригинальной работе или в Мендельсон Э. Введение в математическую логику. — М.: «Наука», 1971. — 320 с.)

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

Бесконечное количество этих гёделевых номеров содержит как истинные, так и ложные утверждения, и их можно свести к аксиомам.

Вся эта механика с гёделевыми номерами (поистине гигантскими даже для простых утверждений) понадобилась для того, чтобы поработать с номером, который соответствует утверждению «Нет доказательства с числом Гёделя g». А фокус в том, что этот номер и равен g.

Если это утверждение ложно, и доказательство есть, то мы докажем, что доказательства нет. Это бы означало противоречивость системы. Если же это утверждение истинно, то тогда эта математическая система содержит истинное утверждение, для которого нет доказательства. То есть, такая система неполна. Теорема Гёделя о неполноте показала, что истинность и доказуемость – не одно и то же.

Что насчёт непротиворечивости математики? Вторая теорема Гёделя говорит о том, что любая непротиворечивая система не способна доказать свою непротиворечивость. Лучшее, что мы можем получить – это непротиворечивая, но неполная система. При этом она не может доказать свою непротиворечивость. То есть, теоретически может возникнуть парадокс, который покажет, что вроде бы непротиворечивая система, оказывается, была самопротиворечивой. Ещё не плачем? Тогда идём дальше.

Вопрос о разрешимости, то есть существует ли алгоритм, который тебе скажет, следует ли некое интересующее тебя утверждение из аксиом или нет?

В 1936 году Алан Тьюринг создал машину Тьюринга (примерно в то же время Алонзо Чёрч ввёл λ-исчисление и понятие λ-определимых функций, а потом ими совместно был сформулирован Тезис Чёрча-Тьюринга об эквивалентности машины Тьюринга и λ-определимых функций).

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

Это применимо и к другим областям. Например, в 2015 году математики издали работу, в котором доказано утверждение «Даже идеального, полного описания микроскопических взаимодействий между частицами некоторого материала не всегда достаточно для вывода их макроскопических свойств».

Ну и ещё одним применением является то, что все современные компьютеры и выполняемые на них программы, любой мощности и сложности, являются всего лишь реализациями машины Тьюринга. А значит, её ограничения, пределы возможностей, переносятся и на всю вычислимую технику.

Что поделать, мы никогда не сможем знать всё наверняка, и это было доказано. Мечта Гильберта не сбылась. Но с этим можно жить – мышление людей выходит за рамки логики первого порядка, и в целом за пределы возможностей вычислимых машин. Хотя в некоторых задачах они, конечно, работают быстрее и чётче. Такие дела.

ВСЁ.

Скрытый текст

Общая канва рассказа взята из видео Math's Fundamental Flaw - что-то выброшено, что-то добавлено.