§D2.5関係・同値関係・順序集合

証明.$R$を$A$上の同値関係とする。定義 2.1 条件 (a)により、各$a\in A$について$a\mathrel{R}a$であるから$a\in[a]_R$であり、$[a]_R$は空でなく$\bigcup_{a\in A}[a]_R=A$が成り立つ。$a,b\in A$が$[a]_R\cap[b]_R\neq\varnothing$を満たすとし、$x$をその共通部分の元とすると$x\mathrel{R}a$かつ$x\mathrel{R}b$である。$y\in[a]_R$を取ると$y\mathrel{R}a$であり、定義 2.1 条件 (b)により$a\mathrel{R}x$であるから、定義 2.1 条件 (c)により$y\mathrel{R}x$が成り立ち、$x\mathrel{R}b$と合わせてふたたび定義 2.1 条件 (c)により$y\mathrel{R}b$が成り立つ。よって$y\in[b]_R$であり$[a]_R\subseteq[b]_R$である。$a$と$b$の役割を入れ替えれば$[b]_R\subseteq[a]_R$も得られるので$[a]_R=[b]_R$である。したがって$A/R$の相異なる二元は互いに素であり、$A/R$は$A$の分割である。

$\mathcal{P}$を$A$の分割とし、$a\mathrel{R_{\mathcal{P}}}b$であることを、$a$と$b$がともに属する$\mathcal{P}$のブロックが存在することと定める。各$a\in A$は$\bigcup_{P\in\mathcal{P}}P=A$からあるブロックに属するので$a\mathrel{R_{\mathcal{P}}}a$であり、$R_{\mathcal{P}}$は反射的である。$a$と$b$がともに属するブロックが存在することと、$b$と$a$がともに属するブロックが存在することは同じ条件であるから、$R_{\mathcal{P}}$は対称的である。$a,b,c\in A$が$a\mathrel{R_{\mathcal{P}}}b$かつ$b\mathrel{R_{\mathcal{P}}}c$を満たすとすると、$a,b\in P$と$b,c\in Q$を満たす$P,Q\in\mathcal{P}$が存在する。$b\in P\cap Q$であるから$P\cap Q\neq\varnothing$であり、$\mathcal{P}$の相異なる二元は互いに素であるから$P=Q$である。よって$a,c\in P$となり$a\mathrel{R_{\mathcal{P}}}c$が成り立つので、$R_{\mathcal{P}}$は推移的である。ゆえに$R_{\mathcal{P}}$は$A$上の同値関係である。

$R$を$A$上の同値関係とし、$a,b\in A$とする。$a\mathrel{R_{A/R}}b$とすると、$a,b\in[c]_R$を満たす$c\in A$が存在し、$a\mathrel{R}c$かつ$b\mathrel{R}c$である。定義 2.1 条件 (b)により$c\mathrel{R}b$であり、定義 2.1 条件 (c)により$a\mathrel{R}b$である。逆に$a\mathrel{R}b$とすると$a\in[b]_R$であり、定義 2.1 条件 (a)により$b\in[b]_R$であるから、$a$と$b$はともに$[b]_R$に属し$a\mathrel{R_{A/R}}b$である。したがって$R_{A/R}=R$である。

$\mathcal{P}$を$A$の分割とし$R=R_{\mathcal{P}}$とおく。$a\in A$を含む$\mathcal{P}$のブロックは存在し、$P,Q\in\mathcal{P}$がともに$a$を含めば$P\cap Q\neq\varnothing$から$P=Q$となるので、ただ一つである。これを$P(a)$と書く。$x\in[a]_R$であることは$x$と$a$がともに属するブロックが存在することであり、$a$を含むブロックは$P(a)$だけであるから、$x\in P(a)$と同値である。よって$[a]_R=P(a)$であり$A/R=\{P(a):a\in A\}$である。各$a\in A$について$P(a)\in\mathcal{P}$であるから$A/R\subseteq\mathcal{P}$であり、逆に$P\in\mathcal{P}$は空でないので$a\in P$を取れば$P=P(a)\in A/R$となる。したがって$A/R_{\mathcal{P}}=\mathcal{P}$である。

