?

Log in

No account? Create an account

Восток и запад: предпочитает ли бог инициальные алгебры? - The chronicler of 452 — LiveJournal

Aug. 14th, 2010

09:56 pm - Восток и запад: предпочитает ли бог инициальные алгебры?

Previous Entry Share Next Entry

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

Изначальная формулировка теоремы Гёделя — полностью синтаксическая: если формальная теория из определённого класса непротиворечива, то она и неполна. Метафизический флёр ей придаёт семантический „довесок“ (точнее „долив“) — замечание о том, что недоказуемое гёделево высказывание истинно. Откуда и делается неутешительный вывод
формальные теории принципиально ущербны (неполны): они не могут доказать некоторые истинные высказывания.

Что же, в данном случае, понимается под истинностью? А то, что гёделево высказывание выполняется в „стандартной модели“ (no relation) арифметики, где термам формальной теории „из определённого класса“ сопоставляются выражения из обычных натуральных чисел и арифметических операций. Понятно, что непредвзятый наблюдатель (не постулирующий заранее, что модель важнее формальной теории) мог бы сделать совершенно симметричное заключение:
модели принципиально ущербны (переполнены): в них оказываются верными высказывания, которые ниоткуда не следуют.

Вот две точки зрения: первая считает первоначальной истину, вторая доказательство. Действительно ли они равноправны? Конечно нет, однако не по той причине (и не в ту сторону), как обычно полагают. Дело в том, то „синтаксис“, т.е. формальная теория и сопутствующее ей понятие доказательства — один, а соответствующих ему моделей (в которых определена истинность) — много. Поэтому синтаксические понятия, включая доказательство, обладают выделенным статусом, по отношению к массе возможных моделей. Более того, как успокаивает нас теорема Гёделя о полноте (более важная, чем её знаменитая почти-тёзка) высказывание доказуемо тогда и только тогда, когда оно истинно во всех моделях. Значит недоказуемое высказывание, вроде гёделевого, обязательно ложно в некоторых моделях:
модели принципиально ущербны: в них оказываются верными высказывания, которые ниоткуда не следуют и которые необходимо ложны в других моделях (т.е. модели обязательно противоречат друг другу).

Представление о первичности истинности по отношению к доказательству и содержимого по отношению к форме очень древнее и распространённое. Вот некоторые его проявления:

  • математические объекты существуют автономно и независимо от нас;
  • классический натуральный ряд (т.е. инициальная модель аксиом Пеано) обладает особым статусом среди всех моделей;
  • математика есть неформализуемое созерцание эйдосов;
  • на самом деле Пятый Постулат Евклида (в совр. варианте — континуум гипотеза, аксиома выбора) верен (не верен);
  • „Какая сложная у тебя профессия: у меня столько идей, а не могу написать ни строчки“ — жалоба Э. Моне Малларме.

А вот как выглядит противоположная точка зрения:
  • Лейбниц не мог знать телефона Анны Карениной;
  • математика есть комбинаторная деятельность, как и сочинение сонетов, кулинария и военное искусство;
  • варьировать нижележащую теорию множеств (и даже логику) так же естественно и полезно, как и локальную систему координат;
  • „Стихи, мой друг, пишутся из слов, а не из идей“.

Не претендуя на историческую достоверность, первую систему взглядов можно назвать „вавилонской“ — жители Междуречья знали и использовали много полезных математических истин, но идея их доказательства в систематической форме им была неинтересна. Вторая же позиция, несомненно, греческая — торговцы и софисты не переставая что-то доказывали, включая и вещи совершенно бесполезные: „Со времён греков говорить «математика» — значит говорить «доказательство»“ (Н. Бурбаки).

Шутка.

Comments:

[User Picture]
From:falcao
Date:August 14th, 2010 08:31 pm (UTC)

апология классической модели арифметики

(Link)
Хотя у меня есть перед Вами "долг" со старых времён в виде пары неотвеченных комментов, я надеюсь, что Вы не будете возражать против того, чтобы помимо "замороженного мяса" Тигры покушали немного "свежатинки", раз уж она попалась под руку лапу :)

> Изначальная формулировка теоремы Гёделя — полностью синтаксическая

Так ли это? Если брать исторически "изначальную" формулировку, то она была усложнённой, и в неё входило условие "омега-непротиворечивости", которое далее было просто отброшено. Устроит ли Вас утверждение о том, что ТГ всего лишь можно сформулировать именно так, как Вы это сделали?

