Теорема Кантора

Теорема Кантора — классическое утверждение теории множеств. Доказано Георгом Кантором в 1891 году. Утверждает, что любое множество A {displaystyle A} менее мощно, чем множество всех его подмножеств 2 A {displaystyle 2^{A}} .

Доказательство

Предположим, что существует множество A {displaystyle A} , равномощное множеству всех своих подмножеств 2 A {displaystyle 2^{A}} , то есть, что существует такая биекция f {displaystyle f} , ставящая в соответствие каждому элементу множества A {displaystyle A} некоторое подмножество множества A {displaystyle A} .

Рассмотрим множество B {displaystyle B} , состоящее из всех элементов A {displaystyle A} , не принадлежащих своим образам при отображении f {displaystyle f} :

B = { x ∈ A : x ∉ f ( x ) } {displaystyle B=left{,xin A:x ot in f(x), ight}} .

Отображение f {displaystyle f} биективно, а B ⊆ A {displaystyle Bsubseteq A} , поэтому существует y ∈ A {displaystyle yin A} такой, что f ( y ) = B {displaystyle f(y)=B} .

Теперь посмотрим, может ли y {displaystyle y} принадлежать B {displaystyle B} . Если y ∈ B {displaystyle yin B} , то y ∈ f ( y ) {displaystyle yin f(y)} , а тогда, по определению B {displaystyle B} , y ∉ B {displaystyle y ot in B} . И наоборот, если y ∉ B {displaystyle y ot in B} , то y ∉ f ( y ) {displaystyle y ot in f(y)} , а следовательно, y ∈ B {displaystyle yin B} . В любом случае, получаем противоречие.

Следовательно, исходное предположение ложно и A {displaystyle A} не равномощно 2 A {displaystyle 2^{A}} . Таким образом доказана строгость неравенства.

Для определения знака неравенства, построим сюръективное отображение g: 2 A {displaystyle 2^{A}} → A {displaystyle A} , сопоставляющее каждому подмножеству 2 A {displaystyle 2^{A}} , состоящему из единственного элемента, этот самый элемент из A {displaystyle A} . В 2 A {displaystyle 2^{A}} остались множества (состоящие из более чем одного элемента). Отсюда можно сделать вывод, что | 2 A | > | A | {displaystyle |2^{A}|>|A|} .