演習3

(1)

集合の体は定義1で定義されたのですが,集合の体を定義1とは異なる仕方 で定義できますか？

$\cup$ と $\cap$ の双対性を使って例えば

「集合の体(field of sets) $A$ とは,次の性質(1)-(3)を満たす集合である: (1) $\cup A \in A$ (2)任意の $X \in A$ について, $\cup A \sim X \in A$ (3) 任意の $X, Y \in A$ について, $X \cap Y \in A$ 」

(2)

空でない集合 $X$ が与えられたとします.この $X$ から集合の体を作れ ますか？
　$A= \{ 0,X \}$ はその例の一つです。
　 $\cup A=0 \cup X=X$ なので, $\cup A \in A$ で定義の条件(1)が充たされ 　 $\cup A \sim X=X \sim X=0 \in A$ と $\cup A \sim 0=X \sim 0=X \in A$ により条件(2)が $0 \cup 0=0 \in A,0 \cup X=X \in A,X \cup 0=X \in A,X \cup X=X \in A$ から条件(3)が充たされています. 　　

(3)-I

1.

$A \cap (B \sim C) = (A \cap B) \sim C;$
$\lbrack 方法1 \rbrack$ 記号論理の規則は既知なものとします。
$x$ を任意にとると：

$$\begin{eqnarray*} x \in A \cap (B \sim C) &\Leftrightarrow& x \in A ~and~ x \... ...not(x \in C) \\ &\Leftrightarrow& x \in (A \cap B) \sim C \\ \end{eqnarray*}$$

$x$ は任意にとったから

$$(\forall x)(x \in A \cap (B \sim C) \Leftrightarrow x \in (A \cap B) \sim C)$$

よって

$$A \cap (B \sim C) = (A \cap B) \sim C$$

$\lbrack 方法2 \rbrack$ $\cap$ と $\cup$ と補集合 $c$ の集合演算は既知としてよいなら ただし,補集合は $A,B,C$ を部分集合としてふくむ含適当な 集合上での補集合をとるものとして

$$\begin{eqnarray*} A \cap (B \sim C) &=& A \cap (B \cap C_c) \\ &=& (A \cap B) \cap C^c\\ &=& (A \cap B) \sim C \\ \end{eqnarray*}$$

　 以下、取り合えず $\lbrack 方法1 \rbrack$ のようにします.

2.

$(A \cup B) \sim C = (A \sim C) \cup (B \sim C);$
$x$ を任意にとると：

$$\begin{eqnarray*} x \in (A \cup B) \sim C &\Leftrightarrow& x \in (A \cup B) ... ... C) \\ &\Leftrightarrow& x \in (A \sim C) \cup (B \sim C) \\ \end{eqnarray*}$$

$x$ は任意にとったから

$$(\forall x) (x \in (A \cup B) \sim C \Leftrightarrow x \in (A \sim C) \cup (B \sim C))$$

よって

$$(A \cup B) \sim C = (A \sim C) \cup (B \sim C)$$

3.

$A \sim (B \cup C)= (A \sim B) \cap (A \sim C);$

$x$ を任意にとると：

$$\begin{eqnarray*} \lefteqn{x \in A \sim (B \cup C)} \\ && \Leftrightarrow x \... ...C) \\ && \Leftrightarrow x \in (A \sim B) \cap (A \sim C) \\ \end{eqnarray*}$$

$x$ は任意にとったから

$$(\forall x)(x \in A \sim (B \cup C) \Leftrightarrow x \in (A \sim B) \cap (A \sim C))$$

よって

$$A \sim (B \cup C) = (A \sim B) \cap (A \sim C) \\$$

4.

$A \sim (B \cap C)= (A \sim B) \cup (A \sim C);$

$x$ を任意にとると:

$$\begin{eqnarray*} \lefteqn{x \in A \sim (B \cap C)} \\ && \Leftrightarrow x \... ...C) \\ && \Leftrightarrow x \in (A \sim B) \cup (A \sim C) \\ \end{eqnarray*}$$

$x$ は任意にとったから

$$(\forall x)(x \in A \sim (B \cap C) \Leftrightarrow x \in (A \sim B) \cup (A \sim C))$$

よって

$$A \sim (B \cap C) = (A \sim C) \cup (B \sim C)$$

5.

$A \sim (A \sim B) = A \cap B ;$
$x$ を任意にとると:

$$\begin{eqnarray*} \lefteqn{x \in A \sim (A \sim B)} \\ && \Leftrightarrow x \... ... \in A ~and~ x \in B \\ && \Leftrightarrow x \in A \cap B \\ \end{eqnarray*}$$

$x$ は任意にとったから

$$(\forall x)(x \in A \sim (A \sim B) \Leftrightarrow x \in A \cap B)$$

よって

$$A \sim (A \sim B) = A \cap B$$