> модели принципиально ущербны (переполнены): в них оказываются верными высказывания, которые ниоткуда не следуют

Давайте прежде всего обратим внимание, что тот "наблюдатель", от имени которого произносится эта фраза, признаёт само "существование" моделей -- коль скоро он о них говорит. Тогда он наверняка признаёт и существование "стандартной" или "классической" модели. Если это так, то получается, что с его точки она как бы ничем не лучше остальных.

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

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

Теперь ещё одно соображение. Если кто-то занимает позицию "правоты" доказуемости -- в противовес истинности, то неплохо было бы предъявить не абстрактный, а конкретный пример "конфликтного" утверждения. Из тех рассуждений, которые прозвучали у Вас, вроде бы следует, что такие утверждения должны быть. Однако предъявление реального примера могло бы многое поставить на свои места.

Здесь как раз годится пример Пятого Постулата. Ясно, что он будет истинным в одной модели (геометрии) и ложен в другой. Обычная точка зрения на этот вопрос заключается в том, что неевклидова геометрия нисколько не "хуже" евклидовой, то есть утверждается некий "равноправный" статус этих двух моделей. Кстати, замечу, что часто используемый аргумент против "платонизма" применяется здесь совсем неправомерно. Когда кто-то говорит, что Пятый Постулат истинен или ложен в неком "абсолютном" смысле, пытаясь вывести это как следствие "объективности" Мира Идей, то не учитывается совсем простое явление -- возможность существования нескольких "обителей". Которых, как известно из Евангелия, там вообще "много" :)

Корни этой ошибки достаточно прозрачны, и их даже не очень интересно анализировать. Но мыслимо ли аналогичное явление на базе арифметики? То есть можно ли предъявить какую-то альтернативную модель натурального ряда, которая была бы "не хуже" классической? Я всё-таки думаю, что нет. (Доводы, которые у меня есть в "арсенале", опять-таки за мной, если что.)

С континуум-гипотезой и аксиомой выбора ситуация не так проста, так как аксиоматизация Цермело - Френкеля (или другие ей "эквивалентные") многих особенностей просто не ухватывает. То есть тут несовершенство аксиоматизаций имеет даже более серьёзный "дефект" нежели неполнота формальной системы Пеано. В последнем случае легко указать саму причину неполноты. Это ярко видно уже на основании того, что соответствующая система аксиом второго порядка, где речь идёт о ВСЕХ свойствах чисел, а не только об арифметических (то есть выразимых на языке формальной теории) имеет одну -- классическую -- модель.

Так что я бы предпочёл говорить об одном "конфликтном" пункте, касающемся особого статуса натурального ряда. Что на этот счёт могут сказать "греки"? На примере бесед с людьми, которые придерживаются этой точки зрения, я не слышал ничего более разумного кроме "а вдруг существует такая модель, за которой закрепится статус, что она ничем не хуже классической?" Я бы хотел продвинуться чуть дальше этого уровня, если это вообще возможно.
(Reply) (Thread)
[User Picture]
From:furia_krucha
Date:August 14th, 2010 09:25 pm (UTC)

апология доказательства

(Link)
Хотя у меня есть перед Вами "долг" со старых времён в виде пары неотвеченных комментов, я надеюсь, что Вы не будете возражать против того, чтобы помимо "замороженного мяса" Тигры покушали немного "свежатинки", раз уж она попалась под руку лапу :)
Честно говоря, я бы предпочёл разбираться с вопросами по-порядку, хотя тигр, конечно, зверь вольный. У меня всё укрепляется ощущение, что Магеллан вам надоел: опять целый месяц ничего не было слышно, хотя на „сладчайшего“ Гёделя, вы среагировали быстро. :-) Если это действительно так, то давайте придадим обсуждению какое-то завершение (как вы сами отмечали нам с вами именно его часто не хватало в прошлом), тем более, что за ним следим не только мы одни.

Так ли это?
Да, в этом я достаточно уверен. Про \omega-consistency и приём Россера я знаю. Вот формулировка из английского перевода Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I (я сравнил и с другим переводом, на всякий случай):
Theorem VI: For every ω-consistent [primitive] recursive class κ of FORMULAS, there exists a [primitive] recursive CLASS EXPRESSION r such that neither v Gen r nor Neg(v Gen r) belongs to Flg(κ) (where v is the FREE VARIABLE of r).

