Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

Основания математики I: Как работают доказательства.

Исходя из школьных знаний часто кажется, что математическое доказательство — это что-то нечёткое, написанное словами и проверяемое бородатыми дядями. И доказательство считается верным только если бородатые дяди не нашли ошибки. Какой-то негодный субъективный критерий.

На самом же деле доказательство легко формализуется. Впервые это сделали Гильберт и Фреге, но у них получилось не очень элегантно. Много лет спустя, в 1969 году было открыто соответствие Карри-Говарда (Curry-Howard), которое поставило всё на место.

Для того, чтобы понять, как формализуется доказательство, вначале надо понять, как формализуются высказывания — то, что мы доказываем и то, из чего исходим в доказательстве.

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

Кроме языка теорию ещё определяет набор аксиом. Это набор высказываний, которые мы именуем какими-нибудь буквами типа w и q. Мы принимаем их правильными. Из них будут исходить наши доказательства. Это не значит, что мы "в них верим" или ещё чего-то в этом роде. Это просто посылки одной отдельно взятой теории, которая может ничего общего не иметь с реальным миром.

Ну вот с высказываниями разобрались, теперь перейдём к доказательствам.
Есть такая штука — называется лямбда-исчисление. Это просто способ записывать композицию функций. Если у нас есть на руках функции f и g, мы можем сделать функцию, которая вначале применяет g, а потом f. Записывается это, например, так:
h = ( x -> f(g(x)) )

Т.е. h = такая штука, которая берёт Х и выдаёт f(g(X)).

Если у функций f и g задан тип, мы можем вычислить тип этой вот новой функции h.

Дык вот выясняется, что мы можем считать наши аксиомы w и q "функциями", у которых типом является их высказывание. А любое доказательство мы можем записать как композицию элементарных аксиом. А ещё мы можем вычислить "тип" получившейся композиции и таким образом узнать, что же мы доказали. Если получившееся высказывание совпало с тем, которое мы хотели — эврика и ура. Доказательство верно. Проверялка доказательств без помощи всяких бородатых дяденек — это программа, занимающия на Perl'е примерно 20 строк. Её можно написать на коленке за полдня.

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

Следующая серия: http://akuklev.livejournal.com/605005.html
Subscribe

  • (no subject)

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

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment