順序関係と順序集合

17.順序関係

半順序

次を満たす集合\(A\)上の二項関係\(R\)を半順序という
\(\forall a,b,c \in A\)に対して

1.\(a\leq_R a\)
2.\((a\leq _R b \land b\leq _R c)\rightarrow a\leq_R c\)
3.\((a\leq_R b \land b\leq_R a)\rightarrow a=b\)

全順序

4.\(\forall a,b \in A(a\leq_R b \lor b\leq_R a)\)
を満たす\(A\)上の半順序を\(A\)上の全順序という

18.順序集合

順序集合

半順序\(\leq_R\)が定義された集合\((A,\leq_R)\)を半順序集合もしくは順序集合という

全順序集合

全順序\(\leq_R\)が定義された集合\((A,\leq_R)\)を全順序集合という

半順序の例

集合\(A\)の冪集合と包含関係\((\mathfrak{P}(A),\subset)\)

\(\forall X,Y,Z \in \mathfrak{P}(A)\)に対して

\(1.X \subset X\)
\(2.(X\subset  Y \land Y\subset  Z)\rightarrow X\subset Z\)
\(3.(X\subset Y \land Y\subset X)\rightarrow X=Y\)

が成立するので半順序集合だが例えば\(A=\{0,1\}\)は\(\{0\}\subset \{1\}\)も\(\{1\}\subset \{0\}\)も成立しないので全順序集合ではない

全順序の例

\(A=\mathbb{N,Z,R}\)と大小関係\((A,\leq )\)

\(\forall a,b,c \in A\)に対して

1.\(a\leq a\)
2.\((a\leq b \land b\leq c)\rightarrow a\leq c\)
3.\((a\leq b \land b\leq a)\rightarrow a=b\)
4.\(\forall a,b \in A(a\leq b \lor b\leq a)\)


が成立するので全順序集合である

19.上界、下界

以下\((P,\leq_R)\)を順序集合、\(A\)を\(P\)の部分集合とする

上界

\(x\)が\(A\)の上界:
\(\forall y\in A(y\leq_R x)\)

下界

\(x\)が\(A\)の下界:
\(\forall y\in A(x\leq_R y)\)

20.最大元、最小元

最大元

\(x\)が\(A\)の最大元:
\( x \in A\ \)かつ \(x\)は\(A\)の上界

最小元

\(x\)が\(A\)の最小元:
\( x \in A\ \)かつ \(x\)は\(A\)の下界

最大元、最小元が存在すれば唯一

\(x_1\)が\(A\)の最大元:\(x_1\in A \land \forall y\in A(y\leq _R x_1)\)
\( x_2\)が\(A\)の最大元:\(x_2\in A \land \forall y\in A(y\leq _R x_2)\)

よって\(y\)をそれぞれ\(x_2,x_1\)と取れば
\(x_2 \leq_R x_1\ \\x_1\leq_R x_2 \)

が成立し、順序関係の定義から

\(x_1=x_2\)

最小元も同様である

表記

\(A\)の最大元を\(max\ A\), 最小元を\(min\ A\)と表す

21.上限、下限

上限

\(x\)が\(A\)の上限:
集合\(\{y\in P|y\)は\(A\)の上界\( \}\)の最小元

下限

\(x\)が\(A\)の下限:
集合\(\{y\in P|y\)は\(A\)の下界\( \}\)の最大元

上限、下限が存在すれば唯一

上限と下限は\(P\)の部分集合の最小元と最大元でこれらは存在すれば唯一である

表記

\(A\)の上限を\(sup\ A\), 下限を\(inf\ A\)と表す

上限が存在すれば上限は上界
下限が存在すれば下限は下界

\(supA\)は集合\(\{y\in P|y\)は\(A\)の上界\(\}\)の最小元なので
\(sup A\in \{y\in P|y\)は\(A\)の上界\(\}\)
よって\(sup A\)は\(A\)の上界

\(infA\)は集合\(\{y\in P|y\)は\(A\)の下界\(\}\)の最大元なので
\(inf A\in \{y\in P|y\)は\(A\)の下界\(\}\)
よって\(inf A\)は\(A\)の下界

\(max A\)が存在する\(\Rightarrow max A=sup A\)
\(min A\)が存在する\(\Rightarrow min A=inf A\)


\(maxA\in A\), \(supA\)は\(A\)の上界なので

\(⓵maxA \leq_R supA\)


\(max A \in \{y\in P|y\)は\(A\)の上界\( \}\)
\(supA\)は\(\{y\in P|y\)は\(A\)の上界\( \}\)の最小元なので

\(⓶sup A \leq_R maxA\)


\(⓵,⓶\)と半順序関係の定義から

\(max A=supA\)

\(minA=infA\)も同様

22.極大元、極小元

極大元

\(x\)が\(A\)の極大元:
\(x\in A \) かつ \( \forall y\in A(x \leq_R y \rightarrow x=y)\)

極小元

\(x\)が\(A\)の極小元:
\(x\in A \) かつ \( \forall y\in A(y \leq_R x \rightarrow x=y)\)

\(maxA\)が存在する\(\Rightarrow max A\)は\(A\)の極大元
\(minA\)が存在する\(\Rightarrow min A\)は\(A\)の極小元


⓵\(maxA\in A\)である

\(\forall y\in A(y\leq_R maxA)\)なので
⓶\(\forall y \in A(max A\leq_R y \rightarrow maxA=y)\)

⓵⓶より\(maxA\)は極大元である

\(minA\)も同様である