6.

$A \cup (B \sim A) = A \cup B;$
$x$ を任意にとると:

$$\begin{eqnarray*} \lefteqn{x \in A \cup (B \sim A)} \\ && \Leftrightarrow x \... ...x \in A ~or~ x \in B \\ && \Leftrightarrow x \in A \cup B \\ \end{eqnarray*}$$

$x$ は任意にとったから

$$(\forall x)(x \in A \cup (B \sim A) \Leftrightarrow x \in A \cup B)$$

よって

$$A \cup (B \sim A) ＝ A \cup B;$$

7.

$A \cap B^c= 0 \Leftrightarrow A \subseteq B;$

[証明] 以下で,補集合は $A,B$ を含むある集合 $X$ について考えるこ とにします.

$$\begin{eqnarray*} \lefteqn{A \cap B^c= 0} \\ && \Leftrightarrow 任意の x \in ... ... A \Rightarrow x \in B ) \\ && \Leftrightarrow A \subseteq B \end{eqnarray*}$$

または以下による.

右辺を仮定すれば $B^c\subseteq A_c$ により

$$A \cap B^c\subseteq A \cap A_c=0$$

また $0 \subseteq A \cap B_c$ は常に成り立っているから

$$A \cap B^c= 0$$

左辺を仮定すれば
$A^c\supseteq B_c$ より $A^c\subseteq B_c$
すなわち $A \subseteq B$

8.

$(A \sim B)^c= A^c\cup B;$

$x$ を任意にとると：

$$\begin{eqnarray*} x \in (A \sim B)^c &\Leftrightarrow& ~not~ (x \in A \sim B) ... ... \in A^c~or~ x \in B \\ &\Leftrightarrow& x \in A^c\cup B \\ \end{eqnarray*}$$

$x$ は任意にとったから

$$(\forall x)(x \in (A \sim B)^c\Leftrightarrow x \in A^c\cup B)$$

よって

$$(A \sim B)^c= Ac \cup B;$$

9.

$(A \cap B=0 ~and~ A \cup B=C) \Rightarrow A=C \sim B.$
$(A \cap B=0 ~and~ A \cup B=C)$ を仮定し $x$ を任意にとると：

$$\begin{eqnarray*} x \in A &\Rightarrow& x \in A \cup B (A \subseteq A \cup B) \\ &\Rightarrow& x \in C (A \cup B=C) \\ \end{eqnarray*}$$

また

$$x \in A \Rightarrow ~not~x \in B (A \cap B=0)$$

よって

$$\begin{eqnarray*} x \in A &\Rightarrow& x \in C ~and~ not~ x \in B \\ &\Rightarrow& x \in C \sim B \\ \end{eqnarray*}$$

逆に,

$$\begin{eqnarray*} \lefteqn{x \in C \sim B} \\ && \Rightarrow x \in C ~and~ no... ...~ (x \in B ~and~ not~ x \in B) \\ && \Rightarrow x \in A \\ \end{eqnarray*}$$

$x$ は任意にとったから

$$(\forall x)(x \in C \sim B \Leftrightarrow x \in A)$$

よって

$$C \sim B = A$$

これは $(A \cap B=0 ~and~ A \cup B=C)$ を仮定して得られたから

$$(A \cap B=0 ~and~ A \cup B=C) \Rightarrow A=C \sim B.$$

(3)-II

$A {\bf\Delta} B = (A \sim B) \cup (B \sim A)$ を対称差といいます.論理回路 をやった方は EX-OR(排他的論理和)に対応するものです. (f)で $A {\bf\Delta} B$ がどういうものかよくわかりますね． この ${\bf\Delta}$ の挙動をみて,あれっと思いませんか？

1. $A {\bf\Delta} B = B {\bf\Delta} A;$ 　　
   
   $$A {\bf\Delta} B=(A \sim B) \cup (B \sim A)=(B \sim A) \cup (A \sim B)=B {\bf\Delta} A ＃\cup は交換可能$$
   
   

