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

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

Парадокс Рассела — открытая в 1903 году Бертраном Расселом и позднее независимо переоткрытая Э. Цермело теоретико-множественная антиномия, демонстрирующая противоречивость наивной теории множеств Г. Кантора.

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

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

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

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

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

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

[править] Варианты формулировок

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

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

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

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

И ещё один:

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