順序

3.1　 集合 $A$ 上の関係 $\rho$ が反射律と 推移律(2.2参照)をみたすとき， $\rho$ は擬順序であるという． $A$ 上の擬順序 $\rho$ がさらに

反対称律：

すべての元 $a,b$ に対して $a\rho b$ かつ $b\rho a$ ならば $a=b$ である

をみたすとき、$\rho$ は順序であるといい、さらに

全律：

すべての元 $a,b$ に対して $a\rho b$ または $b\rho a$ である

が成立するとき $\rho$ は全順序であるという． これら二つの条件は含意形(2.4参照）ではない． 擬順序，順序，全順序の定義された集合をそれぞれ擬順序集合，順序集合，全順序集合という． 順序の記号は慣例的に $\leqq$ で表し， $a\leqq b$ のとき，$a$ は $b$ より小さい， また $b$ は $a$ より大きいという．

数の集合 $Z,Q,R$(1.4参照)等はすべて自然の順序で全順序集合である． 集合の間の包含関係，関係の間の強弱関係 などは順序である．

$\rho$ が集合 $A$ 上の擬順序のとき，$a,b\in A$ に対して $a\sim b$ とは $a\rho b$ かつ $b\rho a$ であることと定義すれば $\sim$ は対称律もみたし，従って $A$ の上の同値関係となる． この各同値類から一つずつ代表元をとって，それらの集合を $B$ とすれば $B\subset A$ で，$\rho$ を $B$ 上に制限したものは 反対称律をみたし，従って $B$ 上の順序となる． $B$ を擬順序集合 $A$ の骨格という．

3.2 $L$ が半束(1.8 参照)のとき， $a\leqq b$ とは $ab=b$ となることとして $L$ 上に関係 $\leqq$ を入れれば $\leqq$ は順序である． 実際 $aa=a$ であるから $a\leqq a$． $a\leqq b$ かつ $b\leqq a$ であれば $ab=b$ かつ $ba=a$， よって可換律より $a=b$． $a\leqq b$ かつ $b\leqq c$ ならば $ab=b$ かつ $bc=c$ だから結合律から $ac=a(bc)=(ab)c=bc=c$． よって $a\leqq c$ で $\leqq$ は順序の三条件 をみたす．

次にこの順序 $\leqq$ で $ab$ は $a,b$ のどちらよりも大きい元の中で最小のものを与えている． 実際、$c=ab$ ならば $ac=a(ab)=(aa)b=ab=c$ で $a\leqq c$． 同様にして $b\leqq c$． さらに $a\leqq x$ かつ $b\leqq x$ であれば $ax=x$ かつ $bx=x$ であるから $cx=(ab)x=a(bx)=ax=x$ で $c\leqq x$ である．

3.3 $X$ は順序集合 $A$ の部分集合とする． $z\in X$ がどの $x\in X$ よりも大きいとき $z$ は $X$ で最大，または $z$ は $X$ の最大元といい，$z\in X$ がどの $x\in X$ より小さいとき、$z$ は $X$ で最小，または $z$ は $X$ の最小元 という．$a\in A$ がどの $x\in X$ より大きいとき $a$ は $X$ の上界といい， $X$ の上界の集合が最小元を持てばそれを $X$ の上端という． $a\in A$ がどの $x\in X$ よりも小さければ $a$ は $X$ の下界といい， $X$ の下界の集合が最大元を持てばそれを $X$ の下端という． $A$ の任意の部分集合が上端を持つとき $A$ は上に完備， $A$ の任意の部分集合が下端を持つとき $A$ は下に完備という． $A$ が上と下に完備のとき $A$ は（単に）完備という． $A$ の任意の有限部分集合が上端を持つとき $A$ は上に有限完備といい， 下に有限完備，（単なる）有限完備も同様に定義する． 3.2の内容は半束 $L$ が上記の関係 $\leqq$ で順序集合となり， その任意の二元部分集合に上端がある（略して任意の二元に上端があるという）ことを意味するが， ここに次の主張が成り立つ．

補題　 任意の二元に上端のある順序集合は上に有限完備である．

証明 三元集合 ${a,b,c}$ については $a,b$ の上端 $x$ と $c$ との上端がこの集合の上端となる． $n$ 元部分集合については数学的帰納法によればよい．(証明終)

系　 半束 $L$ は $ab=b$ のとき $a\leqq b$ と定義すれば関係 $\leqq$ について上に有限完備な順序集合となる． 逆に $L$ が上に有限完備な順序集合のとき二元 $a,b$ の上端を $ab$ とすれば $L$ はこの演算について半束となる．

後半の証明も容易である ．

3.4　 $A,B$ を集合とする．一般に $A$ の元と $B$ の元との間の関係 $\rho$ に対して，$B$ の元と $A$ の元の間の関係$\rho '$ で $a\rho b$ であるとき，かつそのときに限って $b\rho 'a$ となるようなものを $\rho$ の逆関係，または略して逆という．特に $A=B$ のとき， $A$ の上の関係 $\rho$ の逆はまた $\rho$ の双対ともいう． $\rho$ の双対が $\rho$ と一致するための必要十分条件は $\rho$ が対称律をみたすことで，従って同値関係はその双対と一致する． 順序関係の双対はまた新しい順序関係となる．順序集合 $A$ にその双対順序を入れて作った 順序関係をもとの順序集合の双対という．

$\alpha$ を順序集合に関するある概念とする．$\alpha$ を双対順序の中で考えると 新しい概念 $\beta$ になるとき $\beta$ を $\alpha$ の双対という． このとき $\alpha$ はまた $\beta$ の双対となる．例えば 3.3 で述べた 上界，上端，上に完備の双対はそれぞれ下界，下端，下に完備で，完備の双対はそれ自身である．その双対と 一致する概念は自己双対であるという．

ある記述，または定理において，その中に現れるすべての概念をその双対でおきかえて作った記述，定理は もとのものの双対という．ある定理が順序集合の中で一般的に成り立つとき，その双対定理も一般的に成り立つ． もとの定理の証明の中の概念をすべてその双対で置き換えれば双対定理の証明となるからである． 例えば 3.3 の補題に対してその双対補題

補題　 任意の二元に下端のある順序集合は下に有限完備である．

は一般に正しい．

3.5　 $L$ は二つの演算 $\lor \land$ について束であるとする（1.8を参照)． $L$ は $\lor$ について半束だから $a\lor b=b$ のとき $a\leqq b$ とすれば $\leqq$ は $L$ 上の順序となる． 同様に $a\land b=a$ のとき $a\prec b$ とすれば $\prec$ も $L$ 上の順序であるが，$a\leqq b$ ならば $a\lor b=b$ であるから，吸収律の第一式より $a\land b=a\land (a\lor b)=a$ で $a\prec b$． 同様にして吸収律の第二式から $a\prec b$ ならば $a\leqq b$ となり ， この二つの順序は $L$ 上で一致する．すなわち

定理　 束 $L$ において $a\lor b=b$ のとき $a\leqq b$ と定義すれば， $\leqq$ は $L$ 上の順序で，これにより $L$ は有限完備で， $a\lor b,a\land b$ はそれぞれ二元 $a,b$ の上端と下端とを与える． 逆に有限完備な順序集合 $L$ において二元 $a,b$ の上端，下端をそれぞれ $a\lor b,a\land b$ とすれば $L$ は演算 $\lor ,\land$ により束となる．

3.6　 順序という概念は数学や実世界の各所に現れる具体的な現象である大小関係，支配関係等を抽象化， 一般化して統一的に取り扱おうとする考えである．しかしこのような抽象概念を抽象的なまま考察するのは難しい． もしどのような抽象的順序集合でも，これを性質のよくわかった具体的な順序を持つ対象にひき戻すことができて， このような具体的な順序に関する考察や定理が，そのまま一般の抽象的順序に適用できることが示されたなら便利である． このような考え方を順序の，あるいはさらに一般の抽象概念の，表現という．

順序集合 $A$ の各元 $a$ に対して

$A(a)=\{x\in A|x\leqq a\},{\tilde {A}}=\{A(a)|a\in A\}$

とおく．このとき $a\leqq b$ ならば $A(a)\subset A(b)$ で，逆に $A(a)\subset A(b)$ ならば $a\in A(a)\subset A(b)$ であるから $a\leqq b$ である ． 特に $A(a)=A(b)$ ならば $a=b$． よって $A$ の各元と ${\tilde {A}}$ の各元とは一対一対応し， $A$ 内で $a\leqq b$ であることと，${\tilde {A}}$ 内で $A(a)\subset A(b)$ であることとは同等である．この ${\tilde {A}}$ を $A$ の下界による表現という．

