集合 ⑯

Def.

Prop & Proof

任意の $x\in U$ をとる。
対称差の定義より
$$ x\in A\triangle B\ \Leftrightarrow\ (x\in A\setminus B)\lor(x\in B\setminus A) $$
である。さらに差集合の定義より
$$ x\in A\setminus B\ \Leftrightarrow\ (x\in A\land x\notin B),\qquad x\in B\setminus A\ \Leftrightarrow\ (x\in B\land x\notin A) $$
であるから、
$$ x\in A\triangle B\ \Leftrightarrow\ (x\in A\land x\notin B)\lor(x\in B\land x\notin A) $$
が成り立つ。
一方、差集合の定義より
$$ x\in (A\cup B)\setminus(A\cap B)\ \Leftrightarrow\ (x\in A\cup B)\land x\notin(A\cap B) $$
である。ここで和集合と共通部分の定義より
$$ x\in A\cup B\ \Leftrightarrow\ (x\in A\lor x\in B),\qquad x\in A\cap B\ \Leftrightarrow\ (x\in A\land x\in B) $$
だから、
$$ x\in (A\cup B)\setminus(A\cap B) \ \Leftrightarrow\ (x\in A\lor x\in B)\land \neg(x\in A\land x\in B) $$
となる。ここで命題論理のド・モルガン法則と分配法則を用いると、
$$ \begin{aligned} (x\in A\lor x\in B)\land \neg(x\in A\land x\in B) &\Leftrightarrow (x\in A\lor x\in B)\land (x\notin A\lor x\notin B)\\ &\Leftrightarrow \bigl(x\in A\land (x\notin A\lor x\notin B)\bigr)\lor \bigl(x\in B\land (x\notin A\lor x\notin B)\bigr)\\ &\Leftrightarrow \bigl((x\in A\land x\notin A)\lor(x\in A\land x\notin B)\bigr)\lor \bigl((x\in B\land x\notin A)\lor(x\in B\land x\notin B)\bigr)\\ &\Leftrightarrow (x\in A\land x\notin B)\lor(x\in B\land x\notin A)\ \because\ P \lor \bot \equiv P \end{aligned} $$
が成り立つ。したがって
$$ x\in (A\cup B)\setminus(A\cap B) \ \Leftrightarrow\ (x\in A\land x\notin B)\lor(x\in B\land x\notin A) $$
である。
以上より任意の $x\in U$ について
$$ x\in A\triangle B\ \Leftrightarrow\ x\in (A\cup B)\setminus(A\cap B) $$
が成り立つので、集合の等号の定義から
$$ A\triangle B=(A\cup B)\setminus(A\cap B) $$
が従う。
$$ \Box$$

対称差の定義より
$$ A\triangle B=(A\setminus B)\cup(B\setminus A) $$
である。
ここで、差集合の公式( 証明はこちら )より
$$ A\setminus B=A\cap B^c $$
であり、同様に
$$ B\setminus A=B\cap A^c $$
を得る。
さらに、共通部分の可換律($X\cap Y=Y\cap X$ 証明はこちら )より
$$ B\cap A^c=A^c\cap B $$
である。
したがって、以上を対称差の定義式に代入して
$$ A\triangle B =(A\setminus B)\cup(B\setminus A) =(A\cap B^c)\cup(B\cap A^c) =(A\cap B^c)\cup(A^c\cap B) $$
となる。
よって
$$ A\triangle B=(A\cap B^c)\cup(A^c\cap B) $$
が成り立つ。
$$ \Box$$

対称差について既に示した公式
$$ A\triangle B=(A\cup B)\setminus(A\cap B) $$
を用いる。
また、既に示した公式 $X\setminus Y=X\cap Y^c$ を $X=A\cup B,\ Y=A\cap B$ に適用すると
$$ (A\cup B)\setminus(A\cap B)=(A\cup B)\cap(A\cap B)^c $$
が成り立つ。
さらに、ド・モルガンの法則より
$$ (A\cap B)^c=A^c\cup B^c $$
であるから、これを代入して
$$ A\triangle B =(A\cup B)\setminus(A\cap B) =(A\cup B)\cap(A\cap B)^c =(A\cup B)\cap(A^c\cup B^c) $$
を得る。
従って
$$ A\triangle B=(A\cup B)\cap(A^c\cup B^c) $$
が成り立つ。
$$ \Box$$

