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

Можно предположить существование множеств, которые принадлежат сами себе в качестве элемента, и множеств, которые собственными элементами не являются.

Рассмотрим множество $A$ всех таких множеств $X$, которые не являются элементами $X$ (самих себя): [math]\displaystyle{ A= \{X | X\notin X\} }[/math].

Принадлежит ли $A$ само себе как элемент?

Если $A\in A$, то по определению этого множества получим $A\notin A$.

Если предположить, что $A\notin A$, то оказывается $A\in A$.

В любом случае получается, что $A\in A$ и $A\not\in A$ — противоречие.

Рис. 1. Если [math]\displaystyle{ A \in A }[/math], то по определению [math]\displaystyle{ A \notin A }[/math]; если [math]\displaystyle{ A \notin A }[/math], то [math]\displaystyle{ A \in A }[/math]. Оба варианта дают противоречие, поэтому такого множества в наивной теории нет.

Конспект: Дискретная математика