диалектика...

(http://www.youtube.com/watch?v=Da9IkzgoX28)

— Будапешт — столица какой европейской страны?
— Дурацкий это какой-то вопрос!
— Ну, вероятно, возможно…
— Да… но… ведь Европа — это страна! Будаш… Будапешт. Никогда такого не слышала!
— Правильный ответ: Венгрия!
— Чего? Я про Турцию слышала, но Венгрия?! Никогда о такой не слышала!

Интересно задуматься, как часто мы записываем вопросы в «дурацкие». Я и сам этим грешу немало. Пусть эта блондинка с апломбом нам с вами вспомнится, если постановка какого-нибудь вопроса поначалу вдруг покажется не очень умной. Берегите голову.

Проходила тут мимо к/т "Мир" (центр Минска, на проспекте) и всерьез задумалась - а не пойти ли мне в оформители афиш??? По-моему, получится не хуже... заодно и руку набью, начну еще и песцов рисовать :) ( Read more... )

XI. Математические последствия

Хорошо или плохо для математики открытие Геделя? С одной стороны, надежды математиков на самообоснованность математики, на существование единственной верной математической системы, которую можно «открывать», но не «выдумывать», испарились. Можно подумать, что это плохо. С другой же стороны, оказалось, что математика не сводится к механической процедуре доказательств, что в математике всегда останется место для нового не автоматизированного творчества. Проще говоря — математика не заканчивается, как она бы завершилась с изобретением полностью механизированной математической системы. Математики без работы не останутся, и их, в отличие от рабочих на сборочном конвейере, не заменят роботы. И это как будто бы хорошо.

Диалектическую сущность открытия Геделя хорошо сформулировал К. Подниекс в [2]:

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

Итак, с философской точки зрения, теорема Геделя радикально поменяла математические воззрения на основания математики.Математика не может быть одновременно полной и непротиворечивой. Противоречие — много худший дефект теории, чем неполнота: она сводит на нет всю доказательную силу теории. Поэтому математика, какой мы ее разрабатываем, не должна быть противоречивой. Если мы придем к противоречию, нам придется отступить на несколько шагов назад, чтобы изъять из системы те положения, аксиомы, которые к этому противоречию привели. Наша непротиворечивая математика всегда будет неполной. Но каковы же практические — то есть, важные для ежедневной математической работы — последствия этой неполноты?

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

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

Часто бывает, что математика отставляет недоказанность некоторых утверждений в сторону, и развивается, будто они были доказаны. Так же ведут себя и естественные науки. Все, что мы знаем в физике, так же «доказано» наблюдениями и сведением их в теории. В физике нет аксиом, есть только наблюдения. Математика, разумеется, предпочитает аксиомы, но в некоторых случаях и принимает — предварительно, в силу своей строгости — недоказанные утверждения, от которых можно отталкиваться и двигаться вперед.

В число таких недоказанных утверждений входят не только «курьезы» — интересные теоремы, из утверждений которых не делается никаких дальнейших выводов, к каким, например, относится Великая теорема Ферма, доказанная всего несколько лет назад. Существуют гораздо более «серьезные» теоремы, с помощью которых математики доказывают новые теоремы. В их число входит гипотеза Римана.

Гипотеза Римана говорит о значениях нулей комплексной дзета-функции Римана. Разъяснение этой гипотезы лежит далеко за пределами нашего повествования, но нам, безусловно, интересно, что происходит в математике вокруг нее. Доказательства этой гипотезы не найдено уже 150 лет. Говорят, будто, когда у Гильберта спросили, что он сделает, если заснет и проснется через 500 лет, он ответил, что первый вопрос, который он задаст, будет о том, была ли доказана гипотеза Римана. Дело в том, что гипотеза Римана используется во многих доказательствах, как если бы это была доказанная теорема. В этом ее отличие от теоремы Ферма, которая была и остается просто интересным фактом о числах, но не используется в доказательствах так широко. Институт Клэя назначил приз в 1 миллион долларов США за доказательство Римановой гипотезы, потому что ее доказательство чрезвычайно важно для арифметики, в частности, в области факторизации чисел на простые сомножители. Выходит, что и криптостойкость современных шифров зависит от верности предположения Римана, и, таким образом, она оказывает влияние на материальный мир через ежедневные компьютерные операции в нем.

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

