全順序

テンプレート:参照方法 数学における全順序（ぜんじゅんじょ、テンプレート:Lang-en-short）とは、集合での二項関係で、推移律、反対称律かつ完全律の全てを満たすもののことである。

単純順序（たんじゅんじゅんじょ、テンプレート:Lang-en-short）、線型順序（せんけいじゅんじょ、テンプレート:Lang-en-short）とも呼ばれる。

集合と全順序を組にしたものは、全順序集合（テンプレート:Lang-en-short）、線型順序集合（テンプレート:Lang-en-short）、単純順序集合（テンプレート:Lang-en-short）あるいは鎖（テンプレート:Lang-en-short）と呼ばれる。

即ち、集合 テンプレート:Mvar 上の関係 テンプレート:Mathが全順序であるとは、テンプレート:Mathが、テンプレート:Mvar の任意の元 テンプレート:Math2 に対して、次の4条件を満たすことである：

• 反射律：テンプレート:Mvar の任意の元 テンプレート:Mvar に対し、テンプレート:Math が成り立つ。テンプレート:Efn

• 反対称律：テンプレート:Math かつ テンプレート:Math ならば テンプレート:Math
• 推移律：テンプレート:Math かつ テンプレート:Math ならば テンプレート:Math
• 完全律（比較可能）：テンプレート:Math または テンプレート:Math の何れかが必ず成り立つ

反対称性によって テンプレート:Math かつ テンプレート:Math であるという不確定な状態は排除される。完全性を持つ関係は、その集合の任意の二元がその関係でテンプレート:仮リンクであることを意味する。これはまた、元を直線に並べた図式によってその集合が表せるということでもあり、それは「線型」順序の名の由来である。また完全性から反射性 (テンプレート:Math) が出るから、全順序は半順序の公理を満たす。半順序は（完全性の代わりに反射性のみが課されるという意味で）全順序よりも弱い条件である。与えられた半順序を拡張して全順序をえることは、半順序のテンプレート:仮リンクと呼ばれる。

狭義全順序

任意の（広義）全順序関係 ≤ に対し、それに付随する非対称（従って非反射的）な狭義全順序 (strict total order) と呼ばれる関係 テンプレート:Math が存在する。これは次の互いに同値な二種類の仕方で定義することができる。

• テンプレート:Math かつ テンプレート:Math
• テンプレート:Math でない

後者は、関係 テンプレート:Math が テンプレート:Math のテンプレート:仮リンクの逆関係であることを意味するものである。

性質：

• 推移律：テンプレート:Math かつ テンプレート:Math ならば テンプレート:Math
• テンプレート:仮リンク：テンプレート:Math2 または テンプレート:Math2 または テンプレート:Math2 の何れか一つのみが成立する。
• 恒等性を付随する同値関係とするテンプレート:仮リンクである。

推移的かつ三分的な二項関係 テンプレート:Math が最初に与えられたとき、そこから（広義の）全順序 ≤ を定めることも、次の同値な二種類の方法

• テンプレート:Math または テンプレート:Math2
• テンプレート:Math でない

でできる。

他にも2つ、これらの補関係 テンプレート:Math と テンプレート:Math を考えることができ、四つ組 テンプレート:Math2 はどれからでも他の3種類を導出することができるから、集合が全順序付けられることをいうのにいずれの関係を用いて定義・記述してもよい（特に広義か狭義かは記号で区別できる）。

例

