Boole代数

1. 集合 $X$ の冪集合 $\mathcal{P}(X)$ は、$\vee=\cup$、$\wedge=\cap$、$A'=X\setminus A$、$0=\emptyset$、$1=X$ によって Boole 代数である（冪集合 の記事の命題「冪集合は完備Boolean代数である」）。順序は包含関係 $\subset$ であり、原子は 1 点集合 $\{x\}$ である。
2. 2 元集合 $\{0,1\}$ に、$x\vee y=\max\{x,y\}$、$x\wedge y=\min\{x,y\}$、$0'=1$、$1'=0$ を入れたものを $\mathbf{2}$ と書く。$0$ を偽、$1$ を真と読むと、$\vee,\wedge,{}'$ は論理和・論理積・否定の真理値表そのものである。$\mathbf{2}$ は 1 点集合の冪集合 $\mathcal{P}(\{\ast\})$ と同型である（$\emptyset\mapsto0$、$\{\ast\}\mapsto1$）。

$n$ を相異なる素数 $p_1,\dots,p_k$ の積（平方因子をもたない正の整数）とし、$n$ の正の約数全体を $D(n)$ とする。$d\vee e:=\operatorname{lcm}(d,e)$、$d\wedge e:=\gcd(d,e)$、$d':=n/d$、$0:=1$、$1:=n$ とすると、$D(n)$ は Boole 代数であり、$S=\{p_1,\dots,p_k\}$ の冪集合と同型である。
実際、素因数分解の一意性により、$n$ の約数 $d$ は $S$ のある部分集合 $T$ の元の積としてただ一通りに書け、$\psi(d):=T$（$d$ を割り切る素数の集合）とおくと $\psi\colon D(n)\to\mathcal{P}(S)$ は全単射である。$d\mid e$ と $\psi(d)\subset\psi(e)$ は同値なので、整除の順序での最大下界・最小上界である $\gcd$・$\operatorname{lcm}$ は $\cap$・$\cup$ に対応する：$\psi(\gcd(d,e))=\psi(d)\cap\psi(e)$、$\psi(\operatorname{lcm}(d,e))=\psi(d)\cup\psi(e)$。また $\psi(n/d)=S\setminus\psi(d)$、$\psi(1)=\emptyset$、$\psi(n)=S$ である。よって $D(n)$ の演算は $\mathcal{P}(S)$ の演算を $\psi$ で写したものであり、Boole 代数の条件は $\mathcal{P}(S)$ から移る。$n=30$ なら $S=\{2,3,5\}$ で、$6\mapsto\{2,3\}$、$6'=5\mapsto\{5\}$ である。

$D(12)=\{1,2,3,4,6,12\}$ に $\gcd$・$\operatorname{lcm}$ を入れた束は、最小元 $1$ と最大元 $12$ をもつ分配束だが、Boole 代数ではない。分配律は、約数 $2^a3^b$ を指数の組 $(a,b)$（$0\le a\le2$、$0\le b\le1$）で表すと $\gcd$・$\operatorname{lcm}$ が成分ごとの $\min$・$\max$ になり、全順序集合の上では $\min\{x,\max\{y,z\}\}=\max\{\min\{x,y\},\min\{x,z\}\}$ が（$y,z$ の大小で場合を分ければ）成り立つことから従う。しかし $2$ には補元がない。$\gcd(2,c)=1$ となる約数は $c=1,3$ だけで、$\operatorname{lcm}(2,1)=2$、$\operatorname{lcm}(2,3)=6$ はどちらも $12$ でない。$6$ についても $\gcd(6,c)=1$ となるのは $c=1$ だけで、$\operatorname{lcm}(6,1)=6\neq12$ である。満たす性質：最小元・最大元をもつ分配束。満たさない性質：すべての元が補元をもつ。破る含意：「有界な分配束 $\Rightarrow$ Boole 代数」は成り立たない。$12$ が平方因子 $4$ をもつことが原因で、元の個数 $6$ が $2$ の冪でないことからも（thm-boolean-algebra-finite により）Boole 代数でないと分かる。

束 の記事の注意「非分配束」の $M_3$（最小元 $0$、最大元 $1$ と、その間の互いに比較できない 3 元 $a,b,c$）では、$a\wedge b=0$、$a\vee b=1$、$a\wedge c=0$、$a\vee c=1$ なので、$b$ も $c$ も $a$ の補元の条件を満たす。すなわち補元が一意でない。満たす性質：最小元・最大元をもち、各元が補元の条件を満たす元をもつ。満たさない性質：分配律。この例は、次の prop-boolean-algebra-complement で補元が一意になるのに分配律が効いていることを示す。

自然数全体 $\mathbb{N}$ の部分集合のうち、有限集合であるか、補集合が有限であるもの全体を $\mathcal{F}$ とする。$\mathcal{F}$ は $\cup,\cap$ と補集合で閉じ、$\emptyset,\mathbb{N}$ を含む（Boole環 の記事の例「有限または補有限な部分集合の環」と同じ集合族）。有限集合どうし・補有限集合どうし・有限と補有限の和や共通部分を場合分けすれば確かめられる。したがって $\mathcal{F}$ は $\mathcal{P}(\mathbb{N})$ の演算を制限した Boole 代数である。$\mathcal{F}$ は無限集合だが可算集合である（有限部分集合は可算個であり、補有限集合は有限集合の補集合として可算個ある）。一方、ある集合 $X$ の冪集合 $\mathcal{P}(X)$ が可算無限集合と全単射で対応したとすると、$x\mapsto\{x\}$ は $X$ から $\mathcal{P}(X)$ への単射なので、$X$ は有限か可算無限である。$X$ が有限なら $\mathcal{P}(X)$ は有限であり、$X$ が可算無限なら $\mathcal{P}(X)$ は $\mathcal{P}(\mathbb{N})$ と全単射で対応し、冪集合 の記事の定理「Cantorの定理」により可算でない。どちらも矛盾なので、可算無限な冪集合はない。よって $\mathcal{F}$ はどの集合の冪集合とも同型でない。満たす性質：Boole 代数であり、各 $\{n\}$ が原子である。満たさない性質：冪集合と同型。破る含意：「Boole 代数 $\Rightarrow$ ある冪集合と同型」は無限の場合に成り立たない（有限の場合は thm-boolean-algebra-finite）。

区間 $[0,1)$ の部分集合で、有理数 $a< b$ を端点とする半開区間 $[a,b)$（$0\le a< b\le1$）の有限個の和集合として書けるもの全体に $\emptyset$ を加えた族を $\mathcal{I}$ とする。$[a,b)$ の補集合 $[0,a)\cup[b,1)$ は（空でない部分について）また同じ形であり、2 つの半開区間の共通部分は空か半開区間なので、分配律と De Morgan の法則により $\mathcal{I}$ は和・共通部分・補集合で閉じ、$\mathcal{P}([0,1))$ の演算を制限した Boole 代数になる。$\mathcal{I}$ の $0$ でない元 $U$ は、ある $[a,b)$ を含み、$\emptyset\subsetneq[a,\tfrac{a+b}{2})\subsetneq U$ である。よって $\mathcal{I}$ には原子が 1 つもない。満たす性質：自明でない Boole 代数。満たさない性質：$0$ でない元の下に原子がある。破る含意：有限の場合に成り立つ lem-boolean-algebra-atoms-below は無限の場合に成り立たない。