Что будет с математикой, если выяснится, что гипотезу Римана нельзя доказать в существующих даже самых сильнх, самых внешних математических теориях? Конечно, можно сделать ее утверждение аксиомой, просто объявить, что, раз она недоказуема, то мы будем полагать ее истинной по положению. Но, кроме этого, возможен и другой путь. Мы могли бы объявить гипотезу ложной, и считать ее ложность аксиомой¹⁵. В принципе, это не вызвало бы в математике противоречий, но, тем не менее, такое положение шло бы вразрез с уже накопленным математическим знанием. Здесь опять проявляется некоторое сходство математики и естественных наук — сходство, возникающее от того, что думают над теориями в этих науках люди, пользуясь родственными мыслительными системами. Мы наблюдаем, что гипотеза Римана верна для огромного количества случаев, и предполагаем — очень уверенно предполагаем! — что она верна всегда в построенной нами системе математики. Поэтому, если нам случится полагать ее аксиомой, расширяющей эту систему, то естественным будет положить аксиомой ее утверждение, а не его отрицание.

Отвлечение наше на гипотезу Римана было не случайным. На этом примере будет интересно рассмотреть положения о том, что сознанию человека будто бы доступна «истина», не достижимая вычислительным алгоритмом.

Продолжение следует.

__________________________________
⇧ 15. Например, так: существует хотя бы один нетривиальный нуль дзета-функции, вещественная часть которого отлична от 1/2.

...Мы всегда ездили на ЗМ дружной веселой компанией - я, Гена (nheg), Наташа, Виталик и Антон (stiil).
В 2008 году я сдуру пришла на банкет в вечернем платье и на каблуках :) Как говорится, не бывает страшных женщин, а олдевки на конвенте было много, и уже через 15 минут я превратилась в переходящее знамя, а там и костыль для танцев. К концу второго часа я взвыла и, отыскав столик друзей, вцепилась в Антона мертвой хваткой.
- Антон, пошли со мной потанцуем! Только медленно и печально, и чур Я на тебе буду висеть, а то меня уже ноги не держат!!!
К счастью, Антон оказался настоящим джентельменом и даму в беде не бросил.
- Нет, - сказал он к концу танца. - Это ужас какой-то! Меня пригласила такая прекрасная женщина, а я не умею танцевать!
- Да ладно, - попыталась утешить его прекрасная женщина, - я тоже не умею! Разве это важно?
- Нет, - продолжал сокрушаться друг, - так неправильно! Надо срочно учиться танцевать. Все, Олька, я пойду на курсы бальных танцев и в следующем году обязательно оттанцую тебя как положено!

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



Я не представляю, как мы поедем на ЗМ без него.

Чтоб я так жил! — ita ego vivam! (cf. Cic. Att. V, 15)

Чтоб у нас все было, а нам за это ничего не было! — haberemus totum at ex eo hoc ne habemus! (cf. Verg. A. 12, 296)

Еще попереводим?

andrei_koval: Посидим, все дела… — sedeamus, opera omnia…

Два дня накладывала крысам био-йогурт из одной баночки.
Сегодня заглянула в нее и решила что, пожалуй, уже не стоит давать - потравятся.
И доела.

...кто там останется на земле после ядерного взрыва? :)))