2. $(A {\bf\Delta} B) {\bf\Delta} C = A {{\bf\Delta}} (B {\bf\Delta} C);$
   $$\begin{eqnarray*} \lefteqn{(A {\bf\Delta} B) {\bf\Delta} C} \\ && = ((A \sim ... ...\\ && \mbox{ } \cup {C \sim ((A \sim B) \cup (B \sim A))} \\ \end{eqnarray*}$$
   
   
   
   
   
   
   以後根気良く計算をすれば
   
   $$=(A \cap B \cap C) \cup (A \cap B^c\cap C_c) \cup (A^c\cap B \cap C_c) \cup (A^c\cap B^c\cap C)$$
   
   
   また
   $$\begin{eqnarray*} \lefteqn{A {\bf\Delta} (B {\bf\Delta} C)} \\ && =( A \cap B... ...p C_c) \cup (A^c\cap B \cap C_c) \cup (A^c\cap B^c\cap C) \\ \end{eqnarray*}$$
   
   
   
   
   
   
   よって
   
   $$(A {\bf\Delta} B) {\bf\Delta} C=A {\bf\Delta} (B {\bf\Delta} C)$$
   
   

   [別解] : 下の(f) $A {\bf\Delta} B=(A \cup B) \sim (A \cap B).$ を用いて

   $$\begin{eqnarray*} \lefteqn{(A {\bf\Delta} B) {\bf\Delta} C} \\ && =(A {\bf\De... ...c\cup C) \sim \{ (A {\bf\Delta} B) \cap C \} \quad (*1) \\ 　 \end{eqnarray*}$$
   
   
   
   
   
   
   $$\begin{eqnarray*} \lefteqn{\{ (A {\bf\Delta} B) \cap C \} } \\ && = \{ A \cap... ...\cap C \cap B^c\} \cup \{ B \cap C \cap A^c\} \qquad (*2) \\ \end{eqnarray*}$$
   
   
   
   
   
   
   (*1)(*2)から
   $$\begin{eqnarray*} \lefteqn{(A {\bf\Delta} B) {\bf\Delta} C} \\ && = (A \cup B... ...\qquad \cap (A^c\cup B \cup C_0) \cap (A^c\cup B^c\cup C) \\ \end{eqnarray*}$$
   
   
   
   
   
   
   同様に
   $$\begin{eqnarray*} \lefteqn{(A {\bf\Delta} B) {\bf\Delta} C} \\ && = ( A \cup ... ...\qquad \cap (A^c\cup B \cup C_c) \cap (A^c\cup B^c\cup C) \\ \end{eqnarray*}$$
   
   
   
   
   
   

3. $A {\bf\Delta} B = 0 \Leftrightarrow A = B;$
   まず $A=B$ なら
   
   $$A {\bf\Delta} B = (A \sim B) \cup (B \sim A) = 0 \cup 0=0$$
   
   
   　 逆に 　 $(A \sim B) \cup (B \sim A)=A {\bf\Delta} B=0$ なら 　
   
   $$(A \sim B)=0,(B \sim A)=0$$
   
   
   となるから 　 $A \cup B=(A \sim B) \cup B=0 \cup B=B$ より
   
   $$A \subseteq A \cup B=B$$
   
   
   となり, 同様に 　 $A \cup B=(B \sim A) \cup A=0 \cup A=A$ より
   $$\begin{eqnarray*} && B \subseteq A \cup B=A \\ && A=B \\ \end{eqnarray*}$$
   
   
   
   
   
   

4. $A {\bf\Delta} 0 = A;$
   
   $$A {\bf\Delta} 0 =(A \sim 0) \cup (0 \sim A)=A \cup 0=A$$
   
   

5. $A \cap (B {\bf\Delta} C)=(A \cap B) {\bf\Delta} (A \cap C);$
   $$\begin{eqnarray*} \lefteqn{A \cap (B {\bf\Delta} C)} \\ && = A \cap \{ (B \si... ... \sim C \} \cup \{ (A \cap C) \sim B \} \qquad ((3)-I (a)) \\ \end{eqnarray*}$$
   
   
   
   
   
   

   ここで(3)-I (d)より

   $$\begin{eqnarray*} (A \cap B) \sim (A \cap C) &=& \{ (A \cap B) \sim A \} \cup ... ...up \{ (A \cap B) \sim C \} \\ &=& \{ (A \cap B) \sim C \} \\ \end{eqnarray*}$$
   
   
   
   
   
   
   $$\begin{eqnarray*} (A \cap C) \sim (A \cap B) &=& \{ (A \cap C) \sim A \} \cup ... ...up \{ (A \cap C) \sim B \} \\ &=& \{ (A \cap C) \sim B \} \\ \end{eqnarray*}$$
   
   
   
   
   
   

   となるので, 結局

   $$\begin{eqnarray*} \lefteqn{A \cap (B {\bf\Delta} C)} \\ && = \{(A \cap B) \si... ...m (A \cap B) \} \\ && = (A \cap B) {\bf\Delta} (A \cap C) \\ \end{eqnarray*}$$
   
   
   
   
   
   

6. $A {\bf\Delta} B=(A \cup B) \sim (A \cap B).$
       (3-I-(d)) $\; \; A \sim (B \cap C) = (A \sim B) \cup (A \sim C)$ により
   $$\begin{eqnarray*} (A \cup B) \sim (A \cap B) &=& \{ (A \cup B) \sim A \} \cup ... ...) \cup (A \sim B) \qquad (3-I-(f)) \\ &=& A {\bf\Delta} B \\ \end{eqnarray*}$$