全順序
数学における線型順序（せんけいじゅんじょ、英: linear order）、全順序（ぜんじゅんじょ、英: total order）または単純順序（たんじゅんじゅんじょ、英: simple order）は、推移的、反対称かつ完全な二項関係を言う。集合と全順序を組にしたものは、全順序集合 (totally ordered set), 線型順序集合 (linearly ordered set), 単純順序集合 (simply ordered set) あるいは鎖 (chain) と呼ばれる。
即ち、集合 X が関係 ≤ によって全順序付けられるとき、X の任意の元 a, b, c に対して、以下の条件
- 反対称律: a ≤ b かつ b ≤ a ならば a = b;
- 推移律: a ≤ b かつ b ≤ c ならば a ≤ c;
- 完全律 (比較可能): a ≤ b または b ≤ a の何れかが必ず成り立つ;
が満足される。
反対称性によって a < b でも b < a でもあるような不確定な状態は排除される[1]。完全性を持つ関係は、その集合の任意の二元がその関係で比較可能であることを意味する。これはまた、元を直線に並べた図式によってその集合が表せるということでもあり、それは「線型」順序の名の由来である[2]。また完全性から反射性 (a ≤ a) が出るから、全順序は半順序の公理を満たす。半順序は（完全性の代わりに反射性のみが課されるという意味で）全順序よりも弱い条件である。与えられた半順序を拡張して全順序をえることは、半順序の線型拡張と呼ばれる。
Contents
狭義全順序
任意の（広義）全順序関係 ≤ に対し、それに付随する非対称（従って非反射的）な狭義全順序 (strict total order) と呼ばれる関係 < が存在する。これは次の互いに同値な二種類の仕方で定義することができる。
- a < b ⇔ a ≤ b かつ a ≠ b
- a < b ⇔ b ≤ a でない
後者は、関係 < が ≤ の補関係の逆関係であることを意味するものである。
- 性質
推移的かつ三分的な二項関係 < が最初に与えられたとき、そこから（広義の）全順序 ≤ を定めることも、次の同値な二種類の方法
- a ≤ b ⇔ a < b または a = b
- a ≤ b ⇔ b < a でない
でできる。
他にも二つ、これらの補関係 ≥ と > を考えることができ、四つ組 {<, >, ≤, ≥} はどれからでも他の三種類を導出することができるから、集合が全順序付けられることをいうのにいずれの関係を用いて定義・記述してもよい（特に広義か狭義かは記号で区別できる）。
例
- 通常のアルファベット順（たとえば A < B < C など）は文字列全体の成す集合を全順序付ける。
- 全順序集合の任意の部分集合は、もとの全体集合の順序をその部分集合に制限することで、全順序付けられる。
- 順序数からなる任意の集合、あるいは基数からなる任意の集合。これらは単に全順序集合であるばかりでなく、さらに強く整列集合になる。
- 任意の集合 X と X から全順序集合への単射 f に対し、x1 < x2 ⇔ f(x1) < f(x2) と置くことにより、f は X 上の全順序を誘導する。
- 適当な順序数で添字付けられた全順序集合族のデカルト積は、その上に辞書式順序を入れることにより、それ自身全順序集合になる。例えば、アルファベット順に並べた任意の語の集合が全順序付けられることは、（スペースの記号をどの文字よりも小さいものとして加えた）アルファベットの集合の可算個のコピーからなる集合族のデカルト積に辞書式順序を入れることで理解できる。
- 実数全体の成す集合 R は通常の大小関係 ("<" あるいは ">") によって全順序付けられる。従ってその部分集合としての、自然数全体の成す集合 N, 整数全体の成す集合 Z, 有理数全体の成す集合 Q なども全順序集合になる。これらは何れも、ある性質に関して最小の全順序集合として（同型を除いて）唯一の例を与えることが示せる（ここで、全順序集合 A がある性質に関して「最小」とは、同じ性質を持つ任意の B に対して A に順序同型な B の部分集合が存在することをいう）。
- 順序体は定義により全順序である。これは有理数体 Q や実数体 R を包括する概念である。
関連する概念
鎖
全順序の同義語としても用いられる鎖（さ、英: chain）は、また適当な半順序集合の全順序部分集合に対しても用いられる。後者の意味での鎖はツォルンの補題で極めて重要な役割を果たす。
例えば整数全体の成す集合 Z に包含関係で半順序を入れた半順序集合を考えると、自然数 n に対し、n 以下の自然数全体の成す部分集合 In からなる集合族 { In : n は自然数} はこの順序に関する鎖、すなわち包含関係に関する全順序部分集合になる。実際、n≤k ならば In は Ik の部分集合である。
束
全順序集合を特定の種類の束として定義することもできる。つまり、任意の a, b に対して
- [math]\{a\vee b, a\wedge b\} = \{a, b\}[/math]
が成り立つものとして、a ≤ b ⇔ [math]a = a\wedge b[/math] と定義するのである。これにより、全順序集合は分配束になる。
有限全順序
単に要素の数を勘定することにより、任意の空でない有限全順序集合が（従ってその任意の空でない部分集合が）最小元を持つことが確定する。すなわち、任意の有限全順序は整列順序である。任意の有限全順序が、通常の大小関係 < で順序付けられた自然数全体の成す集合 N の何れかの始片に順序同型なることは、直接証明することもできるし、任意の整列順序が何れかの順序数に順序同型なることを見てもわかる。言い換えれば、k-元集合上の全順序は、自然数の最初の k 個からなる全順序から誘導される。従て、有限全順序または順序型 ω を持つ整列順序は、順序の観点からは自然数（0 から始まるか 1 から始まるかは問わず）で付番するのが普通である。
圏論的記述
順序を保つ写像 f（a ≤ b ならば f(a) ≤ f(b)）を射として、全順序集合の全体は半順序集合の圏の充満部分圏になる。
このとき、二つの全順序集合の間の全単射な射はこの圏における同型射になる。
順序位相
任意の全順序集合 X に対して、開区間は
- (a, b) = {x : a < x かつ x < b},
- (−∞, b) = {x : x < b},
- (a, ∞) = {x : a < x},
- (−∞, ∞) = X
などと定義することができる。これらの開区間を用いて任意の順序集合上に位相を定義することができる（順序位相の項を参照）。
一つの集合上に複数の順序が定義されているとき、そのそれぞれから誘導される順序位相について考えることができる。例えば、自然数の集合 N に小なり < と大なり > の二つの全順序を考えると、< の誘導する N の順序位相も > の誘導する N の順序位相も考えられる（今の場合は両者は一致するが、一般には必ずしも一致しない）。
全順序の誘導する順序位相は、遺伝的正規であることが示せる。
完備性
全順序集合が完備 (complete) であるとは、空でなく上界を持つ任意の部分集合が上限を持つことをいう。例えば実数全体の成す集合 R は完備だが、有理数全体の成す集合 Q はそうでない。
集合 X が完備となるような順序位相の性質についての結果はいくつもある。
- X 上の順序位相が連結ならば X は完備である。
- X が順序位相に関して連結となる必要十分条件は、それが完備かつ X に「ギャップ」がないことである（ここで「ギャップ」は X の適当な二点 a, b (a < b) に対して a < c < b を満たす点 c が存在しないことをいう）。
- X が完備となる必要十分条件は、その順序位相に関する任意の閉有界集合がコンパクトとなることである。
完備束を成す全順序集合はその順序位相に関してコンパクトである。実数からなる閉区間（例えば単位閉区間 [0,1] ）や、拡大実数直線はそういった例である。この二つの例の間には順序を保つ同相がある。
順序の和
二つの順序 [math](A_1,\le_1)[/math] と [math](A_2,\le_2)[/math] の非交和と呼ばれる自然な順序 [math]\le_+[/math] が和集合 [math]A_1\cup A_2[/math] 上に定義される。しばしばこれを順序集合の和と呼び、単に [math]A_1+A_2[/math] で表す。
- [math]x,y\in A_1\cup A_2[/math] に対し [math]x\le_+ y[/math] は以下の何れかひとつを満足することと定められる:
- [math]x,y\in A_1[/math] かつ [math]x\le_1 y[/math]
- [math]x,y\in A_2[/math] かつ [math]x\le_2 y[/math]
- [math]x\in A_1[/math] かつ [math]y\in A_2[/math]
直観的にはこれは二番目の集合の各元を一番目の集合の最大元の後ろに並べることを意味する。
より一般に、全順序付けられた添字集合 [math](I,\le)[/math] の各元 [math]i\in I[/math] に対して全順序集合 [math](A_i,\le_i)[/math] が対応して、各集合は対ごとに交わらないものとするとき、[math]\bigcup_i A_i[/math] 上の自然な全順序が
- [math]x,y\in \bigcup_{i\in I} A_i[/math] に対して [math]x\le y[/math] であるとは、
- 適当な [math]i\in I[/math] について [math] x\le_i y [/math] となるか
- [math]I[/math] 上で [math]i\lt j[/math] なる添字について [math] x\in A_i[/math] かつ [math] y\in A_j[/math] となること
と置くことにより定義される。
全順序集合の直積上の順序
二つの全順序集合の直積集合上に三つの順序を入れることができる。強い順に並べると
- 辞書式順序: (a,b) ≤ (c,d) ⇔ a < c または (a = c かつ b ≤ d). (これはまた全順序を与える)
- 積順序: (a,b) ≤ (c,d) ⇔ a ≤ c かつ b ≤ d (これは半順序になる)..
- 対応する狭義全順序の直積関係: (a,b) ≤ (c,d) ⇔ (a < c かつ b < d) または (a = c かつ b = d) (これも半順序).
これら三種の順序は二つより多くの直積の場合にも同様に定義することができる。
数ベクトル空間 Rn にこれらのそれぞれを適用して、順序線型空間にすることができる。
Rn の部分集合上定義される実 n-変数の実函数は、その部分集合上に狭義弱順序と対応する全前順序を定める。
関連する構造
反対称、推移的かつ反射的（だが必ずしも完全でない）二項関係は半順序と言う。
全順序を緩めて得られる全順序性と相互に読み替えられる非自明な構造はそれほどない。向きを忘れれば媒介関係が得られ、端点の位置を忘れれば巡回順序が、それらの両方を忘れれば分離関係が出る[3]。
関連項目
注釈
- ↑ Nederpelt, Rob (2004). “Chapter 20.2: Ordered Sets. Orderings”, Logical Reasoning: A First Course, 3rd, Revised, Texts in Computing, King's College Publications. ISBN 0-9543006-7-X.
- ↑ Nederpelt, Rob (2004). “Chapter 20.3: Ordered Sets. Linear orderings”, Logical Reasoning: A First Course, 3rd, Revisied, Texts in Computing, King's College Publications. ISBN 0-9543006-7-X.
- ↑ Macpherson, H. Dugald (2011), “A survey of homogeneous structures”, Discrete Mathematics, doi:10.1016/j.disc.2011.01.024 . 28 April 2011閲覧.
参考文献
- George Grätzer (1971). Lattice theory: first concepts and distributive lattices. W. H. Freeman and Co. ISBN 0-7167-0442-0
- John G. Hocking and Gail S. Young (1961). Topology. Corrected reprint, Dover, 1988. ISBN 0-486-65676-4