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

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

На неформальном языке парадокс можно описать следующим образом. Условимся называть множество «обычным», если оно не является своим собственным элементом. Например, множество всех людей является «обычным», так как само множество — не человек. Примером «необычного» множества является множество всех множеств, так как оно само является множеством, а следовательно, само является собственным элементом^[2].

Можно рассмотреть множество, состоящее только из всех «обычных» множеств, такое множество называется ра́сселовским мно́жеством. Парадокс возникает при попытке определить, является ли это множество «обычным» или нет, то есть содержит ли оно себя в качестве элемента. Есть две возможности.

Парадокс Рассела можно сформулировать в наивной теории множеств. Следовательно, наивная теория множеств является противоречивой. Противоречив фрагмент наивной теории множеств, который можно определить как теорию первого порядка с бинарным отношением принадлежности $\in$ и схемой свёртывания: для каждой логической формулы $P(x)$ с одной свободной переменной в наивной теории множеств есть аксиома

Эта схема аксиом говорит, что для всякого условия $P(x)$ существует множество $y,$ состоящее из тех $x,$ которые удовлетворяют условию $P(x)$ ^[3].

Этого оказывается достаточно, чтобы сформулировать парадокс Рассела следующим образом. Пусть $P(x)$ есть формула $x\notin x.$ (То есть $P(x)$ означает, что множество $x$ не содержит себя в качестве элемента, или, в нашей терминологии, является «обычным» множеством.) Тогда, по аксиоме свёртывания, найдётся множество $y$ (расселовское множество) такое, что