(Я добавил primitive, т.к. терминология Геделя отличается от современной.) Как видите, про истинность r ничего не говорится. Забавно, что как обычно, обсуждение немедленно ушло на google books. :-)

По поводу остального, в виду первого параграфа, отвечу пока совсем коротко: статус классического натурального ряда, это, несомненно, важный пример, но суть проблемы, не в нём (как вы наверное заметили, утвеждение о его исключительности единственное, для которого нет греческой пары), а в представлении, что есть истинность помимо, до (и вопреки!) доказуемости и что, соответственно, результат Гёделя демонстрирует некую „ущербность“ формализмов.
(Reply) (Parent) (Thread)
[User Picture]
From:falcao
Date:August 15th, 2010 10:28 am (UTC)

других моделей у меня нет :)

(Link)
> я бы предпочёл разбираться с вопросами по-порядку

Я Вас вполне понимаю, но для меня ситуация выглядит примерно так: вот есть только что купленная свежая французская булка, и её можно прямо сейчас скушать :) А есть лежащий на полке давний сухарь, которому уже года полтора :) Его вообще-то никто не собирается выкидывать, и со временем планируется съест и его, но при наличии свежеиспечённого хлеба, ситуация выглядит вполне понятной.

> укрепляется ощущение, что Магеллан вам надоел

Это не совсем так. Тема мне по-прежнему интересна, но там мы многое уже как бы "исчерпали". В принципе, я за то, чтобы подвести под то обсуждение некую "черту", подытожив всё, что было сказано. А при обнаружении каких-то новых фактов или ссылок можно к этой теме возвращаться. Будучи на отдыхе, я не имел возможности Вам ответить в той ветке, но надеюсь на то, что по возвращении домой мы всё это приведём к какому-то "каноническому виду" :)

Насчёт изначальной формулировки я понял, что Вы имели в виду. Если "профильтровать" кое-какие второстепенные вещи, то получится "синтаксическая", а не "семантическая" формулировка, включающая в себя понятие истинности. В принципе, я не имею тут ничего против.

Основная мысль Вашего поста, как я понимаю -- это "перевернуть приоритеты". То есть посмотреть на результаты Гёделя как бы с другого "края". Но давайте зададим вопрос: почему формальные системы кто-то может считать "ущербными"? Ответ, наверное, состоит в том, что они не оправдали неких возлагаемых на них ожиданий. То есть они не позволяют вывести все истинные утверждения об интересующих нас объектах. Это факт. А что получается у Вас? То есть от формализмов чего-то можно было ожидать, и это не оправдалось, а как насчёт моделей? Ведь они, в отличие от формальных систем, то есть "наук" -- это "зверушки", которых мы изучаем. И какие мы к ним можем предъявлять требования? Теорию мы можем усовершенствовать, добавив к ней новые аксиомы, но как мы можем повлиять на объективно существующий (с точки зрения "платонизма") натуральный ряд? Это получается примерно как с "другими писателями"! :)
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:alexey_rom
Date:August 15th, 2010 09:30 pm (UTC)

Re: апология классической модели арифметики

(Link)
Пеано разницы между логикой первого и высших порядков ещё не знал. Аксиома индукции в формулировке Пеано говорит о всех свойствах -- это аксиома второго порядка (увы, просмотра источника на Google Books у меня нет; я основываюсь на переводах). Какие есть причины принять первопорядковую схему аксиом индукции, не принимая второпорядковую аксиому?
(Reply) (Parent) (Thread)
[User Picture]
From:falcao
Date:August 21st, 2010 05:10 pm (UTC)

реабилитация Интуиции

(Link)
Тут надо учитывать одну вещь: когда мы говорим "аксиомы Пеано" или "арифметика Пеано", то под этим стандартно понимается нечто "устаканившееся", названное в честь этого математика (примерно так же обстоит дело и с теоремой Пифагора). Ясно, что принцип математической индукции при этом получается "урезанный", то есть он относится только к арифметическим свойствам.

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

Я вообще вижу главной задачей "реабилитацию" Интуиции, потому что весь "сыр-бор" ведь разгорается вокруг этого. Всё остальное -- это "маскировка" или "дымовухи" :)
(Reply) (Parent) (Thread)
[User Picture]
From:alexthunder
Date:August 14th, 2010 09:53 pm (UTC)
(Link)
Очень интересный взгляд.
Спасибо большущее!
(Reply) (Thread)
[User Picture]
From:furia_krucha
Date:August 14th, 2010 10:00 pm (UTC)
(Link)
Всегда рад.
(Reply) (Parent) (Thread)
[User Picture]
From:az118
Date:August 15th, 2010 11:10 am (UTC)
(Link)
надо сонет написать про то как