• 通常のアルファベット順（テンプレート:Math2）はアルファベット全体の成す集合を全順序付ける。
• 全順序集合の任意の部分集合は、もとの全体集合の順序をその部分集合に制限することで、全順序付けられる。
• 順序数からなる任意の集合、あるいは基数からなる任意の集合。これらは単に全順序集合であるばかりでなく、さらに強く整列集合になる。
• 集合 テンプレート:Mvar に対して、テンプレート:Mvar から全順序集合への単射写像 テンプレート:Mvar が存在するとき、テンプレート:Math2 で テンプレート:Mvar での順序を定めると、テンプレート:Mvar は全順序集合になる。
• 適当な順序数で添字付けられた全順序集合族のデカルト積は、その上に辞書式順序を入れることにより、それ自身全順序集合になる。例えば、アルファベット順に並べた任意の語の集合が全順序付けられることは、（スペースの記号をどの文字よりも小さいものとして加えた）アルファベットの集合の可算個のコピーからなる集合族のデカルト積に辞書式順序を入れることで理解できる。
• 実数全体の成す集合 テンプレート:Mathbf は通常の大小関係 ("テンプレート:Math" あるいは "テンプレート:Math") によって全順序付けられる。従ってその部分集合としての、自然数全体の成す集合 テンプレート:Mathbf, 整数全体の成す集合 テンプレート:Mathbf, 有理数全体の成す集合 テンプレート:Mathbf なども全順序集合になる。これらは何れも、ある性質に関して最小の全順序集合として（同型を除いて）唯一の例を与えることが示せる（ここで、全順序集合 A がある性質に関して「最小」とは、同じ性質を持つ任意の B に対して A に順序同型な B の部分集合が存在することをいう）。
  • テンプレート:Mathbf は上界を持たない最小の全順序集合である。
  • テンプレート:Mathbf は上界も下界も持たない最小の全順序集合である。
  • テンプレート:Mathbf は テンプレート:Mathbf の中で稠密となる最小の全順序集合である。ここでいう稠密性は テンプレート:Math2 なる任意の実数 テンプレート:Math2 に対し、テンプレート:Math となる有理数 q が必ず存在することを言う。
  • テンプレート:Mathbf は順序位相（後述）に関して連結となる最小の非有界全順序集合である。
• 順序体は定義により全順序である。これは有理数体 テンプレート:Mathbf や実数体 テンプレート:Mathbf を包括する概念である。

関連する概念

鎖

全順序の同義語としても用いられる鎖（さ、テンプレート:Lang-en-short）は、また適当な半順序集合の全順序部分集合に対しても用いられる。後者の意味での鎖はツォルンの補題で極めて重要な役割を果たす。

例えば整数全体の成す集合 テンプレート:Mathbf に包含関係で半順序を入れた半順序集合を考えると、自然数 テンプレート:Mvar に対し、テンプレート:Mvar 以下の自然数全体の成す部分集合 テンプレート:Mvar からなる集合族 テンプレート:Math は自然数テンプレート:Math はこの順序に関する鎖、すなわち包含関係に関する全順序部分集合になる。実際、テンプレート:Math2 ならば テンプレート:Mvar は テンプレート:Mvar の部分集合である。

束

全順序集合を特定の種類の束として定義することもできる。つまり、任意の a, b に対して

$\{a\vee b,a\wedge b\}=\{a,b\}$

が成り立つものとして、a ≤ b ⇔ $a=a\wedge b$ と定義するのである。これにより、全順序集合は分配束になる。

有限全順序

単にテンプレート:仮リンクことにより、任意の空でない有限全順序集合が（従ってその任意の空でない部分集合が）最小元を持つことが確定する。すなわち、任意の有限全順序は整列順序である。任意の有限全順序が、通常の大小関係 テンプレート:Math で順序付けられた自然数全体の成す集合 テンプレート:Mathbf の何れかのテンプレート:仮リンクに順序同型なることは、直接証明することもできるし、任意の整列順序が何れかの順序数に順序同型なることを見ても分かる。言い換えれば、k-元集合上の全順序は、自然数の最初の テンプレート:Mvar個からなる全順序から誘導される。従って、有限全順序または順序型 テンプレート:Mvar を持つ整列順序は、順序の観点からは自然数（0 から始まるか 1 から始まるかは問わず）で付番するのが普通である。

圏論的記述

順序を保つ写像 テンプレート:Mvar（テンプレート:Math）を射として、全順序集合の全体は半順序集合の圏の充満部分圏になる。

このとき、二つの全順序集合の間の全単射な射はこの圏における同型射になる。

順序位相

任意の全順序集合 テンプレート:Mvar に対して、開区間が

テンプレート:Math2

テンプレート:Math2

テンプレート:Math2

テンプレート:Math2

で定義できる。これらの開区間を用いて任意の順序集合上に位相を定義することができる（テンプレート:仮リンクの項を参照）。

