全順序

数学における全順序とは、集合での二項関係で、推移律、反対称律かつ完全律の全てを満たすもののことである。

単純順序、線型順序とも呼ばれる。

集合と全順序を組にしたものは、全順序集合 , 線型順序集合 , 単純順序集合  あるいは鎖  と呼ばれる。

即ち、集合 X}} 上の関係 ≤}}が全順序であるとは、≤}}が、X}} の任意の元 //a//, //b//, //c//}} に対して、次の4条件を満たすことである：

反射律：X}} の任意の元 a}} に対し、//a// ≤ //a//}} が成り立つ。
反対称律：//a// ≤ //b//}} かつ //b// ≤ //a//}} ならば
推移律：//a// ≤ //b//}} かつ //b// ≤ //c//}} ならば
完全律：//a// ≤ //b//}} または //b// ≤ //a//}} の何れかが必ず成り立つ反対称性によって //a// < //b//}} かつ //b// < //a//}} であるという不確定な状態は排除される。完全性を持つ関係は、その集合の任意の二元がその関係で比較可能性であることを意味する。これはまた、元を直線に並べた図式によってその集合が表せるということでもあり、それは「線型」順序の名の由来である。また完全性から反射性  が出るから、全順序は半順序の公理を満たす。半順序は全順序よりも弱い条件である。与えられた半順序を拡張して全順序をえることは、半順序の線型拡張と呼ばれる。

1. 狭義全順序
--------

任意の全順序関係 ≤ に対し、それに付随する非対称な狭義全順序  と呼ばれる関係 <}} が存在する。これは次の互いに同値な二種類の仕方で定義することができる。

//a// < //b// [[必要十分条件 かつ
//a// < //b// ⇔ //b// ≤ //a//}} でない後者は、関係 <}} が ≤}} の補関係の逆関係であることを意味するものである。

性質：
推移律：//a// < //b//}} かつ //b// < //c//}} ならば
三分法 ：//a// < //b//}} または //b// < //a//}} または //a// =}} //b//}} の何れか一つのみが成立する。
恒等性を付随する同値関係とする狭義弱順序である。推移的かつ三分的な二項関係 <}} が最初に与えられたとき、そこから全順序 ≤ を定めることも、次の同値な二種類の方法

//a// ≤ //b// ⇔ //a// < //b//}} または
//a// ≤ //b// ⇔ //b// < //a//}} でないでできる。

他にも2つ、これらの補関係 ≥}} と >}} を考えることができ、四つ組 mset はどれからでも他の3種類を導出することができるから、集合が全順序付けられることをいうのにいずれの関係を用いて定義・記述してもよい。

2. 例
----

通常のアルファベット順はアルファベット全体の成す集合を全順序付ける。
全順序集合の任意の部分集合は、もとの全体集合の順序をその部分集合に制限することで、全順序付けられる。
順序数からなる任意の集合、あるいは基数からなる任意の集合。これらは単に全順序集合であるばかりでなく、さらに強く整列集合になる。
集合 X}} に対して、X}}から全順序集合への単射写像 f}} が存在するとき、//x//sub で X}} での順序を定めると、X}} は全順序集合になる。
適当な順序数で添字付けられた全順序集合族のデカルト積は、その上に辞書式順序を入れることにより、それ自身全順序集合になる。例えば、アルファベット順に並べた任意の語の集合が全順序付けられることは、アルファベットの集合の可算個のコピーからなる集合族のデカルト積に辞書式順序を入れることで理解できる。
実数全体の成す集合 R}} は通常の大小関係  によって全順序付けられる。従ってその部分集合としての、自然数全体の成す集合 N}}, 整数全体の成す集合 Z}}, 有理数全体の成す集合 Q}} なども全順序集合になる。これらは何れも、ある性質に関して最小の全順序集合として唯一の例を与えることが示せる。
N}} は上界を持たない最小の全順序集合である。
Z}} は上界も下界も持たない最小の全順序集合である。
Q}} は R}} の中で稠密となる最小の全順序集合である。ここでいう稠密性は //a// < //b//}} なる任意の実数 //a//, //b//}} に対し、//a// < //q// < //b//}} となる有理数 //q// が必ず存在することを言う。
R}} は順序位相に関して連結となる最小の非有界全順序集合である。
順序体は定義により全順序である。これは有理数体 Q}} や実数体 R}} を包括する概念である。

