基本的な命題

前節までに,ブール代数の初等算術とも言うべき色々な定理を証明していただきました (ここで,定理とはブール代数において証明された式のこと.).
まずそれを数字が前後しますが, 命題6 (その1) として証明付きでまとめておきましょう. (演習等で証明された方も,もう一度復習をかねて目を通しておいてください. やり方等,参考になるでしょう.) 命題6(その1)の内容は,今後,特にことわらず自由に用いることにします。

[命題6]

(その1)

$x+x =x; \quad$ (べき等律)
$x \cdot x =x; \quad$ (べき等律)
$x \leq x; \quad$ (反射律)
$(x \leq y ~and~ y \leq x) \Rightarrow x=y; \quad$ (反対称律)
$(x\leq y ~and~ y \leq z) \Rightarrow x \leq z; \quad$ (推移律)
$x \leq y \Leftrightarrow x \cdot y=x;$
$x \cdot 0=0;$
$x \cdot 1=x;$
$x \leq y \Leftrightarrow x \cdot -y=0;$
$x=-y \Leftrightarrow (x+y=1 ~and~ x \cdot y=0); \quad$ (補元の一意性)
$--x =x; \quad$ (二重否定の法則)
$-(x+y)= -x \cdot -y; \quad$ (ド・モルガンの法則)
$-(x \cdot y)= -x+-y; \quad$ (ド・モルガンの法則)
$0 \leq x \leq 1;$
$(x \leq z ~and~ y \leq z ) \Rightarrow x+y \leq z;$
$(x \leq y ~and~ y \leq z) \Rightarrow x \leq y \cdot z.$

(命題6(その1)終わり)

[命題6]

(その1)の証明

$\begin{eqnarray*} x & = & x \cdot x+x \quad 定義3(2)(暲) \\ & = & x+x \cdot x \... ...\cdot x \quad 定義3(2)(暙) \\ & = & x+x \quad 定義3(2)(暲) \\ \end{eqnarray*}$
双対の原理を(1)に適用して, $x \cdot x =x.$
(1) から,定義により $x \leq x.$
$x \leq y$ と $y\leq x$ を仮定する. $\leq$ の定義から,定義 3(2)(i)によって,
$x \leq y$ と $y \leq z$ を仮定する. $\leq$ の定義から, 従って,結合律(定義3(2)(ii))を用いて,

$\begin{displaymath}x+z=x+(y+z)=(x+y)+z=y+z=z \end{displaymath}$

