Total orderとは - わかりやすく解説 Weblio辞書 (original) (raw)

出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。記事の信頼性向上にご協力をお願いいたします。（2019年6月）

数学における全順序（ぜんじゅんじょ、英: _total order_）とは、集合での二項関係で、推移律、反対称律かつ完全律の全てを満たすもののことである。

単純順序（たんじゅんじゅんじょ、英: _simple order_）、線型順序（せんけいじゅんじょ、英: _linear order_）とも呼ばれる。

集合と全順序を組にしたものは、全順序集合 (totally ordered set), 線型順序集合 (linearly ordered set), 単純順序集合 (simply ordered set) あるいは鎖 (chain) と呼ばれる。

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

反対称性によって a < b かつ b < a であるという不確定な状態は排除される[2]。完全性を持つ関係は、その集合の任意の二元がその関係で比較可能（英語版）であることを意味する。これはまた、元を直線に並べた図式によってその集合が表せるということでもあり、それは「線型」順序の名の由来である[3]。また完全性から反射性 (a ≤ a) が出るから、全順序は半順序の公理を満たす。半順序は（完全性の代わりに反射性のみが課されるという意味で）全順序よりも弱い条件である。与えられた半順序を拡張して全順序をえることは、半順序の線型拡張（英語版）と呼ばれる。

狭義全順序

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

後者は、関係 < が ≤ の補関係（英語版）の逆関係であることを意味するものである。

性質：

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

でできる。

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

例

関連する概念

鎖

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

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

束

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

{ a ∨ b , a ∧ b } = { a , b } {\displaystyle \{a\vee b,a\wedge b\}=\{a,b\}}

この節には参考文献や外部リンクの一覧が含まれていますが、**脚注によって参照されておらず、情報源が不明瞭です**。脚注を導入して、記事の信頼性向上にご協力ください。（2019年6月）