直積集合 ⑬

Prop & Proof

まず、定義より
$$ (A\times B)^c=(U\times V)\setminus(A\times B)\subseteq U\times V $$
である( 証明はコチラ )。
また同様に、$A^c=U\setminus A$ より $A^c\subseteq U$ であり、$B^c=V\setminus B$ より $B^c\subseteq V$ であるから、
$$ A^c\times V\subseteq U\times V $$
かつ
$$ U\times B^c\subseteq U\times V $$
である( 証明はコチラ )。したがって、
$$ (A^c\times V)\cup(U\times B^c)\subseteq U\times V $$
である( 証明はコチラ )。
ゆえに、両辺はともに $U\times V$ の部分集合である。
したがって、外延性の原理を $U\times V$ の部分集合に対して用いれば、任意の $(x,y)\in U\times V$ について
$$ (x,y)\in (A\times B)^c \Longleftrightarrow (x,y)\in (A^c\times V)\cup(U\times B^c) $$
を示せばよい。
$ $
任意の $(x,y)\in U\times V$ を取る。このとき、直積集合の定義より
$$ x\in U\land y\in V $$
である。

1. $(x,y)\in (A\times B)^c\Rightarrow (x,y)\in (A^c\times V)\cup(U\times B^c)$ を示す
   $(x,y)\in (A\times B)^c$ と仮定する。補集合の定義より
   $$ (x,y)\in U\times V\land (x,y)\notin A\times B $$
   である。直積集合の定義より
   $$ (x,y)\in A\times B \Longleftrightarrow x\in A\land y\in B $$
   であるから、
   $$ \neg(x\in A\land y\in B) $$
   が成り立つ。命題論理のド・モルガンの法則( 証明はコチラ )より
   $$ x\notin A\lor y\notin B $$
   である。
   ここで場合分けをする。
   i) $x\notin A$ の場合。このとき、$x\in U$ かつ $x\notin A$ であるから
   $$ x\in A^c $$
   である。また $y\in V$ である。したがって、直積集合の定義より
   $$ (x,y)\in A^c\times V $$
   である。ゆえに
   $$ (x,y)\in (A^c\times V)\cup(U\times B^c) $$
   である。
   $ $
   ii) $y\notin B$ の場合。このとき、$y\in V$ かつ $y\notin B$ であるから
   $$ y\in B^c $$
   である。また $x\in U$ である。したがって、直積集合の定義より
   $$ (x,y)\in U\times B^c $$
   である。ゆえに
   $$ (x,y)\in (A^c\times V)\cup(U\times B^c) $$
   である。
   以上より
   $$ (x,y)\in (A^c\times V)\cup(U\times B^c) $$
   である。
   $ $
2. $(x,y)\in (A^c\times V)\cup(U\times B^c)\Rightarrow (x,y)\in (A\times B)^c$ を示す
   $(x,y)\in (A^c\times V)\cup(U\times B^c)$ と仮定する。和集合の定義より
   $$ (x,y)\in A^c\times V\lor (x,y)\in U\times B^c $$
   である。
   ここで場合分けをする。
   i) $(x,y)\in A^c\times V$ の場合。直積集合の定義より
   $$ x\in A^c\land y\in V $$
   である。$x\in A^c$ より $x\in U$ かつ $x\notin A$ である。したがって
   $$ x\in U\land y\in V $$
   であるから
   $$ (x,y)\in U\times V $$
   である。また $x\notin A$ であるから
   $$ \neg(x\in A\land y\in B) $$
   である。ゆえに、直積集合の定義より
   $$ (x,y)\notin A\times B $$
   である。したがって、補集合の定義より
   $$ (x,y)\in (A\times B)^c $$
   である。
   $ $
   ii) $(x,y)\in U\times B^c$ の場合。直積集合の定義より
   $$ x\in U\land y\in B^c $$
   である。$y\in B^c$ より $y\in V$ かつ $y\notin B$ である。したがって
   $$ x\in U\land y\in V $$
   であるから
   $$ (x,y)\in U\times V $$
   である。また $y\notin B$ であるから
   $$ \neg(x\in A\land y\in B) $$
   である。ゆえに、直積集合の定義より
   $$ (x,y)\notin A\times B $$
   である。したがって、補集合の定義より
   $$ (x,y)\in (A\times B)^c $$
   である。
   以上より
   $$ (x,y)\in (A\times B)^c $$
   である。

-以上の $1$ と $2$ より、任意の $(x,y)\in U\times V$ について
$$ (x,y)\in (A\times B)^c \Longleftrightarrow (x,y)\in (A^c\times V)\cup(U\times B^c) $$
である。したがって、集合の外延性より
$$ (A\times B)^c=(A^c\times V)\cup(U\times B^c) $$
が成り立つ。
$$ \Box$$

$A^c\times B^c\subseteq (A\times B)^c$ を示すため、任意の $(x,y)\in A^c\times B^c$ を取る。

1. 直積集合の定義より、
   $$ x\in A^c\land y\in B^c $$
   である。補集合の定義より、
   $$ x\in U\land x\notin A $$
   かつ
   $$ y\in V\land y\notin B $$
   である。したがって、
   $$ x\in U\land y\in V $$
   であるから、直積集合の定義より
   $$ (x,y)\in U\times V $$
   である。
   $ $
2. 次に、$(x,y)\notin A\times B$ を示す。もし
   $$ (x,y)\in A\times B $$
   であると仮定すると、直積集合の定義より
   $$ x\in A\land y\in B $$
   である。特に $x\in A$ である。しかし、上で $x\notin A$ を得ているため矛盾である。したがって、
   $$ (x,y)\notin A\times B $$
   である。

-以上より、
$$ (x,y)\in U\times V\land (x,y)\notin A\times B $$
である。ゆえに、補集合の定義より
$$ (x,y)\in (A\times B)^c $$
である。$(x,y)\in A^c\times B^c$ は任意であったから、
$$ A^c\times B^c\subseteq (A\times B)^c $$
が成り立つ。
$$ \Box$$