Вот скажите мне, в чем правда: отпустить положительным героям после допроса злого разбойника, чтоб он продолжал резать народишко и заниматься похищением людей, или убить, запачкав свою карму? :(
Читаю Петр Первый, жутко завидую Толстому. Проворовался купец? На кол сволочь! Убила мужа? В землю живьем закопать! Заговор стрельцы строили? На крюках на городских стенах развешать! Ни одного положительного героя. Все - люди.
Три мушкетера и то Миледи убиенной оскоромились. Да и по тексту весьма... шалили.

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

upd: ВОТ! большинство комментов: а давайте он как бы нечаянно сам умрет?! типа и ручки не пачкать, и зло наказать... а фигушки так в жизни :(

VIII. Машина доказательств

ФСС элементарной арифметики (ФСЭА), как мы уже знаем, производит строки, интерпретируемые как утверждения арифметики. Она содержит аксиомы, начальные верные строки, и выводит новые строки — теоремы. Мы не будем рассматривать конкретные аксиомы⁸ и правила вывода новых строк из уже выведенных; нам достаточно помнить, что они заданы. В алфавит ФСЭА входят символы для кодирования чисел и переменных, операции + и ×, сравнение =, скобки, кванторы существования E и всеобщности A (мне придется обозначить их латинскими буквами из-за типографских ограничений), и логическое отрицание ~. Числа кодируются в такой же «единичной» системе, какую мы уже рассматривали, количеством «звездочек». Так же кодируются и переменные, только начинаются они со специального символа переменной x: вместо x, y, z, a, b система выдает x•, x••, x••• и т. д. В примерах ниже мы, однако, будем записывать числа в десятичной записи, а переменные буквами.

Примеры утверждений, которые выводит ФСЭА:

Ex:x×2=6

Здесь говорится, что число 6 четно (найдется такое число x, что 2×x=6)

~Ex:Ey:(x+1)×(y+1)=13

13 простое число: не существует таких x и y, что (x+1)×(y+1)=13. Прибавление единицы требуется, чтобы каждый сомножитель был больше 2⁹.

Ax:Ea:~Eb:Ec:(x+a)=(b+1)×(c+1)

Здесь утверждается, что существует бесконечно много простых чисел. Следует читать это так: для любого x найдется a такое, что не существует таких b и c, чтобы равенство (x+a)=(b+1)×(c+1) выполнялось. Иными словами, для каждого x найдется такое a, что (x+a) будет простым числом. Поскольку a>0, то и x+a>x: какое число x ни возьми, найдется простое число, еще большее.

В образовании смысла строк мы следуем правилам, которые мы же сами установили для их интерпретации. Например, «~» мы читаем «неверно, что», A как «для всех», E как «для одного или более», «:» как «верно следующее:», и так далее. Тогда утверждения, выводимые ФСЭА, становятся теоремами. Являются ли они «истинными»? Здесь нужно задуматься о понятии истинности.

Мы изначально полагаем аксиомы истинными, верными утверждениями. Их запись в виде строк ФСЭА интерпретируется именно так, как мы того хотим, с тем смыслом, которые мы в них закладывали, когда придумывали эти строки¹⁰. Являются ли истинными в этом смысле и теоремы? Ровно настолько, насколько мы можем доверять формальному механизму вывода, аппарату формальных систем.

На поверхности кажется, что этот механизм работает надежно. Можно увидеть, как выводятся приведенные выше утверждения, которые мы понимаем как верные в арифметике. Но ведь теорем, которые производит ФСЭА, бесконечно много. Поэтому мы должны поставить вопрос «доверия» к нашей механике вывода. В ФСС сложения чисел доказательство было довольно простым, однако, ФСЭА намного сложнее, и ее «правильность» отнюдь не очевидна.

Вопросы касательно ФСЭА, которыми мы зададимся, следующие. Во-первых, нас интересует, все ли возможные теоремы арифметики выведет наша машина? Например, будет ли среди ее строк доказательство Великой теоремы Ферма? Предположения Гольдбаха? Свойство, которое нас интересует, мы назовем полнотой системы: система полна, если она выводит, в интерпретации смысла, все истинные утверждения в некоей области.

Второй, еще более важный вопрос, который нас волнует: не произойдет ли так, что два утверждения, полученных ФСЭА, будут противоречить одно другому? Например, одним путем мы получим утверждение, что предположение Гольдбаха истинно, а другим — что оно ложно. Такое нарушение будет фатальным для всей системы арифметики: из противоречия можно вывести все, что угодно! Это легко показывается в формальной логике. Из такого противоречия следует, что 0=1, что 2×2=5, что простых чисел не существует, что их существует конечное количество, что количество простых чисел бесконечно — все, что пожелаете. Противоречия в выведенных теоремах ни в коем случае быть не должно. Свойство системы не выдавать противоречивых (в интерпретации смысла) утверждений назовем непротиворечивостью.

Является ли элементарная арифметика полной и непротиворечивой теорией? Над этим вопросом работали великие математики начала XX в. Попытка вывести самообоснованность теории множеств тогда потерпела неудачу¹¹. В ответ на это Давид Гильберт сформулировал в начале 20-х гг. программу по поиску способа вывода всех математических утверждений из аксиом путем механической вычислительной процедуры. Формулировка требований, заданных Гильбертом к аксиомам и процедурам математики, такова: требуется найти (а) процедуру, которая бы выводила все без исключения истинные математические утверждения, и только истинные, из заданного однажды набора аксиом; (б) самый набор этих аксиом и (в) алгоритм доказательства любого наперед заданного утверждения, чтобы определить за конечное время, возможно ли вывести это утверждение из аксиом (в таком случае, оно истинно) или нет (и тогда оно ложно).

Таким образом, Гильберт сформулировал задачу поиска, в наших терминах, полной и непротиворечивой формальной системы арифметики, и дополнил ее требованием конструктивной вычислимости ¹²принадлежности лексически верной строки множеству синтаксически верных строк.

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

IX. Бета-код Геделя

Рассуждение Геделя основано на арифметическом кодировании алфавита, строк и правил ФС. В самом деле, мы можем закодировать алфавит ФС числами. Когда мы это сделаем, правила переписывания строк ФС можно записать в виде арифметических операций над числами. О любом числе можно задать вопрос, является ли это число кодом лексически верной строки в данной ФС. Если ответ на него положительный, далее можно спросить, является ли это число также и кодом синтаксически верной строки. Если да — то мы имеем дело, на семантическом уровне, с кодом теоремы арифметики. Таким образом, выходит, что среди чисел есть подмножество кодов теорем арифметики. Множество всех остальных чисел можно назвать множеством не-теорем арифметики (либо они лексически недопустимы, либо не выводимы системой). Будем называть числа вычислимыми формальной системой, если они выводимы нашей закодированной числами ФС.

Для примера, закодируем нашу первую систему ХИХИ в виде чисел: заменим Х на 1, И на 2, А на 3¹³. Начальная верная строка ХИ тогда первращается в число 12. Теперь перепишем на языке чисел правила системы.

1. К любому числу, заканчивающемуся на 2, можно дописать в конец 3. Математически это можно выразить так: если n вычислимое число, и остаток от деления его на 10 равен 2, то 10×n+3 тоже вычислимое число.

2. Любую «подстроку», следующую за 1, можно «удвоить». Операции «взятия подстроки» и «удвоения», разумеется, следует записать арифметически. Пусть наше число содержит в середине или в начале 1 (пример 23132). Часть, заканчивающуюся 1 (231 в примере) запишем как m×10+1, где m≥0 (в нашем примере m=23). Чтобы приписать к этому числу «хвост» (32), умножим его на 10ⁿ, где n — длина «хвоста» (у нас n=2, 10ⁿ=10²=100): (m×10+1)×10ⁿ, в нашем примере это будет 23100, а затем просто прибавим «хвост», то есть запишем формулу как (m×10+1)×10ⁿ+j, где j обозначает «хвост» (у нас j=32). Чтобы он поместился в отведенное ему разрядное место, мы должны ввести ограничение j<10ⁿ. «Удвоить хвост» можно, еще раз умножив результат на 10ⁿ и прибавив j. Таким образом, правило (2) можно сформулировать так:

Если (m×10+1)×10ⁿ+j, где j<10ⁿ, вычислимое число, то и (m×10+1)×10ⁿ+j)×10ⁿ+j вычислимое число.

Запись правил (3) и (4) в арифметической форме оставим как упражнение читателю.

Все это выглядит чрезвычайно запутанным и искусственным, но нас сейчас не интересует сложность и «неинтересность» этого вывода. Самое главное здесь, что путем формального, механического преобразования можно перейти от записи правил операций над строками к записи правил в виде операций над их кодами, числами. А как только мы переведем описание ФС на язык арифметики, мы сможем сформулировать и задачи, ставящие вопросы об этой ФС, на том же языке арифметики. Например, задача о выводимости ХА переформулируется в таком виде: входит ли число 13 во множество чисел, вычисляемых данной, описанной в виде арифметических действий, ФС?

X. Теоремы Геделя

Ничто не препятствует нам распространить рассуждения о кодах ФС на самое арифметику, вернее, ее формальную систему — ФСЭА. Переписав ее правила в виде арифметических алгоритмов, мы закодируем каждое утверждение, получаемое ФСЭА, натуральным числом.

Что интересного произойдет, когда мы сделаем это? ФСЭА достаточно мощна, чтобы порождать язык арифметики. В тоже самое время, мы переписали ее правила на тот же самый язык! Иными словами, в таком выражении ФСЭА формулирует утверждения о себе. Например, мы можем спросить, входит ли число X во множество чисел-кодов утверждений ФСЭА? Тем самым, мы задаем вопрос, является ли число Х кодом верного утверждения, то есть теоремы, арифметики. Понятно, что число мы можем теперь рассматривать двояко: как собственно число, и как код утверждения о числах.

Гедель доказывает, что возможно (и показывает, как) сконструировать в ФСЭА утверждение «Число G не входит во множество кодов теорем, выводимых ФСЭА», таким образом, чтобы код этого утверждения в точности совпал с самим числом G¹⁴. Каковы последствия существования такого числа?

Попробуем «спросить» арифметику об истинности этого утверждения. Верно ли на самом деле, что число G не входит во множество кодов теорем, выводимых ФСЭА?

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

Предположим теперь, что число G, код утверждения о том, что G не является кодом теоремы, и на самом деле не является кодом теоремы. В таком случае, противоречие снимается. Однако, в этом случае арифметика оказывается неполной! У нас есть верное утверждение (о том, что G не является кодом теоремы), которое, хоть и верное, но не входит в число теорем арифметики. Получается тогда, что арифметика «не знает» всех верных утверждений о натуральных числах.

Это рассуждение и является основным в первой теореме Геделя о неполноте. Формулировка этой теоремы была в дальнейшем значительно усилена Россером; когда говорят о теореме Геделя, имеют в виду обычно первую теорему о неполноте арифметики в формулировке Россера.

Обратите внимание, что такое замыкание нашего рассуждения возможно не в любой ФС. Например, утверждения системы ХИХИ не являются таковыми о натуральных числах; строку системы ХИХИ нельзя интерпретировать как «x не входит во множество Z», ведь у нас нет отображения этих строк на утверждения о числах. Кроме того, она не описывает и системы кодирования утверждений на языке, который она производит. Таким образом, ФС, попадающая под обсуждение теоремы Геделя, должна быть достаточно мощна, чтобы выражать, в некоей интерпретации смысла, действия элементарной арифметики. Системы, для которых такая интерпретация в принципе возможна, мы, вслед за Подниексом [2] назовем фундаментальными.

Давайте теперь проговорим суть вывода теоремы Геделя-Россера:

Фундаментальная система теорем, выводимых формальной системой, не может быть одновременно полной и непротиворечивой.

Этот вывод остается верным применительно к любой фундаментальной системе (то есть, с различными наборами аксиом и правил), не только к конкретной ФСЭА. Например, вполне естественно включить G в число аксиом нашей системы. Раз уж мы знаем, что утверждение G истинно, давайте добавим его к списку аксиом нашей ФСЭА. К сожалению, это не снимает противоречия. Сделав это, мы получим другую формальную систему, ФСЭА′, в которой, по теореме Геделя, есть свое геделево число G′. Можно и его добавить к аксиомам ФСЭА′ — мы получим новую систему ФСЭА′′, но и в ней будет свое геделево число G′′ — и так далее до бесконечности.

Разрешения у этой проблемы нет: арифметика не может быть полностью выражена набором аксиом и механических правил вывода, то есть и арифметика, как и теория множеств, не обосновывает сама себя. Открытие Геделя предопределило крах программы Гильберта по поиску самообоснованной, самосовершенной, заключенной самой в себе арифметики — и математики вообще.

Здесь можно увидеть некоторое сходство с геометрией. Изменяя пятый Евклидов постулат о том, что через заданную точку проходит ровно одна прямая, параллельная заданной прямой, мы получим разные непротиворечивые системы геометрии. Существенная разница в том, что геометрия, в отличие от арифметики, не порождает языка, на котором можно выразить аксиомы и правила геометрии. Тем не менее, общая картина арифметического состояния дел нам ясна: имеются некоторые истинные, в смысле более сложных, «внешних» теорий, утверждения, которые не могут быть ни доказаны, ни опровергнуты в арифметике. В то же время, эти внешние теории страдают тем же недостатком: в них имеются свои геделевы утверждения — и так, опять же, до бесконечности. Единой совершенной теории арифметики не существует. Есть более сильные фундаментальные теории и более слабые — например, аксиоматическая теория множеств ZFC сильнее аксиоматической арифметики Пеано в том смысле, что первая доказывает утверждения, недоказуемые в последней, но «абсолютной» фундаментальной теории все-таки существовать не может,

Стоит, для полноты картины, привести здесь, без доказательства или рассуждения, формулировку второй теоремы Геделя о неполноте арифметики:

Если фундаментальная система теорем арифметики, выводимая формальной системой, содержит доказательство собственной полноты, то эта система противоречива.

Далее нам следует порассуждать о последствиях результатов, полученных Геделем, для математики, и лишь затем мы рассмотрим различные аргументы о применимости этих результатов к моделям и сущности сознания и мышления.

Продолжение следует.
__________________________________
⇧ 8. Множество аксиом ЭА счетно-бесконечно, они тоже выводятся правилами.

⇧ 9. В ЭА рассматриваются натуральные числа, поэтому переменная может принимать значения 1, 2, 3 и так далее. Если x переменная, то (x+1) будет иметь значения 2, 3, 4 — иными словами, 2 или больше.

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

⇧ 11. Парадокс, обнаруженный Бертраном Расселом в теории множеств, популярно сформулирован в википедии (англ.) так. Введем признак «нормальности»: нормальное множество не является своим собственным подмножеством. Например, множество всех квадратов нормально, потому что оно само не есть квадрат. Его дополнительное множество, множество всех неквадратов, не нормально, потому что оно само не квадрат и, следовательно, должно включать и себя. Теперь возьмем множество всех нормальных множеств, и зададимся вопросом, нормально оно или нет? Это парадокс. Если мы предположим, что оно нормально, то оно входит само в себя, и, следовательно, не нормально. Если предположить, что оно не нормально, то его не будет среди всех нормальных множеств, и, значит, оно не подмножество себя — то есть, нормально. Противоречие возникает при любом предположении.

⇧ 12. Конструктивной в математическом смысле: требуется не только доказать существование алгоритма, доказывающего теоремы, но и отыскать сам этот алгоритм.

⇧ 13. Бета-код Геделя основан на взаимно-простых числах и формулируется сложнее, но делает дальнейшие доказательства более эффективными. Для наших качественных рассуждений, однако, конкретный способ кодирования не важен.

⇧ 14. Замечательное неформальное описание этого вывода дается в [1], глл. XIII и XIV, а формальный вывод в [2].

я оказалась самой ленивой, домой пешком не пошла, прошлась недалеко к друзьям и осела им на шею:)
вот думаю, если завтра будет также - идти на работу?..