この表現は $A$ の順序を ${\tilde {A}}$ の包含関係で表現したわけであるが， さらに $A$ の二元の下端が ${\tilde {A}}$ 内の集合論的交で表現されている． 実際 $A$ の中で二元 $a,b$ の下端 $a\land b$ があれば， $A$ 内で $x\leqq a$ かつ $x\leqq b$ であることと $x\leqq a\land b$ であることとは同等であるから，$A(a\land b)=A(a)\cap A(b)$ （ただし ${\tilde {A}}$ では任意の二元 $A(a),A(b)$ に対して必ず $A(a)\cap A(b)$ は存在するが，これがある $c\in A$ について $A(c)$ となっているとは限らない）．しかし $A$ 内の $\lor$ は ${\tilde {A}}$ 内の $\cup$ で表現されていはいない． $a\lor b$ が存在しても $A(a\lor b)$ と $A(a)\cup A(b)$ とは一般に相異なるものである．

3.7　 最後に後に参照するいくつかの概念の定義を述べておく．

$A$ を順序集合，$X$ はその部分集合とする．$x\in X,a\in A$ で $x\leqq a$ ならば必ず $a\in X$ となるとき $X$ は上に閉じているという．各 $a\in A$ に対して $a\leqq x$ である $x\in X$ が見出されるときは $X$ は $A$ に共終であるといい， さらに強く，各 $a\in A$ に対し $a\leqq x$ である $x\in X$ が存在して $\{x\}$ の上界がすべて $X$ に入るとき，$X$ は $A$ に等終であるという．$X$ が $A$ に共終で上に閉じていれば $A$ に等終となる．

上に閉じている，共終，等終の双対はそれぞれ下に閉じている，共始，等始という．

順序集合 $A$ の任意の二元が上界を持つとき $A$ は有向集合であるという． 有向集合は位相論など極限概念を取り扱うときには基本になる概念である． 半束は 3.2で考えた順序によって有向集合である． 有向集合 $A$ の部分集合 $X$ は必ずしも有向集合ではないが， $X$ が $A$ に共終ならば有向集合となる． 上に述べた共終，等終などの概念は普通は有向集合の部分集合に対して考えられるのであるが， 定義だけならば一般の順序集合の中で考えても差し支えない．

順序集合 $A$ の空でない部分集合が常に最小元を持つとき， $A$ は整列集合という．特に整列集合 $A$ の二元 $a,b$ のうちどちらかが集合 $\{a,b\}$ の最小元で，よって整列集合は全順序集合である． 整列集合の部分集合はまた整列集合である． 正整数の集合 $Z^{+}$ は整列集合であるが，さらに

$\{m-1/(n+1)|m,n\in Z^{+}\}$

$\{m-1/(n+1)-1/n(n+1)(l+1)|l,m,n\in Z^{+}\}$

なども実数の部分集合として整列である．集合論の適当な公理系のもとに任意の濃度の整列集合の存在することが知られている．

officious