一つの集合上に複数の順序が定義されているとき、そのそれぞれから誘導される順序位相について考えることができる。例えば、自然数の集合 テンプレート:Mathbf に小なり テンプレート:Math と大なり テンプレート:Math の二つの全順序を考えると、テンプレート:Math の誘導する テンプレート:Mathbf の順序位相も テンプレート:Math の誘導する テンプレート:Mathbf の順序位相も考えられる（今の場合は両者は一致するが、一般には必ずしも一致しない）。

全順序の誘導する順序位相は、遺伝的正規であることが示せる。

完備性

全順序集合が完備 (complete) であるとは、空でなく上界を持つ任意の部分集合が上限を持つことをいう。例えば実数全体の成す集合 テンプレート:Mathbf は完備だが、有理数全体の成す集合 テンプレート:Mathbf はそうでない。

集合 X が完備となるような順序位相の性質についての結果はいくつもある。

• X 上の順序位相が連結ならば X は完備である。
• X が順序位相に関して連結となる必要十分条件は、それが完備かつ X に「ギャップ」がないことである（ここで「ギャップ」は X の適当な二点 a, b (テンプレート:Math) に対して テンプレート:Math を満たす点 c が存在しないことをいう）。
• X が完備となる必要十分条件は、その順序位相に関する任意の閉有界集合がコンパクトとなることである。

完備束を成す全順序集合はその順序位相に関してコンパクトである。実数からなる閉区間（例えば単位閉区間 テンプレート:Math ）や、拡大実数直線はそういった例である。この二つの例の間には順序を保つ同相がある。

順序の和

二つの順序 $(A_1,{\le }_1)$ と $(A_2,{\le }_2)$ の非交和と呼ばれる自然な順序 ${\le }_{+}$ が和集合 $A_1\cup A_2$ 上に定義される。しばしばこれを順序集合の和と呼び、単に $A_1+A_2$ で表す。

$x,y\in A_1\cup A_2$ に対し $x{\le }_{+}y$ は以下の何れかひとつを満足することと定められる:

1. $x,y\in A_1$ かつ $x{\le }_{1}y$
2. $x,y\in A_2$ かつ $x{\le }_{2}y$
3. $x\in A_1$ かつ $y\in A_2$

直観的にはこれは二番目の集合の各元を一番目の集合の最大元の後ろに並べることを意味する。

より一般に、全順序付けられた添字集合 $(I,\le )$ の各元 $i\in I$ に対して全順序集合 $(A_i,{\le }_i)$ が対応して、各集合は対ごとに交わらないものとするとき、$\bigcup _i{A}_i$ 上の自然な全順序が

$x,y\in \bigcup _{i\in I}{A}_i$ に対して $x\le y$ であるとは、

1. 適当な $i\in I$ について $x{\le }_{i}y$ となるか
2. $I$ 上で $i<j$ なる添字について $x\in A_i$ かつ $y\in A_j$ となること

と置くことにより定義される。

全順序集合の直積上の順序

二つの全順序集合の直積集合上に三つの順序を入れることができる。強い順に並べると

• 辞書式順序：テンプレート:Math2 または (テンプレート:Math2 かつ テンプレート:Math2)（これはまた全順序を与える）
• 積順序：テンプレート:Math2 かつ テンプレート:Math2（これは半順序になる）
• 対応する狭義全順序の直積関係：テンプレート:Math2 かつ テンプレート:Math または テンプレート:Math2 かつ テンプレート:Math2（これも半順序）

これら三種の順序は二つより多くの直積の場合にも同様に定義することができる。

数ベクトル空間 テンプレート:Math にこれらのそれぞれを適用して、テンプレート:仮リンクにすることができる。

テンプレート:Math の部分集合上定義される実 テンプレート:Mvar変数の実函数は、その部分集合上にテンプレート:仮リンクを定める。

関連する構造

反対称、推移的かつ反射的（だが必ずしも完全でない）二項関係は半順序と言う。

両立する全順序を持つ群は全順序群と呼ぶ。

全順序を緩めて得られる全順序性と相互に読み替えられる非自明な構造はそれほどない。向きを忘れればテンプレート:仮リンクが得られ、端点の位置を忘れればテンプレート:仮リンクが、それらの両方を忘れればテンプレート:仮リンクが出る。

関連項目

• テンプレート:仮リンク
• 整列順序
• ススリンの問題
• テンプレート:仮リンク

参考文献

• 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