Диагональ множества: интересная задача из теории множеств.

[ProPupil]

Пусть $Y$ - множество, а $2^Y$ - множество всех его подмножеств. Докажите, что если мощность $Y$ превышает мощность континуума, то диагональ $\Delta_Y = \{y \in Y: (y,y)\}$ не принадлежит множеству $2^Y \times 2^Y$, т. е. $\Delta_Y \not \in 2^Y \times 2^Y$.

[provincialka]

Непонятно даже без континуума. Элементы диагонали $Y$ принадлежат $Y\times Y$, а не $2^Y \times 2^Y$. Хм...

[AlexDem]

Однако же вопрос был не об элементах, а о самой диагонали как множестве.

[ProPupil]

Верно, вопрос о самой диагонали. Добавил формализованную запись отсутствия принадлежности.

[NSKuber]

Но диагональ - множество пар, а $2^Y \times 2^Y$ - множество пар подмножеств. Как множество пар элементов $Y$ превращается в пару подмножеств $Y$?

[ProPupil]

Подмножества из одного элемента, к примеру? Хотя, конечно, в доказательстве утверждения всё куда веселее.

[NSKuber]

Распишем множества:
$\Delta_y = \{(y,y): y\in Y\}=\{\{\{y\},\{y,y\}\}: y\in Y\}=\{\{\{y\}\}: y\in Y\}=\{\{\{y_1\}\},\{\{y_2\}\},\ldots\}$.
Пусть $s \in 2^Y \times 2^Y$. Тогда $s=(A,B)$, где $A\subseteq Y, B\subseteq Y$.
$s=(A,B)=\{\{A\},\{A,B\}\}$.
Если $|Y|>2$, то $|\Delta_y|=|Y|>2$, а $|s|\leq 2$, противоречие.
Вот доказательство, и не то, что континуальности, бесконечности не надо.

[ProPupil]

Здесь могу привести следующий контрпример:

Если $Y$ конечна, то $2^Y$ образует алгебру множеств.

Т. е. $2^Y \times 2^Y$ есть произведение алгебр, что образует алгебру.

Соответственно, к примеру $\Delta_Y = \{0\}\times\{0\} \cup \{1\}\times\{1\} \cup \{2\}\times\{2\} \in 2^Y \times 2^Y$ в силу алгебры.