Пусть А есть некоторое множество и P(A) есть множество всех подмножеств множества А. Очевидно, что A⊆P(A) и потому мощность |A|≤|P(A)|.

Теорема: (Кантора). |A|<|P(A)|.
Доказательство: Покажем, что |A|≠|P(A)|. Допустим противное. Мощность |A|=|P(A)|. Тогда существует φA→P(A). Пусть множество А₁={a принадлежит множеству А: а принадлежит множеству &phi(а)} , А₂={a принадлежит множеству А: а не принадлежит множеству φ(а)}, тогда А₂=А — А₁. Множество А₂ принадлежит P(A). φ(b) для некоторого b из множества А.

Каждый элемент из А попадает либо в А₁, либо в А₂, b принадлежит φ(b) = A₂.

Но b∈A₁ по построению А₁. Противоречие: b принадлежит A₁ и A₂. Если b принадлежит A₂, то b не принадлежит φ(b) = A₂ . Противоречие: b принадлежит A₂ и не принадлежит A₂ одновременно. Следовательно, наше предположение |A| = |P(A)|неверно и потому мощности не равны и |A| < |P(A)|. Замечание: Иногда множество P(A) всех подмножеств множества А обозначается через 2^A, тогда |P(A)| через 2^|A|. Тогда по теореме |A| < 2^|A|. По теореме Кантора, начиная от множества А, можно построить возрастающую последовательность кардинальных чисел: |A| < 2^|A| < 2^2|A|<.... Начиная с множества натуральных чисел N, можно построить возрастающую последовательность кардиналов. Она обозначается N₀ (алеф «ноль»).
N₀ < 2^N₀ = C = N₁ < 2^N₁ = N₂ < 2^N₂ = N₃ < ... , где N₀, N₁=C, N₂=2^C, N₃=2² (N – алеф, С – готическое «це») есть последовательная счетная мощность, континуум, гипер-континуум, гипер-гипер-континуум. Кантор поставил вопрос о существовании промежуточной мощности между счетной и континуумом и о существовании промежуточной мощности между N₀ и N₁ (континуум гипотезы). Гедель и Коэн показали, что обе гипотезы не могут быть доказаны (Гедель) и опровергнуты (Коэн) в аксиоматической теории множеств, то есть обе гипотезы не зависят от аксиом теории множеств.

Комментарии запрещены.