任意の $x\in U$ をとる。
対称差の要素による特徴付けより
$$ x\in A\triangle B\ \Leftrightarrow\ (x\in A\land x\notin B)\lor(x\in B\land x\notin A) $$
が成り立つ。
ここで命題論理の $\lor$ の可換律より
$$ (x\in A\land x\notin B)\lor(x\in B\land x\notin A) \ \Leftrightarrow\ (x\in B\land x\notin A)\lor(x\in A\land x\notin B) $$
が成り立つ。
一方、再び対称差の要素による特徴付けより
$$ (x\in B\land x\notin A)\lor(x\in A\land x\notin B)\ \Leftrightarrow\ x\in B\triangle A $$
である。
以上より、任意の $x\in U$ について
$$ x\in A\triangle B\ \Leftrightarrow\ x\in B\triangle A $$
が成り立つ。
従って集合の等号の定義より
$$ A\triangle B=B\triangle A $$
が成り立つ。
$$ \Box$$

対称差の定義より
$$ A\triangle\varnothing=(A\setminus\varnothing)\cup(\varnothing\setminus A) $$
である。
ここで、すでに示した公式( 証明はこちら )
$$ A\setminus\varnothing=A,\qquad \varnothing\setminus A=\varnothing $$
より
$$ A\triangle\varnothing=A\cup\varnothing $$
が成り立つ。
さらに、すでに示した公式( 証明はこちら )
$$ A\cup\varnothing=A $$
より
$$ A\triangle\varnothing=A $$
が従う。
$$ \Box$$

対称差の定義より
$$ A\triangle A=(A\setminus A)\cup(A\setminus A) $$
である。
ここで、既に示した命題より( 証明はこちら )
$$ A\setminus A=\varnothing $$
が成り立つから、これを代入して
$$ A\triangle A=\varnothing\cup\varnothing $$
を得る。
さらに、既に示した命題 $X\cup\varnothing=X$ ( 証明はこちら )に $X=\varnothing$ を代入すると
$$ \varnothing\cup\varnothing=\varnothing $$
である。
従って
$$ A\triangle A=\varnothing $$
が成り立つ。
$$ \Box$$

対称差の定義より
$$ A\triangle U=(A\setminus U)\cup(U\setminus A) $$
である。
ここで、$A\subseteq U$ であるから、既に示した命題より( 証明はこちら )
$$ A\setminus U=\varnothing $$
が成り立つ。また、補集合の定義と差集合の関係より( 証明はこちら )
$$ U\setminus A=A^c $$
である。
したがって
$$ A\triangle U=(A\setminus U)\cup(U\setminus A)=\varnothing\cup A^c $$
となる。さらに、$\varnothing\cup A^c=A^c$ であるから( 証明はこちら )
$$ A\triangle U=A^c $$
が成り立つ。
$$ \Box$$

任意の $x\in U$ を取る。
対称差の要素による特徴付けより、任意の集合 $X,Y\subseteq U$ について
$$ x\in X\triangle Y\ \Leftrightarrow\ (x\in X\land x\notin Y)\lor(x\in Y\land x\notin X) $$
が成り立つ。したがって、$x\in X\triangle Y$ の真偽は、$x\in X$ と $x\in Y$ の真偽だけで決まる。
ここでは $X,Y$ として $A,B,C,A\triangle B,B\triangle C$ を用いるので、結局$x\in (A\triangle B)\triangle C$ と $x\in A\triangle(B\triangle C)$ の真偽は
$x\in A,\ x\in B,\ x\in C$ の真偽だけで決まる。
そこで、次の真理表を作る。
$$ \begin{array}{|c|c|c|c|c|c|c|} \hline x\in A & x\in B & x\in C & x\in A\triangle B & x\in (A\triangle B)\triangle C & x\in B\triangle C & x\in A\triangle(B\triangle C) \\ \hline T & T & T & F & T & F & T \\ T & T & F & F & F & T & F \\ T & F & T & T & F & T & F \\ T & F & F & T & T & F & T \\ F & T & T & T & F & F & F \\ F & T & F & T & T & T & T \\ F & F & T & F & T & T & T \\ F & F & F & F & F & F & F \\ \hline \end{array} $$
したがって任意の $x\in U$ について
$$ x\in (A\triangle B)\triangle C\ \Leftrightarrow\ x\in A\triangle(B\triangle C) $$
が成り立つ。
$x\in U$ は任意であったから、集合の等号の定義より
$$ (A\triangle B)\triangle C=A\triangle(B\triangle C) $$
が成り立つ。
$$ \Box$$