3. 関連する概念
---------

3.1. 鎖
------

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

例えば整数全体の成す集合 Z}} に包含関係で半順序を入れた半順序集合を考えると、自然数 n}} に対し、n}} 以下の自然数全体の成す部分集合 Isub からなる集合族 は自然数 はこの順序に関する鎖、すなわち包含関係に関する全順序部分集合になる。実際、 ならば は の部分集合である。

3.2. 束
------

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

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

3.3. 有限全順序
----------

単にことにより、任意の空でない有限全順序集合が最小元を持つことが確定する。すなわち、任意の有限全順序は整列順序である。任意の有限全順序が、通常の大小関係 で順序付けられた自然数全体の成す集合 の何れかのに順序同型なることは、直接証明することもできるし、任意の整列順序が何れかの順序数に順序同型なることを見ても分かる。言い換えれば、//k//-元集合上の全順序は、自然数の最初の 個からなる全順序から誘導される。従って、有限全順序または順序型 を持つ整列順序は、順序の観点からは自然数で付番するのが普通である。

3.4. 圏論的記述
----------

順序を保つ写像 を射として、全順序集合の全体は半順序集合の圏の充満部分圏になる。

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

3.5. 順序位相
---------

任意の全順序集合 に対して、開区間が

で定義できる。これらの開区間を用いて任意の順序集合上に位相を定義することができる。

一つの集合上に複数の順序が定義されているとき、そのそれぞれから誘導される順序位相について考えることができる。例えば、自然数の集合 に小なり と大なり の二つの全順序を考えると、 の誘導する の順序位相も の誘導する の順序位相も考えられる。

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

3.6. 完備性
--------

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

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

//X// 上の順序位相が連結ならば //X// は完備である。
//X// が順序位相に関して連結となる必要十分条件は、それが完備かつ //X// に「ギャップ」がないことである。
//X// が完備となる必要十分条件は、その順序位相に関する任意の閉有界集合がコンパクトとなることである。完備束を成す全順序集合はその順序位相に関してコンパクトである。実数からなる閉区間や、拡大実数直線はそういった例である。この二つの例の間には順序を保つ同相がある。

3.7. 順序の和
---------

二つの順序 と の非交和と呼ばれる自然な順序 が和集合 上に定義される。しばしばこれを順序集合の和と呼び、単に で表す。

に対し は以下の何れかひとつを満足することと定められる:
かつ
かつ
かつ 直観的にはこれは二番目の集合の各元を一番目の集合の最大元の後ろに並べることを意味する。

より一般に、全順序付けられた添字集合 の各元 に対して全順序集合 が対応して、各集合は対ごとに交わらないものとするとき、 上の自然な全順序が

に対して であるとは、
適当な について となるか
上で なる添字について かつ となることと置くことにより定義される。

4. 全順序集合の直積上の順序
---------------

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

辞書式順序： または 
積順序： かつ
対応する狭義全順序の直積関係： かつ または かつ これら三種の順序は二つより多くの直積の場合にも同様に定義することができる。

数ベクトル空間 にこれらのそれぞれを適用して、にすることができる。

の部分集合上定義される実 変数の実函数は、その部分集合上にを定める。

5. 関連する構造
---------

反対称、推移的かつ反射的二項関係は半順序と言う。

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

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

6. 関連項目
-------

整列順序
ススリンの問題

7. 注釈
-----

8. 出典
-----

9. 参考文献
-------

George Grätzer . //Lattice theory: first concepts and distributive lattices.// W. H. Freeman and Co. ISBN 0-7167-0442-0
John G. Hocking and Gail S. Young . //Topology.// Corrected reprint, Dover, 1988. ISBN 0-486-65676-4