直積集合 ⑮

Prop&Proof

1. まず
   $$ (X\times Y)\setminus(A\times B)\subseteq ((X\setminus A)\times Y)\cup(X\times(Y\setminus B)) $$
   を示す。任意の $(x,y)\in (X\times Y)\setminus(A\times B)$ をとる。
   差集合の定義より
   $$ (x,y)\in X\times Y\ \land\ (x,y)\notin A\times B $$
   が成り立つ。
   ■　前半と直積集合の定義より
   $$ x\in X\ \land\ y\in Y $$
   　　が成り立つ。
   $ $
   ■　また、$(x,y)\notin A\times B$ であるから、直積集合の定義
   $$ (x,y)\in A\times B\ \Leftrightarrow\ (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 X$ かつ $y\in Y$ であるから
   $$ x\in X\setminus A\ \land\ y\in Y $$
   　　　　が成り立つ。
   　　　　したがって、直積集合の定義より
   $$ (x,y)\in (X\setminus A)\times Y $$
   　　　　である。
   　　　　よって
   $$ (x,y)\in ((X\setminus A)\times Y)\cup(X\times(Y\setminus B)) $$
   　　　　が成り立つ。
   $ $
   　　(ii) $y\notin B$ の場合。
   　　　　すでに $x\in X$ かつ $y\in Y$ であるから
   $$ x\in X\ \land\ y\in Y\setminus B $$
   　　　　が成り立つ。
   　　　　したがって、直積集合の定義より
   $$ (x,y)\in X\times(Y\setminus B) $$
   　　　　である。よって
   $$ (x,y)\in ((X\setminus A)\times Y)\cup(X\times(Y\setminus B)) $$
   　　　　が成り立つ。
   $ $
   以上より
   $$ (X\times Y)\setminus(A\times B)\subseteq ((X\setminus A)\times Y)\cup(X\times(Y\setminus B)) $$
   が成り立つ。
   $ $
2. 次に
   $$ ((X\setminus A)\times Y)\cup(X\times(Y\setminus B))\subseteq (X\times Y)\setminus(A\times B) $$
   を示す。任意の $(x,y)\in ((X\setminus A)\times Y)\cup(X\times(Y\setminus B))$ をとる。
   和集合の定義より
   $$ (x,y)\in (X\setminus A)\times Y\ \lor\ (x,y)\in X\times(Y\setminus B) $$
   が成り立つ。
   ここで再び場合分けを行う。
   $ $
   (i)　$(x,y)\in (X\setminus A)\times Y$ の場合。
   　　 直積集合の定義より
   $$ x\in X\setminus A\ \land\ y\in Y $$
   　　 が成り立つ。さらに差集合の定義より
   $$ x\in X\ \land\ x\notin A $$
   　　 が成り立つ。したがって
   $$ x\in X\ \land\ y\in Y $$
   　　 であるから、直積集合の定義より
   $$ (x,y)\in X\times Y $$
   　　 が成り立つ。また、もし
   $$ (x,y)\in A\times B $$
   　　 であるとすると、直積集合の定義より
   $$ x\in A $$
   　　 が成り立つが、これは $x\notin A$ に矛盾する。
   　　 したがって
   $$ (x,y)\notin A\times B $$
   　　 である。ゆえに、差集合の定義より
   $$ (x,y)\in (X\times Y)\setminus(A\times B) $$
   　　 が成り立つ。
   $ $
   (ii) $(x,y)\in X\times(Y\setminus B)$ の場合。
   　　 直積集合の定義より
   $$ x\in X\ \land\ y\in Y\setminus B $$
   　　 が成り立つ。さらに差集合の定義より
   $$ y\in Y\ \land\ y\notin B $$
   　　 が成り立つ。したがって
   $$ x\in X\ \land\ y\in Y $$
   　　 であるから、直積集合の定義より
   $$ (x,y)\in X\times Y $$
   　　 が成り立つ。また、もし
   $$ (x,y)\in A\times B $$　　
   　　 であるとすると、直積集合の定義より
   $$ y\in B $$
   　　 が成り立つが、これは $y\notin B$ に矛盾する。
   　　 したがって
   $$ (x,y)\notin A\times B $$
   　　 である。ゆえに、差集合の定義より
   $$ (x,y)\in (X\times Y)\setminus(A\times B) $$
   　　 が成り立つ。
   $ $
   以上より
   $$ ((X\setminus A)\times Y)\cup(X\times(Y\setminus B))\subseteq (X\times Y)\setminus(A\times B) $$
   　　 が成り立つ。
   $ $

-したがって
$$ (X\times Y)\setminus(A\times B)=((X\setminus A)\times Y)\cup(X\times(Y\setminus B)) $$
が成り立つ。
$$ \Box$$

1. まず
   $$ (A\times B)\setminus(C\times D)\subseteq ((A\setminus C)\times B)\cup(A\times(B\setminus D)) $$
   を示す。任意の $(x,y)\in (A\times B)\setminus(C\times D)$ をとる。
   差集合の定義より
   $$ (x,y)\in A\times B\ \land\ (x,y)\notin C\times D $$
   が成り立つ。
   $ $
   ■　前半と直積集合の定義より
   $$ x\in A\ \land\ y\in B $$
   を得る。
   $ $
   ■　また、後半より
   $$ (x,y)\notin C\times D $$
   　　である。ここで、$x\notin C$ または $y\notin D$ が成り立つことを示す。
   　　もし
   $$ x\in C\ \land\ y\in D $$
   　　であるとすると、直積集合の定義より
   $$ (x,y)\in C\times D $$
   　　が成り立つ。これは
   $$ (x,y)\notin C\times D $$
   　　に矛盾する。したがって
   $$ x\notin C\ \lor\ y\notin D $$
   　　が成り立つ。ゆえに、場合分けを行う。
   $ $
   　　(i)　$x\notin C$ の場合。
   　　　　 すでに $x\in A$ かつ $y\in B$ であるから
   $$ x\in A\setminus C\ \land\ y\in B $$
   　　　　 が成り立つ。
   　　　　 したがって、直積集合の定義より
   $$ (x,y)\in (A\setminus C)\times B $$
   　　　　 である。よって
   $$ (x,y)\in ((A\setminus C)\times B)\cup(A\times(B\setminus D)) $$
   　　　　 が成り立つ。
   $ $
   　　(ii) $y\notin D$ の場合。
   　　　　 すでに $x\in A$ かつ $y\in B$ であるから
   $$ x\in A\ \land\ y\in B\setminus D $$
   　　　　 が成り立つ。
   　　　　 したがって、直積集合の定義より
   $$ (x,y)\in A\times(B\setminus D) $$
   　　　　 である。
   よって
   $$ (x,y)\in ((A\setminus C)\times B)\cup(A\times(B\setminus D)) $$
   が成り立つ。以上より
   $$ (A\times B)\setminus(C\times D)\subseteq ((A\setminus C)\times B)\cup(A\times(B\setminus D)) $$
   が成り立つ。
   $ $
2. 次に
   $$ ((A\setminus C)\times B)\cup(A\times(B\setminus D))\subseteq (A\times B)\setminus(C\times D) $$
   を示す。任意の $(x,y)\in ((A\setminus C)\times B)\cup(A\times(B\setminus D))$ をとる。
   和集合の定義より
   $$ (x,y)\in (A\setminus C)\times B\ \lor\ (x,y)\in A\times(B\setminus D) $$
   が成り立つ。
   $ $
   再び場合分けを行う。
   (i) $(x,y)\in (A\setminus C)\times B$ の場合。
   　　直積集合の定義より
   $$ x\in A\setminus C\ \land\ y\in B $$
   　　が成り立つ。さらに差集合の定義より
   $$ x\in A\ \land\ x\notin C $$
   　　が成り立つ。したがって
   $$ x\in A\ \land\ y\in B $$
   　　であるから、直積集合の定義より
   $$ (x,y)\in A\times B $$
   　　が成り立つ。
   　　また、$(x,y)\in C\times D$ であるとすると、直積集合の定義より
   $$ x\in C $$
   　　が従うが、これは $x\notin C$ に矛盾する。よって
   $$ (x,y)\notin C\times D $$
   　　である。
   　　したがって、差集合の定義より
   $$ (x,y)\in (A\times B)\setminus(C\times D) $$
   　　が成り立つ。
   $ $
   (ii) $(x,y)\in A\times(B\setminus D)$ の場合。
   　　直積集合の定義より
   $$ x\in A\ \land\ y\in B\setminus D $$
   　　が成り立つ。さらに差集合の定義より
   $$ y\in B\ \land\ y\notin D $$
   　　が成り立つ。したがって
   $$ x\in A\ \land\ y\in B $$
   　　であるから、直積集合の定義より
   $$ (x,y)\in A\times B $$
   　　が成り立つ。
   　　また、$(x,y)\in C\times D$ であるとすると、直積集合の定義より
   $$ y\in D $$
   　　が従うが、これは $y\notin D$ に矛盾する。よって
   $$ (x,y)\notin C\times D $$
   　　である。したがって、差集合の定義より
   $$ (x,y)\in (A\times B)\setminus(C\times D) $$
   　　が成り立つ。以上より
   $$ ((A\setminus C)\times B)\cup(A\times(B\setminus D))\subseteq (A\times B)\setminus(C\times D) $$
   　　が成り立つ。
   $ $

-以上より
$$ (A\times B)\setminus(C\times D)=((A\setminus C)\times B)\cup(A\times(B\setminus D)) $$
が成り立つ。
$$ \Box$$