Как получить свой лотерейный билет и выиграть подарки для себя и друзей?

концепция поменялась, домой иду, но пешком!

Ну-да, ну-да - и опять восемнадцать. И опять на конференции - даже прочитать надо бегать на переменках. Спасибо огромное всем! Как закончится немного бардак, так сразу повезу всех снова в Рим. Всех люблю - ваша Я.

P.S. Когда мне было лет шесть, а моей маме снова двадцать один я очень расстроилась - я всё подсчитала и, со слезами на глазах, пожаловалась на судьбу - "Вот когда мама была такая как я, у неё уже был мой брат.... А у меня, до сих пор, ещё никого нет!". Правда, меня достаточно быстро утешили, спросив хотела ли бы я такого - поскольку мы часто ругались, моё утешение наступило немедленно....

по всей видимости, ночую на работе

Я тут занималась генеральной уборкой своего стратегического запасника. У меня традиция такая, предновогодняя:-)).
Каждый раз устраивать баню моим старым кулинарным журналам. Последние года три, всё заканчивалась выбрасыванием в мусорку единичных экземпляров, с выдергиванием нужных рецептов, а потом, как правило, меня душила зеленая подруга, и я опять задвигала коробки подальше с чувством выполненного долга. Но в этом году попарилась я на славу!)). Три коробки журналов с большими почестями отправились в вечное странствие. И что больше всего удивило меня ,то что выдирать то там было и нечего)
Вот что нашла интересного из очень-очень старого, так это вот рецепт необычного чизкейка. Его и приготовила и даже нашла время снять, и даже …еще раз снять, в новой интерпретации, по-моему, очень интересной;-)

