?

Log in

нормальные герои всегда идут в обход или новый обход парадокса Расселла - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

нормальные герои всегда идут в обход или новый обход парадокса Расселла [окт. 3, 2002|11:56 pm]
Anatoly Vorobey
Чрезвычайно интересное письмо Харви Фридмана на рассылке FOM (Foundations of Mathematics). Фридман анонсирует свой новый результат -- "естественную" формальную систему для теории множеств, эквивалентную существованию некоторого класса больших кардиналов в ZFC.


Несколько упрощая и сокращая, историю schema of comprehension (назову её схемой охвата; если кто-то знает "официальное" русское название, подскажите) можно представить так. В конце прошлого века Фреге придумал простой и удобный метод формализовать теорию множеств, которую в свою очередь можно рассматривать в качестве формального фундамента всей (почти) современной математики -- а построение такого фундамента как раз и было одной из главных задач математической логики на рубеже веков и в первой половине 20-го века.

(на самом деле Фреге формализовал не теорию множеств, а теорию типов -- но его результаты потом использовались для теории множеств, и когда обнаружилось, как легко с помощью множеств формализуется вся математика, теории типов потеряли почти всю свою притягатлеьность)

Так вот. Теорию множеств можно очень легко и красиво формализовать при помощи всего нескольких аксиом, из которой главной является схема охвата (а остальные одну или две я упоминать не буду). Она гласит, что любому свойству соответствует множество всех множеств, имеющих это свойство. Эта схема позволяет очень легко строить разнообразные множества, обладающие нужными характеристиками. Нужно пустое множество? Рассмотрим свойство "x не равно x". Согласно схеме охвата, существует множество, содержащее все множества x, такие, что x не равно x. Но таких x не существует, следовательно, это множество - пустое. Нужно объединение двух множеств a и b? Смотрим на свойство "быть членом a или быть членом b" и получаем по схеме охвата множество всех таких членов, что и есть объединение a и b. И так далее, и тому подобное.

В 1902-м году, однако, Бертранд Расселл доказал, что схема охвата приводит к противоречивой теории. Рассмотрим свойство "не быть членом самого себя", и пусть X, согласно схеме охвата, будет множеством всех множеств, которые не являются членами самих себя. Если само множество X является членом самого себя, то, по своему же определению, оно не является членом самого себя. Если же оно не является членом самого себя, то опять по его же определению, оно - одно из тех множеств, которые составляют X. Получаем противоречие: X не может ни быть членом самого себя, ни не быть членом самого себя. Это - знаменитый парадокс Расселла.

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

Такие наборы аксиом были построены; самый известный и широко используемый из них -- система аксиом ZFC (по инициалам математиков, сыгравших роль в её формулировке: Zermelo-Fraenkel, а буква C означает аксиому выбора (Choice)). Место схемы охвата в ZFC или других схожих с ней аксиоматических теориях занимает горсть аксиом, позволяющих в основном строить множества "снизу вверх". Например, аксиома пары гласит, что если есть множества a и b, то есть и множество {a,b}, состоящее из них обоих; аксиома объединения позволяет строить объединение набора множеств и считать его тоже множеством; итп. Только аксиома выбора позволяет в каком-то смысле взять множество "из ничего", не скомбинировав точно определённым образом уже существующие - но и в ней "размер" получающегося множества строго ограничен.

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

Результат Фридмана интересен тем, что он возвращается к схеме охвата, и только немного её модифицирует, ослабляет её некоторым образом (технические подробности есть в пролинкованном письме Фридмана). В предлагаемой им теории можно опять выбросить скучные, "осторожные" аксиомы, строящие всё по ступенькам, и пользоваться столь удобной схемой охвата (хоть и ограниченной новым условием -- не знаю, насколько подходящей для действительного использования на практике при изучении теории множеств окажется система Фридмана -- допускаю, что окажется неподходящей, но всё равно результат очень интересен). Кроме того, построенная таким образом теория оказывается сильнее ZFC и эквивалентной ZFC, усиленной утверждением о существовании некоторого класса больших кардиналов. Что такое большие кардиналы и чем они важны я уже не надеюсь здесь объяснить - но скажу вкратце, что аксиомы о существовании больших кардиналов во многом являются следующим логическом шагом для пополнения теории множеств новыми аксиомами; проблема в том, что в отличие от всех других аксиом теории множеств они очень далеки от обычной математической практики, и среднему математику совершенно непонятно, зачем и как и кому они нужны. Фридман, который убеждён в том, что несмотря на свою кажущуся эзотеричность (с точки зрения обычной "рабочей" математики) аксиомы больших кардиналов очень важны и следует внедрять их понимание в математические массы, уже много лет работает над нахождением "естественных" с точки зрения обычной математики задач, которые оказываются нерешаемы в рамках ZFC и требуют для их решения каких-нибудь дополнительных аксиом о больших кардиналах. У него на этом пути есть весьма интересные результаты, хотя настоящей своей цели он пока не добился. А этот результат, если он верен, показывает прямую связь между "эзотеричной" аксиомой о существовании больших кардиналов (одной из множества таких аксиом) и довольно-таки "естественной" и интересной новой аксиоматической формулировкой теории множеств, опирающейся на "переработанную" схему охвата.
СсылкаОтветить

Comments:
[User Picture]From: passing
2002-10-03 02:31 pm

