Теорема Кантора
Теорема Кантора — классическое утверждение теории множеств. Доказано Георгом Кантором в 1891 году. Утверждает, что любое множество [math]\displaystyle{ A }[/math] менее мощно, чем множество всех его подмножеств [math]\displaystyle{ 2^A }[/math].
Доказательство
Предположим, что существует множество [math]\displaystyle{ A }[/math], равномощное множеству всех своих подмножеств [math]\displaystyle{ 2^A }[/math], то есть, что существует такая биекция [math]\displaystyle{ f }[/math], ставящая в соответствие каждому элементу множества [math]\displaystyle{ A }[/math] некоторое подмножество множества [math]\displaystyle{ A }[/math].
Рассмотрим множество [math]\displaystyle{ B }[/math], состоящее из всех элементов [math]\displaystyle{ A }[/math], не принадлежащих своим образам при отображении [math]\displaystyle{ f }[/math][1]:
- [math]\displaystyle{ B=\left\{\,x\in A : x\not\in f(x)\,\right\} }[/math].
Отображение [math]\displaystyle{ f }[/math] биективно, а [math]\displaystyle{ B \subseteq A }[/math], поэтому существует [math]\displaystyle{ y \in A }[/math] такой, что [math]\displaystyle{ f(y) = B }[/math].
Теперь посмотрим, может ли [math]\displaystyle{ y }[/math] принадлежать [math]\displaystyle{ B }[/math]. Если [math]\displaystyle{ y \in B }[/math], то [math]\displaystyle{ y \in f(y) }[/math], а тогда, по определению [math]\displaystyle{ B }[/math], [math]\displaystyle{ y \not\in B }[/math]. И наоборот, если [math]\displaystyle{ y \not\in B }[/math], то [math]\displaystyle{ y \not\in f(y) }[/math], а следовательно, [math]\displaystyle{ y \in B }[/math]. В любом случае, получаем противоречие.
Следовательно, исходное предположение ложно и [math]\displaystyle{ A }[/math] не равномощно [math]\displaystyle{ 2^A }[/math]. Таким образом доказана строгость неравенства.
Для определения знака неравенства построим сюръективное отображение g: [math]\displaystyle{ 2^A }[/math]→ [math]\displaystyle{ A }[/math], сопоставляющее каждому подмножеству [math]\displaystyle{ 2^A }[/math], состоящему из единственного элемента, этот самый элемент из [math]\displaystyle{ A }[/math]. В [math]\displaystyle{ 2^A }[/math] остались множества (состоящие из более чем одного элемента). Отсюда можно сделать вывод, что [math]\displaystyle{ |2^A|\gt |A| }[/math].
Примечания
- ↑ Оно существует по аксиоме выделения, значение есть подмножество А.
Ссылки
- Р. Курант, Г. Роббинс Что такое математика? Глава II, § 4, С. 111—122.