同値関係$R$に$A/R$を対応させる写像を$\Phi$、分割$\mathcal{P}$に$R_{\mathcal{P}}$を対応させる写像を$\Psi$と書く。ここまでに示したことにより、$\Phi$は$A$上の同値関係全体から$A$の分割全体への写像、$\Psi$は$A$の分割全体から$A$上の同値関係全体への写像であり、$\Psi\circ\Phi$と$\Phi\circ\Psi$はともに恒等写像である。$\Psi\circ\Phi$が恒等写像であることから$\Phi$は単射であり、$\Phi\circ\Psi$が恒等写像であることから$\Phi$は全射である。ゆえに$\Phi$は全単射である。▨

証明.命題 2.5により、$[n]$上の同値関係全体から$[n]$の分割全体への全単射が存在する。全単射で結ばれた二つの有限集合の元の個数は等しいから、結論が従う。▨

証明.$(P,\le)$を半順序集合、$S\subseteq P$とし、$m,m'$をともに$S$の最大元とする。最大元の定義から$m\le m'$かつ$m'\le m$であり、$\le$の反対称性から$m=m'$である。したがって最大元は存在すれば一意である。

$n,n'$をともに$S$の最小元とする。最小元の定義から$n\le n'$かつ$n'\le n$であり、$\le$の反対称性から$n=n'$である。したがって最小元も存在すれば一意である。▨

証明.$a=x_0\lessdot x_1\lessdot\cdots\lessdot x_k=b$を満たす列が存在するとする。$k=0$ならば反射律により$a\le b$であり、$k>0$ならば各$x_{i-1}<x_i$と推移律により$a<b$である。

$a\le b$とし、$M(a,b)=\{y\in P:a<y<b\}$の元の個数について帰納法を用いる。$a=b$ならば$k=0$の列を取ることができる。$a<b$かつ$M(a,b)=\varnothing$ならば$a\lessdot b$であるから、$k=1$の列を取ることができる。$a<b$かつ$M(a,b)\ne\varnothing$ならば、$x\in M(a,b)$を取る。$<$の推移性から$M(a,x),M(x,b)\subseteq M(a,b)$であり、いずれも$x$を含まないから、それぞれの元の個数は$M(a,b)$の元の個数より小さい。帰納法の仮定により$a$から$x$への被覆列と$x$から$b$への被覆列が存在し、二つの列を$x$でつなぐと$a$から$b$への被覆列を得る。▨

証明.$F\subseteq L$を空でない有限部分集合とし、$F$の元の個数について帰納法を用いる。$F=\{a\}$ならば$a$が$F$の上限である。$n$元以下の空でない部分集合が上限をもつと仮定し、$F=\{a_1,\ldots,a_n,a_{n+1}\}$とする。$b=\sup\{a_1,\ldots,a_n\}$とおくことができ、束の定義から$b\vee a_{n+1}$が存在する。各$a_i$は$b\vee a_{n+1}$以下であるから、$b\vee a_{n+1}$は$F$の上界である。$u$を$F$の上界とすると、$b\le u$かつ$a_{n+1}\le u$であるから$b\vee a_{n+1}\le u$である。したがって$b\vee a_{n+1}=\sup F$である。数学的帰納法により、$F$は上限をもつ。

$F=\{a\}$ならば$a$が$F$の下限である。$n$元以下の空でない部分集合が下限をもつと仮定し、$F=\{a_1,\ldots,a_n,a_{n+1}\}$とする。$c=\inf\{a_1,\ldots,a_n\}$とおくことができ、束の定義から$c\wedge a_{n+1}$が存在する。$c\wedge a_{n+1}$は各$a_i$以下であるから$F$の下界である。$l$を$F$の下界とすると、$l\le c$かつ$l\le a_{n+1}$であるから$l\le c\wedge a_{n+1}$である。したがって$c\wedge a_{n+1}=\inf F$である。数学的帰納法により、$F$は下限ももつ。▨