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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Основные сведения

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

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

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

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

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

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

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

Существует много формулировок этого парадокса. Здесь приведены часто встречающиеся:

  • Наиболее ранняя из формулировок, приписываемая софистам, называется Парадокс лжеца: «Критянин сказал, что все критяне лжецы. Сказал ли он правду?»
  • Парадокс брадобрея: Единственному деревенскому брадобрею приказали: «Брить всякого, кто сам не бреется, и не брить того, кто сам бреется». Кто побреет брадобрея?
  • В одной стране вышел указ: «Мэры всех городов должны жить не в своем городе, а в специальном Городе мэров». Где должен жить мэр Города мэров?
  • Некая библиотека решила составить библиографический каталог, в который входили бы все те и только те библиографические каталоги, которые не содержат ссылок на самих себя. Должен ли такой каталог включать ссылку на себя?
  • Парадокс всемогущества: может ли всемогущее существо сделать что-либо, что ограничило бы его способность выполнять действия?

См. также

Литература

Примечания

  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