( сделаем дело) )

Как известно, с высокоценными украинскими щурами мне не обломилось :)
Но поскольку желание завести крысу (а лучше трех :)) было горячо и непреодолимо, я с горя стукнулась в аську к знакомой по минской выставке, у которой жило несколько крыс. Вообще с клубами любителей животных я стараюсь не связываться ( см. Тайное Общество Памяти Ёжиков), но тут меня пробило на конкретную крысу - черноглазую сиамку, - а на рынке их не купишь.
- Слушай, у вас в клубе случайно нет сейчас свободных крысят-сиамочек? - спросила я.
Подруга сказала, что сиамочек нет, зато есть кепочки, вот ссылка.
Крысы были ничего такие, забавные. К сожалению, самая симпатичная девочка была уже забронирована. Я начала присматриваться к ее сестренке, но тут увидела фотку их матери и резко передумала. Я люблю длиннномордых, как бультерьеры, крыс, а у этой пыся была коротенькая.
- А у вас нет "таких же, но с перламутровыми пуговицами" (с)? - спросила я.
( И тут подруга совершила фатальную ошибку. )

Вообще-то уделанная клавиатура была подсказкой ;)
( Read more... )

V. Кубики со смыслом

Никакого смысла в строках системы ХИХИ нет. Математика — игра ума. Математики любят играть в кубики и смотреть, как ведет себя система из кубиков, правила которой придуманы произвольно, но жестко соблюдаются. Эта игра интересна сама по себе; никакой другой ценности от нее математику не требуется.