がいえる.すなわち, $x \leq z$ を得る.
$( \Rightarrow )x \leq y$ を仮定する. $\leq$ の定義から, 定義3(2)(iii)から, $x \cdot y=x \cdot (x+y)=x.$
( $\Rightarrow$ の逆) 今上で, $x+y=y \Rightarrow x \cdot y=x$ を証明した.これに双対の原理を適用すると, $x \cdot y=y \Rightarrow x+y=x$ を得る.ここで, を置き換えると, $y \cdot x=x \Rightarrow y+x=y.$ これはすなわち, $x \cdot y=x \Rightarrow x \leq y$ である.
$\begin{eqnarray*} x \cdot 0 &=& x \cdot (x \cdot -x) \quad 定義3(2)(v) \\ &=& (... ...ad 定義3(2)(ii) \\ &=& x \cdot -x=0 \quad (2)と定義3(2)(v) \\ \end{eqnarray*}$
$\begin{eqnarray*} x \cdot 1 &=& x \cdot (x+-x) \quad 定義3(2)(v) \\ &=& (-x+x) \cdot x \quad 定義3(2)(i) \\ &=& x \quad 定義3(2)(iii) \\ \end{eqnarray*}$
双対の原理を(8)に適用して
双対の原理を(7)に適用して
$( \Rightarrow )x \leq y$ を仮定する.(6)から, $x \cdot y= x.$ これを用いて,

$\begin{eqnarray*} x \cdot (-y) &=& (x \cdot y) \cdot (-y) \\ &=& x \cdot (y \c... ...ad 定義3(2)(ii) \\ &=& x \cdot 0=0 \quad (7)と定義3(2)(v) \\ \end{eqnarray*}$

$( \Rightarrow の逆)x \cdot -y=0$ を仮定する.すると,

$\begin{eqnarray*} x \cdot y &=& x \cdot y+0 \quad (9) \\ &=& x \cdot y+x \cdot ... ...d 定義3(2)(iv) \\ &=& x \cdot 1 = x \quad (8)と定義3(2)(v) \\ \end{eqnarray*}$

がいえる.(4) から, $x \leq y$ が成立する.
$( \Rightarrow )x=-y$ を仮定する.これと定義3(2)(i)と(v)から, がいえる.また同様に,定義3(2)(i)と(v)から, $x \cdot y=-y \cdot y=y \cdot -y=1$ がいえる.
$( \Rightarrow の逆)x+y=1$ と $x \cdot y=0$ を仮定する.そのとき,

$\begin{eqnarray*} x &=& x \cdot 1 \quad (8) \\ &=& x \cdot (y+-y) \quad 定義3(2... ...&=& 1 \cdot -y \quad 仮定 \\ &=& -y \quad (8)と定義3(2)(i) \\ \end{eqnarray*}$
定義3(2)(v)と(12)から, を得る.
まず,

$\begin{eqnarray*} x+y+-x \cdot -y &=& x+(x+-x) \cdot y+-x \cdot -y \quad 定義3... ...=& x+-x \quad (8)と定義3(2)(v) \\ &=& 1 \quad 定義3(2)(v) \\ \end{eqnarray*}$

$\begin{eqnarray*} (x+y) \cdot -x \cdot -y &=& x \cdot -x \cdot -y+y \cdot -x \cd... ...(iv) \\ &=& 0+0 \quad (7)と定義3(2)(i) \\ &=& 0 \quad (9) \\ \end{eqnarray*}$

がいえる.上の２式に(12)を適用して,ド・モルガンの法則 $-(x+y)= -x \cdot -y$ が成立する.
双対の原理を(14)のド・モルガンの法則に適用して,もう一つのド・モルガンの法則 $-(x \cdot y)= -x+-y$ を得る.
(9)と定義3(2)(i)から, $0 \leq x$ がいえる.(10) から, $x \leq 1.$ 従って, $0 \leq x \leq 1.$
$x \leq z$ と $y \leq z$ を仮定する. $\leq$ の定義から, 従って,結合律(定義3(2)(ii))を用いて,

$\begin{displaymath}(x+y)+z=x+(y+z)=x+z=z \end{displaymath}$

がいえる.これが証明すべきことであった.
$x \leq y$ と $x \leq z$ を仮定する.(6)から, $x \cdot y=x,x \cdot z=x.$ 従って,これを用いて結合律(定義3(2)(ii))から,

$\begin{displaymath}x \cdot (y \cdot z)=(x \cdot y) \cdot z=x \cdot z=z \end{displaymath}$

がいえる.これが証明すべきことであった.(注:(18)は(17)に双対の原理を適用して導くこともできる)

[命題6(その１)の証明終わり]

もう少し,ブール代数の初等的な性質を見てみましょう.

[命題6]

(その2)

$x \leq x+y,y \leq x+y;$
$x \cdot y \leq x,x \cdot y \leq y ;$
$x \leq y \Rightarrow x \cdot a \leq y \cdot a;$
$x \leq y \Rightarrow x+a \leq y+a;$
$-x \leq y \Leftrightarrow x+y=1;$
$x \leq -y \Leftrightarrow x \cdot y=0;$
$x \leq y \Rightarrow -y \leq -x .$

(命題6(その2)終わり)

[命題6]: (その2)の証明
(演習10)を参照.

[命題6(その2)の証明終わり]

少し,ウォーミングアップをしましょう.

(演習10): 命題6(その2)を証明しなさい.

(演習10の終わり)

さて,ブール代数は束論(lattice theory)の方から特徴付けできます。
つまり,ブール代数は相補的な分配束として定義することができます。
それについて少し触れておきましょう.少し長い準備が必要です。
この節はその準備で終わってしまいます。
次節で, ブール代数を相補的な分配束として定義しましょう. まず,束を定義したいのですが,そのために半順序の概念が必要です。
(順序に関して,定義が分散すると嫌なので,下でかなりまとまって書いてしまいます。
そのため,順序について慣れていない方はつらいと思います。
しかし,これ以後(できれば次回も),逐次演習など入れていきますのでだんだんに慣れていってください.)

半順序集合((partially ordered set,略してよく poset (ポーセットと読む)といわれる) とは, 集合と次の (1) $\sim$ (3)を満足する上の2項関係 $\leq$ の組 $(P, \leq)$ のことです: 任意の $x,y,z \in P$ について,

$x \leq x;$ (反射律)
$(x \leq y ~and~ y \leq x ) \Rightarrow x=y;$ (反対称律)
$( x \leq y ~and~ y \leq z ) \Rightarrow x \leq z.$ (推移律)

このとき, $\leq$ は順序関係 (order relation),特に( 上の)(半)順序((partial) order)といいます。

が空集合のときも定義できるものとします。
また,明らかに混乱が起きない場合,( $P,\leq$ )を単にと書きます。
を集合を要素とする集合とすると,集合間の包含関係 $\subseteq$ は明らかに順序関係となり, $(P,\subseteq)$ は半順序集合です。
また, $x \leq y$ を $y \geq x$ とも書くことにします。

この定義から,命題6(その1)によって,ブール代数で定義された $\leq$ に関して, $(A,\leq)$ は半順序集合になります。
任意の集合について, $(P(X), \subseteq)$ も半順序集合です。

$(P, \leq)$ を半順序集合とします。
をの部分集合とします。
このとき, $\leq'$ を $\leq$ を上で考えたものとすれば, $(P, \leq')$ は半順序集合になります。
この $(P, \leq')$ を単に, $(Q, \leq)$ で表すことにします。
$(Q, \leq)$ は $(P, \leq)$ の部分半順序集合といいます。

をブール代数 ${\cal A}$ の部分宇宙とします。
で定義された $\leq$ に関して, $(B ,\leq)$ は $(A,\leq)$ の部分半順序集合になります。

$(P, \leq)$ を半順序集合とします。
の要素は全ての $x\in P$ について, $x \leq a$ となるとき,最大元といいます。
同様に, の要素は全ての $x\in P$ について, $a \leq x$ となるとき,最小元といいます。
は常に最大元または最小元を持つとは限りません.
の最大元が存在するときはそれを1で,最小元が存在するときはそれを0で表します。

(演習11)

半順序集合とみたブール代数では最大元,最小元は存在しますか? もし存在するならば,それは何ですか?
最小元を持つが,最大元を持たない半順序集合の例を挙げなさい.
最大元を持つが,最小元を持たない半順序集合の例を挙げなさい.
最大元も,最小元も持たない半順序集合の例を挙げなさい.
最大元(最小元)が存在するとき,その一意性を証明しなさい.

(演習11の終わり)

半順序集合 $(P, \leq)$ の,元は, $( x \leq y ~or~ y \leq x )$ がいえるとき,比較可能であるといいます。
の部分集合は, の全ての2つの元が比較可能なとき,連鎖(または,鎖)(chain) といいます。
自身が連鎖のとき, $(P, \leq)$ を全順序集合 (totally ordered set), あるいは,線形順序集合(linearly ordered set)といいます。
そのとき, $\leq$ は ( 上の) 全順序(total order),あるいは線形順序(linear order)といいます。

任意の要素 $x,y \in P$ について, $x \leq y$ または $y\leq x$ のいずれかが成り立つとき, $(P, \leq)$ を全順序集合であるというわけです。
「任意の要素 $x,y \in P$ について, $x \leq y$ または $y\leq x$ のいずれかが成り立つ」というところは, 「任意の要素 $x,y \in P$ について, 」といってもかまいません.
ここで, は $(x \leq y ~and~ x \ne y)$ によって定義されます。
上と同様, をとも書くことにします。

実数全体の集合,有理数全体の集合,整数全体の集合などは,普通の順序で考えて全順序集合です。

(演習12): 全順序集合でない半順序集合の例を挙げなさい.

(演習12の終わり)

を半順序集合の部分集合とします。
の要素は,全ての $m \in M$ について, $m \leq s (s \leq m)$ を満足するとき, の上界(下界)と呼ばれ, $M \leq s (s \leq M)$ と書きます。
に上界(下界)が存在するとき, は上に(下に)有界であるといいます。
は上界を持たないこともあるし, 無限個の上界を持つこともあります。
これは下界についても同様です。
特に, が最小の上界(最大の下界)であるとき, の上限(下限)といいます。
それらの英語は,上界(upper bound), 下界(lower bound),上限(supremum),下限(infinimum) です。

の上限(下限)であるとき, $s= \Sigma M (s= \Pi M)$ ( $\Pi$ は $\pi$ の大文字)で表します。
$s= \Sigma M (s= \Pi M)$ を, $s= \sup M$ や $s= \cup M (s= \inf M や s= \cap M)$ で表すことも多いです。

(演習13): 上限(下限)は存在すれば,一意的に決まることを証明しなさい.

(演習13の終わり)

(演習14)

を自然数全体の集合とします。

を

の有限部分集合の全体とします。

を

の部分集合

で,

または $Nat \sim E$ が有限になるもの全体の集合とします。
さらに,

を

の有限部分集合で偶数のみからなる集合全体の集合とします。
このとき,半順序集合 $(P(Nat), \subseteq)$ とその部分半順序集合 $(Fin, \subseteq),(Cofin+, \subseteq),(FinEven, \subseteq)$ を考えます。
$FinEven \subseteq Fin \subseteq Cofin+ \subseteq P(Nat)$ は明らかです。
このとき,

は $(Fin, \subseteq)$ では上界を持たないが, $(Cofin+, \subseteq)$ では無限個の上界を持つことを確かめなさい.
また, $(P(Nat), \subseteq)$ では,偶数全体の集合がの上限になっていることを確かめなさい.

(演習14の終わり)

半順序集合の要素(元) が, となる $x\in P$ が存在しないとき, の極大元といいます。
同様に, の要素(元) がとなる $ｘ \in P$ が存在しないとき, の極小元といいます。
極大元(極小元)はないこともありますし,1つあるいは複数個あることもあります。
が最大元(最小元)を持つとき,それはただ一つの極大元(極小元)となります。

ちょっと寄り道ですが,半順序集合が帰納的順序集合 (inductively ordered set) であるとは, $P \ne 0$ であって, の任意の空でない全順序部分集合(=連鎖)が上に有界である(上界が存在する)であることをいいます。

ここで,数学の証明に良く用いる有名な (ツォルン) の補題を紹介しましょう.それは, 「半順序集合が帰納的順序集合ならば, は極大元を持つ.」です。
これは集合論の選択公理と同値になります。
選択公理とは,集合論の悩ましい(?) 公理で,「2つずつ互いに素な空でない集合からなる集合が与えられているとき, 次の条件を満たす集合が存在する:任意の $X \in A$ について, $S \cap X= \{ Y \}$ となる集合が存在する.」というものです。
選択公理には色々なバージョンがあります。
選択公理は証明するときの良い道具になるのですが,悩ましいというのは,これから,常識外のことが導き出せるからです。
たとえば,球を適当に分割してまた寄せ集めると,元の球と全く同じ球を2つ作れるという,バナッハ・タルスキーのパラドックスが選択公理から証明できます。
これについては,

砂田利一著「バナッハ・タルスキーのパラドックス」岩波書店　1997年という本があります。
砂田さんは数学者として著名な方です。
たしか,志賀浩二著「無限からの光芒ポーランド学派の数学者達」日本評論社　1988年
にも,その記述があったように記憶しています。
はっきり記憶していませんが.志賀さんも数学者として著名な方です。
上の2冊とも昔,書店でパラパラと見ただけなので本当に推薦すべき書物かどうかはわかりません.
著名な方が書いておられるので大丈夫だとは思います。
洋書でも,バナッハ・タルスキーのパラドックスのみについて書かれたものを見たことがあります。
Banach-Tarski Pradox というタイトルだったかな.忘れました.

選択公理については,(真打登場!) 田中尚夫さんの, 田中尚夫著「選択公理と数学(増補版)」遊星社　1999年

に詳しい記述があります。
また,選択公理のみを扱った数理論理学の専門書 (洋書) (The Axiom of Choice)が North-Holland社から2冊出ています。
田中さんの本はまたしてもお薦めです。
我々のブール代数とも関係があります。
機会があれば見てみてください.(田中さんの本にもバナッハ・タルスキーのパラドックスが, 今述べたものとはすこし異なるかたちで載っています。 )

このセミナーでも,近い将来,ツォルンの補題を用いて重要な定理を証明します。
さて,寄り道から本道に戻りましょう.

半順序集合 $(L, \leq)$ において,任意の2元 $x,y \in L$ について, 集合 $\{x,y \}$ の上限および下限が ( の中で)存在するとき, を束(lattice)といいます。
空集合0,あるいはただ一つの要素からなる半順序集合もそれぞれ束をなします。
特に後者を単位束といいます。
$\{x,y \}$ の上限,下限をそれぞれ, $x+y,x \cdot y$ と表します。
+と $\cdot$ の替わりに,それぞれ, $\cup$ と $\cap$ とか, $\lor$ と $\land$ を使うことも多いです。
束に関しても,双対の原理が成り立ちます。
(注: $x \leq y$ の双対命題は, $y\leq x$ です。 )