Мда:) Проверяешь на "вшивость"?:))
Все регулярные воспеватели отвалились, не нашли чего сказать. Ну ладно, я тады это - попробую, не пустовать же посту:)
Когда-то в детстве проходили мы разные бесконечносты всяких порядков. Может эти самые парадоксальные "множества" просто являют совой следующыю степень этой самои бесконечности, а аксиомы охвата(?) - например действуют только на одной и той же?
Э как завернул, сам ничего не знаючи:)))
(Ответить) (Thread)
[User Picture]From: avva
2002-10-03 02:58 pm
Какая вшивость, при чём тут?

"Бесконечности разных порядков" - это и есть кардиналы. "Парадоксальное" по своей величине множество больше всех таких бесконечностей и включает их все в себя.

Большие кардиналы - это бесконечности столь невообразимо больших порядков, что они начинают себя весьма странно с обычной точки зрения.
(Ответить) (Parent) (Thread)
[User Picture]From: passing
2002-10-03 03:25 pm
Дак енто я, выходит, почти в тему слямзил? Ба:) Приятно. В свое время любил я эту теорию множеств, ну и она тоже отвечала временами. А теперь квадратное уравнение с трудом (в последнии раз формулу детерминанта выводил через уравнение производной, которую, почемуто, помню - вот так:))

Про вшивость, точно не помню но мне показалось что этот пост вроде того "мне скучно" - типа посмотреть сколько придворных весельчаков предложит развлечь. Типичный сказочный сюжет:)) Нет?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-10-03 03:30 pm

Re:

Нет, просто это тема, которая меня интересует.
Я не занимаюсь вообще-то постами вида "типа посмотреть", это не моя специальность. Да и придворных весельчаков вокруг себя не наблюдаю, к счастью.

(Ответить) (Parent) (Thread)
[User Picture]From: passing
2002-10-04 08:53 am
Тут вот подумалось...а какова кардинальность слова/определения "ВСЕ"?
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-10-03 03:36 pm
Выход - актуальную бесконечность запретить.

Множество подмножеств всех множеств уже парадокс.

(Ответить) (Thread)
[User Picture]From: avva
2002-10-03 03:43 pm
Без актуальной бесконечности тяжело жить.

А множество подмножеств всех множеств это то же самое, что и множество всех множеств.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-10-03 03:53 pm
Тогда запретить всехность применительно к бесконечности как алгоритмически недостижимую.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-10-03 04:14 pm
1)Опять же кажется, что кардинальное число множества подмножеств всех множеств больше, чем множества всех множеств.

2)Допущение таких конструкций ничем не лучше теологических споров, может ли бог создать такой камень, который сам не сможет поднять.
(Ответить) (Parent) (Thread)
[User Picture]From: lz
2002-10-03 04:30 pm

2 - на этот вопрос уже дан изящный ответ, еще в начале прошлого века - не только может, но и уже создал - это человек с его свободной волей
:-))
(Ответить) (Parent) (Thread)
[User Picture]From: ktotam
2002-10-07 06:24 pm
со свободной волей не всё так просто
(Ответить) (Parent) (Thread)
From: (Anonymous)
2002-10-04 02:14 am
A ne mogli by vy ob'yasnit', chto takoe language L (epsilon)?

Spasibo
(Ответить) (Thread)
[User Picture]From: avva
2002-10-04 03:49 am

Re:

L(epsilon) означает, что данная теория строится формальном языке, имеющем только один знак - буква эпсилон, использующаяся для обозначения того, что одно множество является членом другого (a ε b означает, что a - член b). L означает Language, а в скобках перечисляются базисные символы данного логического языка.

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

Другая альтернатива, которую используют чаще, т.к. она удобнее по ряду причин -- считать базисным знаком вместе со знаком ε также знак равенства =. Тогда в список стандартных аксиом данной логической аксиомы включают также несколько аксиом, определяющих обычные свойства равенства (например, x=x; если x=y и y=z, то x=z; итп.).

От того, какую логику выбрать - с равенством или без равенства (first-order logic with equality или first-order logic without equality) зависит то, какие аксиомы потом надо брать для теории множеств, и некоторые другие технические детали.

Самая важная из них - форма аксиомы экстенциональности, очень важной аксиомы, которая утверждает, что два множества равны тогда и только тогда, когда у них есть одинаковые члены, т.е. "a=b" эквивалентно "любой x является членом a тогда и только тогда, когда x является членом b".

В случае логики с равенством, когда = является одним из базисных символов, т.е. языка L(=,epsilon), одно направление этой аксиомы является тривиальным следствием аксиом равенства: если a=b, то a можно подставлять вместо b в любом выражении и наоборот, поэтому x ε a влечёт x ε b и наоборот. А вот второе её направление является совсем нетривиальным и очень важным, поэтому в такой формулировке его и называют аксиомой экстенциональности: "если множества a и b имеют одинаковый набор членов, то a=b".

В случае же логики без равенства, с языком L(epsilon), как у Фридмана, равенство определяется с помощью этого свойства: множества a и b называются равными, если у них одни и те же члены. Тогда аксиома экстенциональности просто не нужна, т.к. она по сути дела превратилась в определение равенства. И поэтому в системе Фридмана есть вообще всего одна аксиома (точнее, схема аксиом) охвата, и больше ничего: в более обычной формулировке логики с равенством он не смог бы обойтись без аксиомы экстенциональности.

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

Логика без равенства как бы более лаконична, по-спартански минимальна, чем логика с равенством. Логика с равенством более удобна и чаще используется.
(Ответить) (Parent) (Thread)