Парадокс Рассела

Парадокс Рассела — открытый в 1901 году^[1] Бертраном Расселом и позднее независимо переоткрытый Э. Цермело теоретико-множественный парадокс, демонстрирующий противоречивость логической системы Фреге, являвшейся ранней попыткой формализации наивной теории множеств Г. Кантора.

Парадокс Рассела формулируется следующим образом:

Пусть $K$ — множество всех множеств, которые не содержат себя в качестве своего элемента. Содержит ли $K$ само себя в качестве элемента? Если да, то, по определению $K$, оно не должно быть элементом $K$ — противоречие. Если нет — то, по определению $K$, оно должно быть элементом $K$ — вновь противоречие.

Противоречие в парадоксе Рассела возникает из-за использования в рассуждении внутренне противоречивого^[2] понятия множества всех множеств и представления о возможности неограниченного применения законов классической логики при работе с множествами. Для преодоления этого парадокса было предложено несколько путей. Наиболее известный состоит в предъявлении для теории множеств непротиворечивой формализации $\mathcal M$, по отношению к которой являлись бы допустимыми все «действительно нужные» (в некотором смысле) способы оперирования с множествами. В рамках такой формализации утверждение о существовании множества всех множеств было бы невыводимым.

Действительно, допустим, что множество $U$ всех множеств существует. Тогда, согласно аксиоме выделения, должно существовать и множество $K$, элементами которого являются те и только те множества, которые не содержат себя в качестве элемента. Однако предположение о существовании множества $K$ приводит к парадоксу Рассела. Следовательно, ввиду непротиворечивости теории $\mathcal M$, утверждение о существовании множества $U$ невыводимо в этой теории, что и требовалось доказать.

В ходе реализации описанной программы «спасения» теории множеств было предложено несколько возможных её аксиоматизаций (теория Цермело — Френкеля ZF, теория Неймана — Бернайса — Гёделя NBG и т. д.), однако ни для одной из этих теорий до настоящего момента не найдено доказательства непротиворечивости. Более того, как показал Гёдель, разработав ряд теорем о неполноте, такого доказательства не может существовать (в некотором смысле).

Другой реакцией на открытие парадокса Рассела явился интуиционизм Л. Э. Я. Брауэра.

Варианты формулировок

Существует много популярных формулировок этого парадокса. Одна из них традиционно называется парадоксом брадобрея и звучит так:

Одному деревенскому брадобрею приказали «брить всякого, кто сам не бреется, и не брить того, кто сам бреется». Как он должен поступить с самим собой?

Еще один вариант:

В одной стране вышел указ: «Мэры всех городов должны жить не в своем городе, а в специальном Городе мэров». Где должен жить мэр Города мэров?

И ещё один:

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

См. также

• Парадокс Бурали-Форти
• Парадокс Кантора
• Парадокс Мириманова

Литература

• Курант Р., Роббинс Г. Что такое математика? — гл. II, § 4.5
• Мирошниченко П. Н. Что же разрушал парадокс Рассела в системе Фреге? // Современная логика: проблемы теории, истории и применения в науке. — СПб., 2000. — С. 512—514.
• Катречко С. Л. Расселовский парадокс брадобрея и диалектика Платона — Аристотеля // Современная логика: проблемы теории, истории и применения в науке. — СПб., 2002. — С. 239—242.
• Мартин Гарднер А ну-ка, догадайся! = Aha! Gotcha. Paradoxes to puzzle and delight. — М.: Мир, 1984. — С. 22-23. — 213 с.

Примечания

1. ↑ Godehard Link (2004), «One hundred years of Russell's paradox», с. 350, ISBN 9783110174380, <http://books.google.com/?id=Xg6QpedPpcsC&pg=PA350> 
2. ↑ Френкель А.А, Бар-Хиллел И. Основания теории множеств / А.А. Френкель, И. Бар-Хиллел. – М.: Мир, 1966. – C. 17-18