全順序
概要
全順序（total order）とは、集合 $P$ 上の順序（反射律・反対称律・推移律を満たす二項関係）$\leq$ であって、さらに任意の二元 $x,y\in P$ について $x\leq y$ または $y\leq x$ が成り立つもの、すなわち比較不能な組が存在しない順序のことであり、線形順序とも呼ばれる。全順序を備えた集合を全順序集合または鎖という。整数や実数の通常の大小関係、単語の辞書式順序が典型例であり、集合の包含関係や整除関係は順序ではあるが全順序ではない。狭義順序の三分律で特徴付けられ、部分集合への制限や辞書式順序で保たれ、有限な全順序集合では空でない部分集合が必ず最小元を持つ。任意の順序は Zorn の補題により全順序へ拡大できる（順序拡大定理）。
前提知識: 順序集合, 二項関係, 反射律, 反対称律, 推移律
定義
集合 $P$ 上の二項関係 $\leq$ が $P$ 上の全順序（total order, linear order）であるとは、次の四条件を満たすことをいう。
- 反射律：任意の $x\in P$ に対して $x\leq x$。
- 反対称律：$x\leq y$ かつ $y\leq x$ ならば $x=y$。
- 推移律：$x\leq y$ かつ $y\leq z$ ならば $x\leq z$。
- 全順序律（totality, comparability）：任意の $x,y\in P$ に対して $x\leq y$ または $y\leq x$。
条件 1〜3 は $\leq$ が $P$ 上の順序（半順序）であること、すなわち $(P,\leq)$ が順序集合であることを意味する。したがって全順序とは、任意の二元が比較可能な順序のことである。$\leq$ が $P$ 上の全順序であるとき、組 $(P,\leq)$ を全順序集合（totally ordered set, linearly ordered set）または線形順序集合という。全順序集合、あるいはより大きな順序集合の中で誘導順序が全順序になっている部分集合を鎖（chain）ともいう。
$x,y\in P$ が比較可能であるとは $x\leq y$ または $y\leq x$ が成り立つことをいい、そうでないとき比較不能であるといって $x\parallel y$ と書く。全順序律は「比較不能な組 $x\parallel y$ が存在しない」ことと同値である。$P=\emptyset$ のときは比較すべき組がないので全順序律は空虚に成り立ち、$P$ が一元集合 $\{a\}$ のときは反射律から $a\leq a$ なので、いずれも全順序集合である。反対称律を落としたものが前順序である。
$(P,\leq)$ を順序集合とする。$x< y$ を「$x\leq y$ かつ $x\neq y$」で定め、$<$ を $\leq$ の狭義順序という。$P$ 上の関係 $<$ が三分律（law of trichotomy）を満たすとは、任意の $x,y\in P$ に対して
$$
x< y,\qquad x=y,\qquad y< x
$$
のうちちょうど一つが成り立つことをいう。
直感
順序集合では比較できる二元と比較できない二元が混在してよいが、実数の大小関係では任意の二実数 $x,y$ について $x\leq y$ か $y\leq x$ の少なくとも一方が必ず成り立つ。全順序は、この「どの二元も必ず比較できる」という性質を順序集合に追加で課した構造であり、有限ならHasse図は枝分かれのない一本の線として描ける順序である。全順序集合ではすべての元を一列に並べられるので、ソートや数列の単調性のように「並べる」ことを前提とする議論の舞台になる。ただし一列に並ぶことと「一番小さい元から順に取り出せる」ことは別であり、後者は整列順序が扱う。
例と反例
自然数全体 $\mathbb{N}$、整数全体 $\mathbb{Z}$、有理数全体 $\mathbb{Q}$、実数全体 $\mathbb{R}$ に通常の大小関係 $\leq$ を入れると、いずれも全順序集合である。任意の二つの実数 $x,y$ について $x\leq y$ または $y\leq x$ が成り立つことは実数の順序の基本性質であり、$\mathbb{N},\mathbb{Z},\mathbb{Q}$ は $\mathbb{R}$ の部分集合として誘導順序を受け継ぐ（prop-total-order-restriction）。全順序の概念は、この「大小がつく」という感覚を一般の集合に対して公理化したものである。
アルファベット $\{a,b,\ldots,z\}$ に $a< b<\cdots< z$ の順序を入れ、単語（有限長の文字列）を辞書のように先頭の文字から順に比較する。先頭から一致する限り次の文字を比べ、一方が他方の真の接頭辞になっている場合（「cat」と「catalog」）は短い方を先とする。任意の二つの単語について、最初に異なる文字の位置があるか、一方が他方の接頭辞であるかのどちらかなので、どちらが先かが必ず決まり、この並びは全順序である。prop-total-order-lex は、二成分の場合の基本形である。
有限集合 $\{x_1,\ldots,x_n\}$ の元を一列に並べ、$x_i\leq x_j$ を $i\leq j$ で定めると全順序集合になる。逆に $n$ 元集合上の全順序は、元の並べ方（順列）と一対一に対応し、ちょうど $n!$ 個ある。有限全順序集合の整列性により最小元から順に取り出せば列挙が得られ、列挙から全順序を定める対応がその逆になる。有限な全順序集合は空でない任意の部分集合が最小元を持つ（prop-total-order-finite-well-ordered）。
次の二つは順序集合ではあるが全順序集合ではない。すなわち順序の三条件は満たすが全順序律を満たさず、「順序ならば全順序」という含意が成り立たないことを示す。
整数全体 $\mathbb{Z}$ の通常の大小関係は全順序だが、$\mathbb{Z}$ 自身は最小元を持たない（任意の $n$ に対して $n-1< n$）ので、空でない任意の部分集合が最小元を持つという整列順序の条件を満たさない。実数の開区間 $(0,1)$ も、通常の順序で全順序だが、$(0,1)$ 自身に最小元はない（$x\in(0,1)$ に対して $x/2\in(0,1)$ かつ $x/2< x$）。「全順序ならば整列順序」という含意は成り立たない。
性質
$(P,\leq)$ を順序集合とし、$<$ をその狭義順序とする。次は同値である。
- $\leq$ は $P$ 上の全順序である。
- $<$ は三分律を満たす。
(1 ⇒ 2) $x,y\in P$ を任意にとる。全順序律から $x\leq y$ または $y\leq x$ である。$x\leq y$ のとき、$x=y$ なら「$x=y$」が、$x\neq y$ なら $x< y$ が成り立つ。$y\leq x$ のときも同様なので、三つのうち少なくとも一つは成り立つ。二つ以上が同時に成り立たないこと：$x< y$ と $x=y$ は $x< y$ の定義が $x\neq y$ を含むので両立しない。$x=y$ と $y< x$ も同様である。$x< y$ と $y< x$ が同時に成り立てば $x\leq y$ かつ $y\leq x$ となり、反対称律から $x=y$ となって $x< y$ に反する。
(2 ⇒ 1) $x,y\in P$ を任意にとる。$x=y$ なら反射律から $x\leq y$ である。$x\neq y$ なら三分律から $x< y$ または $y< x$ であり、狭義順序の定義から $x\leq y$ または $y\leq x$ である。よって全順序律が成り立つ。$\square$
$(P,\leq)$ を全順序集合、$S\subset P$ とする。$\leq$ を $S\times S$ に制限した誘導順序は $S$ 上の全順序である。
誘導順序が $S$ 上の順序であることは 順序集合 の部分集合への制限の命題による。全順序律も「任意の $x,y\in P$ について」成り立つ条件であり、$S$ の元は $P$ の元でもあるから、$x,y\in S$ に限っても成り立つ。$\square$
反射律：$p=p$ かつ $q\leq_Q q$ なので $(p,q)\leq_{\mathrm{lex}}(p,q)$。
反対称律：$(p,q)\leq_{\mathrm{lex}}(p',q')$ かつ $(p',q')\leq_{\mathrm{lex}}(p,q)$ とする。$p<_P p'$ なら $p\neq p'$ なので、二つ目の関係は $p'<_P p$ でなければならず、$p\leq_P p'\leq_P p$ と反対称律から $p=p'$ となって矛盾する。$p'<_P p$ の場合も同様に矛盾する。よって $p=p'$ であり、二つの関係はそれぞれ $q\leq_Q q'$、$q'\leq_Q q$ を与えるので、$\leq_Q$ の反対称律から $q=q'$。ゆえに $(p,q)=(p',q')$。
推移律：$(p,q)\leq_{\mathrm{lex}}(p',q')$ かつ $(p',q')\leq_{\mathrm{lex}}(p'',q'')$ とする。辞書式順序の定義から、いずれの場合も $p\leq_P p'$ かつ $p'\leq_P p''$ であり、推移律から $p\leq_P p''$ である。$p<_P p'$ または $p'<_P p''$ の少なくとも一方が成り立つ場合、$p=p''$ とすると $p\leq_P p'\leq_P p$ と反対称律から $p=p'=p''$ となって狭義の関係に反するので、$p\neq p''$、すなわち $p<_P p''$ である。よって $(p,q)\leq_{\mathrm{lex}}(p'',q'')$。残るのは $p=p'=p''$、$q\leq_Q q'\leq_Q q''$ の場合であり、$\leq_Q$ の推移律から $q\leq_Q q''$、よって $(p,q)\leq_{\mathrm{lex}}(p'',q'')$。
全順序律：$(p,q),(p',q')\in P\times Q$ をとる。prop-total-order-trichotomy により $p<_P p'$、$p=p'$、$p'<_P p$ のいずれかが成り立つ。$p<_P p'$ なら $(p,q)\leq_{\mathrm{lex}}(p',q')$、$p'<_P p$ なら $(p',q')\leq_{\mathrm{lex}}(p,q)$ である。$p=p'$ なら $Q$ の全順序律から $q\leq_Q q'$ または $q'\leq_Q q$ であり、それぞれ $(p,q)\leq_{\mathrm{lex}}(p',q')$、$(p',q')\leq_{\mathrm{lex}}(p,q)$ を与える。$\square$
$P,Q$ が全順序集合であっても、成分ごとに比較する直積順序（$(p,q)\leq(p',q')$ を $p\leq_P p'$ かつ $q\leq_Q q'$ で定めたもの）は一般に全順序ではない。$\mathbb{N}\times\mathbb{N}$ では $(1,0)$ と $(0,1)$ が比較不能である。全順序を得るには、成分を同時に比べる直積順序ではなく、第1成分を優先して逐次比べる辞書式順序を用いる。
$(P,\leq)$ を全順序集合とする。$P$ の空でない有限部分集合 $S$ は最小元（任意の $x\in S$ に対して $m\leq x$ となる $m\in S$）と最大元を持つ。特に有限な全順序集合は整列集合である。
$n=|S|\geq 1$ についての帰納法（数学的帰納法）で最小元の存在を示す。$n=1$ のとき $S=\{a\}$ であり、$a\leq a$ から $a$ が最小元である。$n\geq 2$ とし、元の個数が $n$ 未満の空でない部分集合については主張が成り立つとする。$a\in S$ を一つ選び $S':=S\setminus\{a\}$ とおくと $|S'|=n-1\geq 1$ なので、帰納法の仮定から $S'$ は最小元 $m$ を持つ。全順序律から $a\leq m$ または $m\leq a$ である。$a\leq m$ なら、任意の $x\in S'$ に対して $a\leq m\leq x$ なので、$a$ は $S$ の最小元である。$m\leq a$ なら、$m$ は $S'$ の元すべて以下であり $a$ 以下でもあるので、$m$ は $S$ の最小元である。
最大元の存在は、$x\leq y$ または $y\leq x$ という条件は $\leq^{\mathrm{op}}$ について対称なので双対順序 $\leq^{\mathrm{op}}$（順序集合）も全順序であることに注意して、同じ議論を $\leq^{\mathrm{op}}$ に適用すれば得られる。$\square$
$(P,\leq)$ を順序集合、$a,b\in P$ を比較不能な二元とする。$P$ 上の関係 $\leq'$ を
$$
x\leq' y\ :\Longleftrightarrow\ x\leq y\ \text{または}\ (x\leq a\ \text{かつ}\ b\leq y)
$$
で定めると、$\leq'$ は $P$ 上の順序であり、$\leq\ \subset\ \leq'$ かつ $a\leq' b$ が成り立つ。
$x\leq y$ なら $x\leq' y$ なので $\leq\ \subset\ \leq'$ であり、$a\leq a$ かつ $b\leq b$ から $a\leq' b$ である。反射律は $\leq$ の反射律から従う。
反対称律：$x\leq' y$ かつ $y\leq' x$ とする。$x\leq y$ かつ $y\leq x$ なら反対称律から $x=y$ である。$x\leq y$ かつ（$y\leq a$ かつ $b\leq x$）なら $b\leq x\leq y\leq a$ より $b\leq a$ となり、$a\parallel b$ に反する。（$x\leq a$ かつ $b\leq y$）かつ $y\leq x$ の場合も同様に $b\leq a$ となって矛盾する。（$x\leq a$ かつ $b\leq y$）かつ（$y\leq a$ かつ $b\leq x$）なら $b\leq x\leq a$ となって矛盾する。よって $x=y$ である。
推移律：$x\leq' y$ かつ $y\leq' z$ とする。$x\leq y$ かつ $y\leq z$ なら $x\leq z$。$x\leq y$ かつ（$y\leq a$ かつ $b\leq z$）なら $x\leq a$ かつ $b\leq z$ なので $x\leq' z$。（$x\leq a$ かつ $b\leq y$）かつ $y\leq z$ なら $x\leq a$ かつ $b\leq z$ なので $x\leq' z$。（$x\leq a$ かつ $b\leq y$）かつ（$y\leq a$ かつ $b\leq z$）は $b\leq y\leq a$ を与え矛盾するので起こらない。$\square$
任意の順序集合 $(P,\leq)$ に対して、$P$ 上の全順序 $\leq^{*}$ で $\leq\ \subset\ \leq^{*}$ となるもの、すなわち $x\leq y$ ならば $x\leq^{*}y$ となる全順序が存在する。このような $\leq^{*}$ を $\leq$ の線形拡大（linear extension）という。
Zornの補題（順序集合の任意の鎖が上界を持てば極大元が存在する。選択公理と同値であり、本記事では証明せずに用いる。Jec03 Chapter 5）を使う。$\mathcal{O}$ を、$P$ 上の順序 $R$（$R\subset P\times P$ とみなす）で $\leq\ \subset R$ を満たすもの全体の集合とし、包含関係で順序集合とみる。$\leq\ \in\mathcal{O}$ なので $\mathcal{O}\neq\emptyset$ である。
$\mathcal{C}\subset\mathcal{O}$ を鎖とする。$\mathcal{C}=\emptyset$ なら $\leq$ が上界である。$\mathcal{C}\neq\emptyset$ のとき $U:=\bigcup\mathcal{C}$ とおく。$U$ が順序であることを確かめる。反射律は $\mathcal{C}$ の任意の元が反射的であることから従う。$(x,y)\in R_1\in\mathcal{C}$、$(y,x)\in R_2\in\mathcal{C}$ とすると、$\mathcal{C}$ が鎖なので $R_1\subset R_2$ または $R_2\subset R_1$ であり、大きい方の $R_i$ が $(x,y),(y,x)$ をともに含むので、$R_i$ の反対称律から $x=y$ である。推移律も同様に、$(x,y),(y,z)$ を含む $\mathcal{C}$ の元を一つとれば従う。さらに $\leq\ \subset R\subset U$（$R\in\mathcal{C}$）なので $U\in\mathcal{O}$ であり、$U$ は $\mathcal{C}$ の上界である。
よって Zorn の補題により $\mathcal{O}$ は極大元 $R^{*}$ を持つ。$R^{*}$ が全順序でないとすると、$R^{*}$ に関して比較不能な $a,b\in P$ が存在する。lem-total-order-one-step-extension を $(P,R^{*})$ に適用すると、$R^{*}\subset R'$、$(a,b)\in R'\setminus R^{*}$ となる順序 $R'$ が得られ、$\leq\ \subset R^{*}\subset R'$ より $R'\in\mathcal{O}$ かつ $R^{*}\subsetneq R'$ となって、$R^{*}$ の極大性に反する。ゆえに $R^{*}$ は $\leq$ を含む全順序である。$\square$
補足
thm-total-order-extension は Szpilrajn の定理とも呼ばれ、Szp30 による。上の証明は Zorn の補題を用いるが、$P$ が有限のときは選択公理を使わずに、極小元を一つずつ取り出して並べる操作（位相的整列）で線形拡大が具体的に構成できる。一方、「任意の順序が線形拡大を持つ」という主張（順序拡大原理）は選択公理より真に弱いことが知られており、選択公理を仮定しない集合論での位置づけは Jec08 を参照。
集合論寄りの文献（End77 Chapter 7、Jec03 Chapter 2）では、反射的な $\leq$ ではなく非反射的・推移的な狭義順序 $<$ を先に定義し、全順序を「非反射律・推移律に加えて三分律を満たす関係 $<$」として直接定義する。prop-total-order-trichotomy と 順序集合 の狭義順序による特徴付けにより、この定義と本記事の定義は同じ構造を与える。
全順序集合では極大元と最大元が一致し（順序集合）、空でない有限部分集合は必ず最小元と最大元を持つ（prop-total-order-finite-well-ordered）。解析学では、実数の全順序が単調数列の増加・減少、区間、上限・下限の前提になっている。全順序集合には開区間を開基とする順序位相が入り、$\mathbb{R}$ の通常の位相はその例である。計算機科学では、ソートは比較対象の集合上の全順序を前提とする操作であり、依存関係のような一般の順序集合を全順序へ並べ直す位相的整列は有限順序集合の線形拡大の構成である。集合論では、全順序集合のうち空でない任意の部分集合が最小元を持つものが整列集合であり、その同型類を順序数が代表する。全順序を保つ全単射は順序同型である。任意の集合に全順序、さらには整列順序を入れられるかという問い（整列可能定理）は選択公理と結びつく。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