Интересно, однако, понять, какое место занимают ФС в ряду прочих математических инструментов. Чтобы ФС «заговорила» о математике, нам потребуется наделить строки ФС смыслом. Смысл этот мы присваиваем только результату работы ФС; на самом процессе ее работы он не сказывается. Смысл этот, таким образом, определяется снаружи ФС.

Как осмыслить результат работы системы ХИХИ, я не представляю. Это не значит, что смысла нет, или что он есть, но неизвестен. Смысл мы придаем строкам по желанию, любые утверждения о его существовании бессодержательны. Возможно, что кто-то сопоставит строки этой системы с другим математическим объектом, и это даст толчок какой-то новой его идее.

Мы же сейчас рассмотрим другую ФС. Ее алфавит состоит из трех символов: { •, §, # }. Единственную строку •§•#•• будем считать верной по определению. Введем следующие два правила получения новых верных строк:

1. К верной строке можно приписать слева и справа по •, например, из верной строки •§•#•• выйдет по этому правилу ••§•#•••
2. Слева и справа от символа # в верной строке можно вставить по •: из строки •§•#•• получится •§••#•••

Применяя эти правила по очереди в разных сочетаниях, можно получить, например, такие строки (все они будут верными):

••§•••#•••••
••••§•#•••••
•••§•••#••••••

Вы наверняка уже заметили, что если заменить число звездочек на натуральное число и понимать § как операцию сложения, а # как равенство, строки эти можно осмыслить как 2+3=5, 4+1=5, 3+3=6. Я нарочно не сделал + и = символами алфавита нашей системы, а выбрал для этого § и #, чтобы подчеркнуть, что мы осмысливаем § как +, а # как = вне системы.

Кроме того, возможно и иное осмысление. Введем операцию «отнять от» и обозначим ее ÷, например, 1 отнять от 5 даст 4: 1÷5=4. Теперь мы можем задать иной смысл формальному результату: заменим § на =, а # на ÷, и получим тогда верные арифметические выражения: 2=3÷5, 4=1÷5, 3=3÷6.

Формальную систему можно осмыслить множеством способов — насколько хватит фантазии играющего в кубики.

Нелишне будет нам еще раз вспомнить, что результат работы ФС, все ее строки, можно пронумеровать натуральными числами⁶. Эта нумерация, само собой, тоже происходит вне системы: система не нумерует строк, это мы с вами, находясь за границей системы, их нумеруем.

VI. Семантика

До сих пор, мы четко разграничивали формальную («внутреннюю») и интерпретационную («внешнюю») стороны ФС. Сейчас мы с вами построим из ФС и ее избранной интерпретации новый объект, формальную систему со смыслом, или семантикой (ФСС). Каждый раз, когда вы читаете фразу «ФС говорит, что…», «ФС утверждает…», вы имеете дело с ФСС, включающей некоторую интерпретацию ее строк. Такие выражения — совершенно общее место в литературе. Мы, тем не менее, не случайно заострили внимание на различении синтаксиса системы (механических правил преобразования символов) и ее семантики — слоя, положенного поверх синтаксиса и предназначенного для осмысления результата ее работы.

Синтаксис ФС заключен в себе. Это означает, что нам ничего не стоит написать компьютерную программу, которая выполнит все преобразования строк. Семантика ФСС, с другой стороны, не замыкается на себя, но неизбежно обращается к другим понятиям. Чтобы осознать это, рассмотрим осмысление нашей предыдущей ФС в виде ФСС, описывающей сложение натуральных чисел.

Итак, договоримся, что звездочки • означают запись числа в единичной системе: количество звездочек означает натуральное число, равное этому количеству. К каким понятиям мы обратились здесь? Понятия натурального числа и количества. Количество мы, возможно, формализуем, но, опять же, через понятие натурального ряда (нам потребуются числа и операция увеличения на 1, или перехода к следующему числу в ряду). Таким образом, первое же наше смысловое правило привнесло внешнее понятие, именно, понятие натурального ряда, которое мы знали ранее.

Теперь определим § как операцию сложения, а # как равенство, как мы уже делали ранее. Это привнесет новые, уже знакомые нам арифметические понятия сложения натуральных чисел и сравнения их между собой. Результатом сложения является натуральное же число, например, складывая 3 и 4, получим 7. Результатом сравнения чисел может быть одно из двух значений: истина или ложь. Например, утверждение 2=2 истинно, а 2=5 ложно.

Легко показать, что наша ФСС производит все верные выражения для сложения натуральных чисел, и не выдает ни одного неверного⁷.

Давайте взглянем внимательно, как проходит наша новая, семантическая граница, что находится теперь внутри и вовне ФСС. Утверждение 2+2=4 выводится внутри семантики ФСС, той предметной области, в которой определена наша смысловая интерпретация. Однако, утверждение «2+2=4 истинно» лежит вовне нашей новой системы. Когда мы говорим о семантической интерпретации, следует отличать истинность, которую мы определяем для себя, сравнивая результат осмысления строк системы с «внешним миром», и выводимость, возможность получения строки-утверждения в ФС. Выводимость утверждения (в семантической области мы называем строки утверждениями) определяется формализмом системы. Истинность же «на самом деле» система сама по себе не утверждает; любое «на самом деле», какой бы смысл ни вкладывался в эти слова, находится всегда вовне системы.

Это утверждение, если мы с вами рассуждаем о такой простой системе, конечно же, тривиально. В дальнейшем, однако, когда мы рассмотрим более сложную ФСС, вынесение «истинности» за границу системы создает серьезные диалектические вопросы в понимании математики.

VII. Элементарная арифметика

ФСС, которую мы рассмотрели, порождает результат чрезвычайно тривиальный: перечисление всех выражений вида a+b=c с конкретными числами. Однако, далеко не все формальные системы так просты. Назначая правила синтаксиса и базовую семантику символов, мы можем получить и систему, которая, как оказывается, выводит теоремы элементарной арифметики!

Тоже мне, скажете вы, особое достижение — элементарная арифметика! Это ведь то, что мы к третьему классу уже все знали, сложение-умножение? Нет, неверно. Младшеклассникам, изучающим арифметику в школе, показывают даже не краешек, а тень этой математической горы! К элементарной арифметике (ЭА) относятся, например, задачи решения диофантовых уравнений, изучение простых чисел, и очень многое другое. К примеру, Великая теорема Ферма, остававшаяся недоказанной несколько веков, тоже относится к области арифметики. Вся современная компьютерная криптография имеет в своей научной основе арифметику. А элементарной мы называем такую систему арифметики вовсе не потому, что она очень простая, а потому, что она не требует основания в других разделах математики, строится на основе своих собственных аксиом. Геометрия Эвклида тоже будет в этом смысле элементарной геометрией, потому что она не требует для основания ничего, кроме своих собственных понятий и аксиом.

Так же, как и в геометрии, где не определяются некоторые понятия, например,точки или прямой, в арифметике тоже есть неопределимые понятия. Одно из них — интуитивно знакомое всем натуральное число. Хоть нам все интуитивно известно, что такое число, никакого определения числа арифметика не дает. Аксиомами задаются лишь их свойства, такие, как «для каждого числа есть ровно одно последующее число», «1 не следует ни за каким числом» и прочие. Устройством своих основ ЭА напоминает геометрию; хотя последней уделяется в школе определенное внимание, аксиоматическое определение арифметики в школе не упоминается вовсе.

В число теорем арифметики включаются, разумеется, и утверждения, широко известные под именем собственно теорем («для любого натурального числа существует превышающее его простое число»), и более частные утверждения, возникающие при решении отдельных задач («не существует трех простых чисел, больших 3, подряд через одно», т. е. для любого простого числа p>3, по крайней мере одно из p+2 и p+4 не является простым), и совсем уж тривиальные, не интересные, на первый взгляд, утверждения (например, «для любого числа а, 0+а=а»).

В этом популярном изложении не найдется места детальному описанию ФСС, производящей теоремы ЭА. Если вас интересуют подробности ее работы и устройства, лучше обратиться к [1] за популярным изложением или к [2] за глубоким математическим изъяснением предмета. Мы ограничимся только общими принципами ее построения, и сама теорема Геделя будет объяснена лишь «на пальцах», без надлежащих стройных формулировок и строгих доказательств.

Продолжение следует.

__________________________________
⇧ 6. Подумайте, как можно пронумеровать строки, порождаемые нашей системой.

⇧ 7. Попробуйте, в качестве упражнения, доказать это.