任意の$x\in U$を取る。
まず左辺を変形する。
$$ \begin{aligned} x\in A\cap(B\triangle C) &\Leftrightarrow (x\in A)\land(x\in B\triangle C) &&\because\text{共通部分の定義} \\ &\Leftrightarrow (x\in A)\land\bigl((x\in B\land x\notin C)\lor(x\in C\land x\notin B)\bigr) &&\because\text{対称差の要素による特徴付け} \\ &\Leftrightarrow (x\in A\land x\in B\land x\notin C)\lor(x\in A\land x\in C\land x\notin B) &&\because\text{命題論理の分配法則} \end{aligned} $$
次に右辺を変形する。
$$ \begin{aligned} x\in (A\cap B)\triangle(A\cap C) &\Leftrightarrow \bigl(x\in A\cap B\land x\notin A\cap C\bigr)\lor\bigl(x\in A\cap C\land x\notin A\cap B\bigr) &&\because\text{対称差の特徴付け} \\ &\Leftrightarrow \bigl((x\in A\land x\in B)\land \neg(x\in A\cap C)\bigr)\lor\bigl((x\in A\land x\in C)\land \neg(x\in A\cap B)\bigr) &&\because\text{共通部分の定義} \\ &\Leftrightarrow \bigl((x\in A\land x\in B)\land \neg(x\in A\land x\in C)\bigr)\lor\bigl((x\in A\land x\in C)\land \neg(x\in A\land x\in B)\bigr) &&\because\text{共通部分の定義} \\ &\Leftrightarrow \bigl((x\in A\land x\in B)\land (x\notin A\lor x\notin C)\bigr)\lor\bigl((x\in A\land x\in C)\land (x\notin A\lor x\notin B)\bigr) &&\because\text{ド・モルガン法則} \\ \end{aligned} $$
ここで、
$$ P:=(x\in A\land x\in B),\qquad Q:=(x\notin A),\qquad R:=(x\notin C) $$
$$ P':=(x\in A\land x\in C),\qquad Q':=(x\notin A),\qquad R':=(x\notin B) $$
と見なすと、
$$ \Phi := \bigl((x\in A\land x\in B)\land (x\notin A\lor x\notin C)\bigr)\lor\bigl((x\in A\land x\in C)\land (x\notin A\lor x\notin B)\bigr) $$
は
$$ \Phi \Leftrightarrow \bigl(P\land(Q\lor R)\bigr)\lor\bigl(P'\land(Q'\lor R')\bigr) $$
ここで、命題論理の分配法則
$$ P\land(Q\lor R)\ \Leftrightarrow\ (P\land Q)\lor(P\land R) $$
を左側と右側にそれぞれ適用すると、
$$ \Phi \Leftrightarrow \bigl((P\land Q)\lor(P\land R)\bigr)\lor\bigl((P'\land Q')\lor(P'\land R')\bigr) $$
結合法則で括弧をならべ直すと、
$$ \Phi \Leftrightarrow (P\land Q)\lor(P\land R)\lor(P'\land Q')\lor(P'\land R') $$
元の式に戻すと、
$$ \Phi \Leftrightarrow \bigl((x\in A\land x\in B)\land x\notin A\bigr)\lor\bigl((x\in A\land x\in B)\land x\notin C\bigr)\lor\bigl((x\in A\land x\in C)\land x\notin A\bigr)\lor\bigl((x\in A\land x\in C)\land x\notin B\bigr) $$
さらに $\land$ の結合法則で書き直し、$x\in A\land x\notin A$は偽 (すなわち、$P \lor \bot \equiv P$であるから)
$$ \begin{aligned} \Phi &\Leftrightarrow \bigl((x\in A\land x\in B\land x\notin A)\lor(x\in A\land x\in B\land x\notin C)\bigr) \lor \bigl((x\in A\land x\in C\land x\notin A)\lor(x\in A\land x\in C\land x\notin B)\bigr)\\ &\because\ \text{命題論理の分配法則，および }\land\text{ の結合法則} \\ &\Leftrightarrow \bigl((((x\in A\land x\notin A)\land x\in B)\lor(x\in A\land x\in B\land x\notin C))\bigr)\lor\bigl((((x\in A\land x\notin A)\land x\in C)\lor(x\in A\land x\in C\land x\notin B))\bigr)\\ &\because\ \text{矛盾律の部分 }(x\in A\land x\notin A)\text{ を括り出した} \\ &\Leftrightarrow (x\in A\land x\in B\land x\notin C)\lor(x\in A\land x\in C\land x\notin B)\\ &\because\ \text{矛盾律 }(R\land\neg R)\equiv\bot\text{，}\land\text{ の零元律 }(P\land\bot)\equiv\bot\text{，}\lor\text{ の単位律 }(P\lor\bot)\equiv P \end{aligned} $$
左辺の変形結果と右辺の変形結果が一致するので、任意の$x\in U$について
$$ x\in A\cap(B\triangle C)\ \Leftrightarrow\ x\in (A\cap B)\triangle(A\cap C) $$
が成り立つ。
従って集合の等号の定義より
$$ A\cap(B\triangle C)=(A\cap B)\triangle(A\cap C) $$
が成り立つ。
$$ \Box$$

対称差の要素による特徴付け
$$ x\in A\triangle B\ \Leftrightarrow\ (x\in A\land x\notin B)\lor(x\in B\land x\notin A) $$
を用いて、両方向を示す。

1. $(\Rightarrow)$ を示す。
   $A\triangle B=\varnothing$ と仮定する。$A=B$ を示すために、$A\subseteq B$ かつ $B\subseteq A$ を示す。
   $ $
   (i) まず $A\subseteq B$ を示す。任意の $x\in U$ をとり、$x\in A$ と仮定する。
   背理法で $x\in B$ を示すため、$x\notin B$ と仮定する。すると
   $$ x\in A\land x\notin B $$
   が成り立つので、対称差の要素表示より $x\in A\triangle B$ が従う。
   しかし $A\triangle B=\varnothing$ だから、集合の等号の定義より $x\in A\triangle B\Leftrightarrow x\in\varnothing$ である。
   空集合の定義より $x\in\varnothing$ は偽であるから、$x\in A\triangle B$ は偽でなければならない。これは矛盾である。
   よって $x\notin B$ は成り立たず、$x\in B$ が成り立つ。従って $A\subseteq B$ である。
   $ $
   (ii) 次に $B\subseteq A$ を示す。任意の $x\in U$ をとり、$x\in B$ と仮定する。
   背理法で $x\in A$ を示すため、$x\notin A$ と仮定する。すると
   $$ x\in B\land x\notin A $$
   が成り立つので、対称差の要素表示より $x\in B\triangle A$ が従う。
   対称差の可換性より$A\triangle B=B\triangle A$より$x\in A\triangle B$が成り立つ。
   しかし $A\triangle B=\varnothing$ だから、集合の等号の定義より $x\in A\triangle B\Leftrightarrow x\in\varnothing$ である。
   空集合の定義より $x\in\varnothing$ は偽であるから、$x\in A\triangle B$ は偽でなければならない。これは矛盾である。
   よって $x\notin A$ は成り立たず、$x\in A$ が成り立つ。従って $B\subseteq A$ である。
   $ $
   (i) より $A\subseteq B$ であり、(ii) より $B\subseteq A$ であるから、集合の等号の定義より
   $$ A=B $$
   が成り立つ。
   $$ $$
2. $(\Leftarrow)$ を示す。
   $A=B$ と仮定する。集合の等号の定義より、任意の $x\in U$ について
   $$ x\in A\ \Leftrightarrow\ x\in B $$
   が成り立つ。
   $A\triangle B=\varnothing$ を示すために、集合の等号の定義より、任意の $x\in U$ について
   $$ x\in A\triangle B\ \Leftrightarrow\ x\in\varnothing $$
   を示せばよい。
   任意の $x\in U$ をとる。対称差の要素表示より
   $$ x\in A\triangle B\ \Leftrightarrow\ (x\in A\land x\notin B)\lor(x\in B\land x\notin A) $$
   である。
   ここで仮定 $A=B$ より、$x\in A$ ならば $x\in B$ であり、したがって $x\in A\land x\notin B$ は成り立たない。
   同様に、等号の定義より $x\in B$ ならば $x\in A$ であるから、$x\in B\land x\notin A$ も成り立たない。
   よって右辺は偽であり、$x\in A\triangle B$ は偽である。
   一方、空集合の定義より $x\in\varnothing$ も偽である。したがって
   $$ x\in A\triangle B\ \Leftrightarrow\ x\in\varnothing $$
   が成り立つ。
   以上より任意の $x\in U$ について $x\in A\triangle B\Leftrightarrow x\in\varnothing$ が成り立つので、集合の等号の定義より
   $$ A\triangle B=\varnothing $$
   が成り立つ。

-以上より
$$ A\triangle B=\varnothing\ \Leftrightarrow\ A=B $$
が成り立つ。
$$ \Box$$