Сравнимость множеств через лемму Цорна

[Padawan]

Теорема. Любые два множества сравнимы по мощности.
Доказательство. Пусть даны два непустых множества $A$ и $B$. Рассмотрим множество $M$ всех функций $f$ таких, что область определения $D_f\subset A$, $f\colon D_f\to B$ и $f$ -- иньекция.
Для $f,g\in M$ полагаем $f\leqslant g$, если $D_f\subset D_g$ и $f=g|_{D_f}$, т.е. $g$ является продолжением $f$. Это частичный порядок.
Проверим выполнение условия леммы Цорна. Если $\{f_p: p\in I\}$ -- линейно упорядоченное подмножество, то его верхней гранью будет функция, у которой ${\mathrm {graph}} \ f = \bigcup_{p\in I} {\mathrm {graph}} \ f_p$.
Пусть $f$ -- максимальный элемент. Тогда либо $D_f=A$, либо $f(D_f)=B$, так как в противном случае найдется точка $a\in A\setminus D_f$ и точка $b\in B\setminus f(D_f)$, и можно продолжить $f$, полагая $f(a)=b$.
Теорема доказана.

Обычно по-моему эту теорему при помощи полного упорядочивания доказывают.

[Dandan]

ничего удивительного, лемма Цорна эквивалента принципу вполне упорядочивания, причем эта эквивалентность довольно проста.