互いに素な集合と対角集合の関係

by nomura · 2023年8月11日

互いに素な集合と対角集合の関係
集合$X$の部分集合$A,B\subseteq X$に対し、以下が成り立つ。
\[ A\cap B=\emptyset\Leftrightarrow\left(A\times B\right)\cap\Delta_{X}=\emptyset \]

-

$\Delta_{X}$は$X$の対角集合

$\Rightarrow$

$A\cap B=\emptyset$のとき、
\begin{align*} \left(A\times B\right)\cap\Delta_{X} & =\left(A\times B\right)\cap\left\{ \left(x,y\right)\in X\times X;x=y\right\} \\ & \subseteq\left\{ \left(x,y\right)\in A\times B;x\ne y\right\} \cap\left\{ \left(x,y\right)\in X\times X;x=y\right\} \\ & =\emptyset \end{align*} となるので、$\left(A\times B\right)\cap\Delta_{x}=\emptyset$となる。
従って$\Rightarrow$が成り立つ。

$\Leftarrow$

対偶で示す。
$A\cap B\ne\emptyset$のとき、$\left(A\times B\right)\cap\Delta_{X}\ne\emptyset$を示せばいい。
$A\cap B\ne\emptyset$なのである元$a\in X$が存在し$a\in A\land a\in B$となる。
このとき、$\left(a,a\right)\in A\times B$となり、対角集合の定義より、$\left(a,a\right)\in\Delta_{X}$なので、$\left(a,a\right)\in\left(A\times B\right)\cap\Delta_{X}\ne\emptyset$となる。
故に対偶が示されたので$\Leftarrow$が成り立つ。