Положим |X| < |Y|, если |X| £ |Y| и не существует биекции между X и Y.

Теорема Кантора.  Для любого множества X справедливо |X| < |P(X)|, где P(X) – множество всех подмножеств множества X.

Доказательство.  Ясно, что  |X| £ |P(X)|.  Предположим, что существует биекция f: X à P(X). Рассмотрим подмножество:

A = {x Î X : x Ï f(x)}.

Если существует  y Î X,  для  которого  f(y) = A,  то  из  y Î A  будет  следовать:  y Ï f(y) = A; а из y Ï A = f(y) следует: y Î A. Отсюда нет элементов y Î X, таких, что f(y) = A, и, стало быть, f – не биекция. Теорема доказана. Эта теорема показывает, что необходимость уточнения понятия множества была известна Георгу Кантору:

Антиномия Кантора.  Предположим,  что  все  множества  составляют  некоторое множество  U. Тогда каждое подмножество  A Í U  принадлежит  U. Стало быть,  P(U) Í U и имеет место |P(U)| £ |U|, что противоречит теореме Кантора. Следовательно, собрание всех множеств не является множеством.