в начале были слово и истинна,
но не было слов, синтаксиса и доказательств
за их ненадобностью.

потом слова размножились, породив надобность
в доказательствах их истинности и синтаксисе,
и утопили истину в них.
(Reply) (Thread)
[User Picture]
From:furia_krucha
Date:August 15th, 2010 11:28 am (UTC)
(Link)
Initio ratio erat.
(Reply) (Parent) (Thread)
[User Picture]
From:az118
Date:August 15th, 2010 01:57 pm (UTC)
(Link)
в начале был при-каз
из слова одного
и начался рас-с-каз
про это и про то

и у-казуют руки
на полную луну
где ползают науки
по илистому дну

а если кто до-кажет
что это есть не то
жестоко всех на-кажем
отправим в эрато
(Reply) (Parent) (Thread) (Expand)
From:ex_kosilova
Date:August 15th, 2010 05:25 pm (UTC)
(Link)
Пардон, я не математик, у меня глупый вопрос. Вот Вы пишете "Представление о первичности истинности по отношению к доказательству ..." - что имеется в виду? Доказательство ведь тоже может быть истинным и не истинным? Имеется в виду представление об истинности какого-то высказывания ?
(Reply) (Thread)
[User Picture]
From:furia_krucha
Date:August 15th, 2010 05:55 pm (UTC)
(Link)
Слово "истина" тут нужно понимать как термин из математической логики. (Кстати, математики говорят про доказательство не "истинно" или "ложно", а "верно" или "ошибочно".)

Речь идёт вот о чём: есть т.н. "формальные теории", которые состоят из "языка" (способа строить формулы теории), "аксиом" и "правил вывода". Аксиомы и правила вывода определяют какие формулы считаются "доказуемыми", т.е. для каких формул есть цепочка, начинающаяся с аксиом, формируемая согласно правилам вывода и оканчивающаяся данной формулой. Все эти понятия и манипуляции исключительно _синтаксические_, т.е. сводящиеся с операциям над строками символов.

Для формальной теории можно построить _модель_ --- это множество объектов, которые в некотором техническом смысле "удовлетворяют" теории. Модели это "семантика" формальных теорий. Про высказывание говорят, что оно "истинно" (в некоторой модели!) если оно выполняется в этой модели, т.е. если объекты, из которых состоит модель действительно находятся в этом соотношении.

Теорема Гёделя о полноте устанавливает связь между синтаксическим понятием доказуемости и семантическим понятием истинности: для формальных теорий определённого класса, высказывание доказуемо если и только оно истинно во _всех_ моделях.

Вот пример: можно построить формальную теорию, соответствующую геометрии Евклида, без постулата о параллельных. У неё есть разные модели: одна "стандартная", где в качестве прямых, точек и плоскостей берутся обычные геометрические объекты, другая "нестандартная", например полуплоскость Пуанкаре. Все высказывания доказуемые из аксиом (за вычетом 5-го постулата) будут истинны во всех моделях, но сам постулат в нестандартной модели не выполняется.

То же самое верно и для аксиом Пеано натуральных чисел: имеются нестандартные модели этих аксиом (хотя их и сложнее описать, чем для геометрии) и высказывание истинно во всех моделях тогда и только тогда, когда оно доказуемо из аскиом.
(Reply) (Parent) (Thread) (Expand)
From:(Anonymous)
Date:October 27th, 2011 02:59 am (UTC)

Спасибо за информацию

(Link)
Увлекательно спс Вам! Об таком я прочитала, а на том блоге как-то иначе было написано...
(Reply) (Thread)
[User Picture]
From:livejournal
Date:July 25th, 2013 12:05 am (UTC)

Восток и запад: предпочитает ли бог инициальные алгебр

(Link)
User az118 referenced to your post from Восток и запад: предпочитает ли бог инициальные алгебры? saying: [...] Оригинал взят у в Восток и запад: предпочитает ли бог инициальные алгебры? [...]
(Reply) (Thread)
[User Picture]
From:livejournal
Date:July 25th, 2013 11:07 am (UTC)

генеалогия структур

(Link)
User az118 referenced to your post from генеалогия структур saying: [...] да, эти аксиомы задают еще ZF [...]
(Reply) (Thread)