全ぜん順序じゅんじょ

数学すうがくにおける全ぜん順序じゅんじょ（ぜんじゅんじょ、英えい: total order）とは、集合しゅうごうでの二に項こう関係かんけいで、推移すいい律りつ、反対称律はんたいしょうりつかつ完全かんぜん律りつの全すべてを満みたすもののことである。

単純たんじゅん順序じゅんじょ（たんじゅんじゅんじょ、英えい: simple order）、線型せんけい順序じゅんじょ（せんけいじゅんじょ、英えい: linear order）とも呼よばれる。

集合しゅうごうと全ぜん順序じゅんじょを組くみにしたものは、全ぜん順序じゅんじょ集合しゅうごう (totally ordered set), 線型せんけい順序じゅんじょ集合しゅうごう (linearly ordered set), 単純たんじゅん順序じゅんじょ集合しゅうごう (simply ordered set) あるいは鎖くさり (chain) と呼よばれる。

即すなわち、集合しゅうごう $X$ 上うえの関係かんけい $\leq$ が全ぜん順序じゅんじょであるとは、 $\leq$ が、 $X$ の任意にんいの元もと $a, b, c$ に対たいして、次つぎの4条件じょうけんを満みたすことである：

反射はんしゃ律りつ： $X$ の任意にんいの元もと $a$ に対たいし、 $a \leq a$ が成なり立たつ。^{[注釈ちゅうしゃく 1]}

反対称律はんたいしょうりつ： $a \leq b$ かつ $b \leq a$ ならば $a = b$
推移すいい律りつ： $a \leq b$ かつ $b \leq c$ ならば $a \leq c$
完全かんぜん律りつ（比較ひかく可能かのう）： $a \leq b$ または $b \leq a$ の何いずれかが必かならず成なり立たつ

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

狭義きょうぎ全ぜん順序じゅんじょ

任意にんいの（広義こうぎ）全ぜん順序じゅんじょ関係かんけい ≤ に対たいし、それに付随ふずいする非対称ひたいしょう（従したがって非ひ反射はんしゃ的てき）な狭義きょうぎ全ぜん順序じゅんじょ (strict total order) と呼よばれる関係かんけい $<$ が存在そんざいする。これは次つぎの互たがいに同値どうちな二に種類しゅるいの仕方しかたで定義ていぎすることができる。

$a < b \Leftrightarrow a \leq b$ かつ $a \neq b$
$a < b \Leftrightarrow b \leq a$ でない

後者こうしゃは、関係かんけい $<$ が $\leq$ の補ほ関係かんけい（英語えいご版ばん）の逆ぎゃく関係かんけいであることを意味いみするものである。

性質せいしつ：

推移すいい律りつ： $a < b$ かつ $b < c$ ならば $a < c$
三さん分ふん律りつ（英語えいご版ばん）： $a < b$ または $b < a$ または $a = b$ の何いずれか一ひとつのみが成立せいりつする。
恒等こうとう性せいを付随ふずいする同値どうち関係かんけいとする狭義きょうぎ弱じゃく順序じゅんじょ（英語えいご版ばん）である。

推移すいい的てきかつ三さん分ふん的てきな二に項こう関係かんけい $<$ が最初さいしょに与あたえられたとき、そこから（広義こうぎの）全ぜん順序じゅんじょ ≤ を定さだめることも、次つぎの同値どうちな二に種類しゅるいの方法ほうほう

$a \leq b \Leftrightarrow a < b$ または $a = b$
$a \leq b \Leftrightarrow b < a$ でない

でできる。

他ほかにも2つ、これらの補ほ関係かんけい $\geq$ と $>$ を考かんがえることができ、四よっつ組ぐみ ${<, >, \leq, \geq}$ はどれからでも他たの3種類しゅるいを導出どうしゅつすることができるから、集合しゅうごうが全ぜん順序付じゅんじょづけられることをいうのにいずれの関係かんけいを用もちいて定義ていぎ・記述きじゅつしてもよい（特とくに広義こうぎか狭義きょうぎかは記号きごうで区別くべつできる）。

例れい

通常つうじょうのアルファベット順じゅん（ $A < B < C$ ）はアルファベット全体ぜんたいの成なす集合しゅうごうを全ぜん順序付じゅんじょづける。
全ぜん順序じゅんじょ集合しゅうごうの任意にんいの部分ぶぶん集合しゅうごうは、もとの全体ぜんたい集合しゅうごうの順序じゅんじょをその部分ぶぶん集合しゅうごうに制限せいげんすることで、全ぜん順序付じゅんじょづけられる。
順序じゅんじょ数すうからなる任意にんいの集合しゅうごう、あるいは基数きすうからなる任意にんいの集合しゅうごう。これらは単たんに全ぜん順序じゅんじょ集合しゅうごうであるばかりでなく、さらに強つよく整列せいれつ集合しゅうごうになる。
集合しゅうごう $X$ に対たいして、 $X$ から全ぜん順序じゅんじょ集合しゅうごうへの単たん射い写像しゃぞう $f$ が存在そんざいするとき、 $x 1 < x 2 \Leftrightarrow f (x 1) < f (x 2)$ で $X$ での順序じゅんじょを定さだめると、 $X$ は全ぜん順序じゅんじょ集合しゅうごうになる。
適当てきとうな順序じゅんじょ数すうで添字そえじ付つけられた全ぜん順序じゅんじょ集合しゅうごう族ぞくのデカルト積つもるは、その上うえに辞書じしょ式しき順序じゅんじょを入いれることにより、それ自身じしん全ぜん順序じゅんじょ集合しゅうごうになる。例たとえば、アルファベット順じゅんに並ならべた任意にんいの語かたりの集合しゅうごうが全ぜん順序付じゅんじょづけられることは、（スペースの記号きごうをどの文字もじよりも小ちいさいものとして加くわえた）アルファベットの集合しゅうごうの可算かさん個このコピーからなる集合しゅうごう族ぞくのデカルト積つもるに辞書じしょ式しき順序じゅんじょを入いれることで理解りかいできる。
実数じっすう全体ぜんたいの成なす集合しゅうごう R は通常つうじょうの大小だいしょう関係かんけい ("<" あるいは ">") によって全ぜん順序付じゅんじょづけられる。従したがってその部分ぶぶん集合しゅうごうとしての、自然しぜん数すう全体ぜんたいの成なす集合しゅうごう N, 整数せいすう全体ぜんたいの成なす集合しゅうごう Z, 有理数ゆうりすう全体ぜんたいの成なす集合しゅうごう Q なども全ぜん順序じゅんじょ集合しゅうごうになる。これらは何いずれも、ある性質せいしつに関かんして最小さいしょうの全ぜん順序じゅんじょ集合しゅうごうとして（同型どうけいを除のぞいて）唯一ゆいいつの例れいを与あたえることが示しめせる（ここで、全ぜん順序じゅんじょ集合しゅうごう A がある性質せいしつに関かんして「最小さいしょう」とは、同おなじ性質せいしつを持もつ任意にんいの B に対たいして A に順序じゅんじょ同型どうけいな B の部分ぶぶん集合しゅうごうが存在そんざいすることをいう）。
- $N$ は上うえ界かいを持もたない最小さいしょうの全ぜん順序じゅんじょ集合しゅうごうである。
- $Z$ は上うえ界かいも下界げかいも持もたない最小さいしょうの全ぜん順序じゅんじょ集合しゅうごうである。
- $Q$ は $R$ の中なかで稠密ちゅうみつとなる最小さいしょうの全ぜん順序じゅんじょ集合しゅうごうである。ここでいう稠密ちゅうみつ性せいは $a < b$ なる任意にんいの実数じっすう $a, b$ に対たいし、 $a < q < b$ となる有理数ゆうりすう q が必かならず存在そんざいすることを言いう。
- $R$ は順序じゅんじょ位相いそう（後述こうじゅつ）に関かんして連結れんけつとなる最小さいしょうの非ひ有界ゆうかい全ぜん順序じゅんじょ集合しゅうごうである。
順序じゅんじょ体たいは定義ていぎにより全ぜん順序じゅんじょである。これは有理数ゆうりすう体たい $Q$ や実数じっすう体たい $R$ を包括ほうかつする概念がいねんである。

関連かんれんする概念がいねん

鎖くさり

全ぜん順序じゅんじょの同義語どうぎごとしても用もちいられる鎖くさり（さ、英えい: chain）は、また適当てきとうな半はん順序じゅんじょ集合しゅうごうの全ぜん順序じゅんじょ部分ぶぶん集合しゅうごうに対たいしても用もちいられる。後者こうしゃの意味いみでの鎖くさりはツォルンの補題ほだいで極きわめて重要じゅうような役割やくわりを果はたす。

例たとえば整数せいすう全体ぜんたいの成なす集合しゅうごう $Z$ に包含ほうがん関係かんけいで半はん順序じゅんじょを入いれた半はん順序じゅんじょ集合しゅうごうを考かんがえると、自然しぜん数すう $n$ に対たいし、 $n$ 以下いかの自然しぜん数すう全体ぜんたいの成なす部分ぶぶん集合しゅうごう $I n$ からなる集合しゅうごう族ぞく ${I n | n$ は自然しぜん数すう $}$ はこの順序じゅんじょに関かんする鎖くさり、すなわち包含ほうがん関係かんけいに関かんする全ぜん順序じゅんじょ部分ぶぶん集合しゅうごうになる。実際じっさい、 $n \leq k$ ならば $I n$ は $I k$ の部分ぶぶん集合しゅうごうである。

束たば

全ぜん順序じゅんじょ集合しゅうごうを特定とくていの種類しゅるいの束たばとして定義ていぎすることもできる。つまり、任意にんいの a, b に対たいして

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

が成なり立たつものとして、a ≤ b ⇔ $a=a\wedge b$ と定義ていぎするのである。これにより、全ぜん順序じゅんじょ集合しゅうごうは分配ぶんぱい束たばになる。

有限ゆうげん全ぜん順序じゅんじょ

単たんに要素ようその数かずを勘定かんじょうする（英語えいご版ばん）ことにより、任意にんいの空そらでない有限ゆうげん全ぜん順序じゅんじょ集合しゅうごうが（従したがってその任意にんいの空そらでない部分ぶぶん集合しゅうごうが）最小さいしょう元もとを持もつことが確定かくていする。すなわち、任意にんいの有限ゆうげん全ぜん順序じゅんじょは整列せいれつ順序じゅんじょである。任意にんいの有限ゆうげん全ぜん順序じゅんじょが、通常つうじょうの大小だいしょう関係かんけい $<$ で順序付じゅんじょづけられた自然しぜん数すう全体ぜんたいの成なす集合しゅうごう $N$ の何いずれかの始はじめ片へん（英語えいご版ばん）に順序じゅんじょ同型どうけいなることは、直接ちょくせつ証明しょうめいすることもできるし、任意にんいの整列せいれつ順序じゅんじょが何いずれかの順序じゅんじょ数すうに順序じゅんじょ同型どうけいなることを見みても分わかる。い換いかえれば、k-元もと集合しゅうごう上うえの全ぜん順序じゅんじょは、自然しぜん数すうの最初さいしょの $k$ 個こからなる全ぜん順序じゅんじょから誘導ゆうどうされる。従したがって、有限ゆうげん全ぜん順序じゅんじょまたは順序じゅんじょ型がた $ω おめが$ を持もつ整列せいれつ順序じゅんじょは、順序じゅんじょの観点かんてんからは自然しぜん数すう（0 から始はじまるか 1 から始はじまるかは問とわず）で付ふ番ばんするのが普通ふつうである。

圏けん論ろん的てき記述きじゅつ

順序じゅんじょを保たもつ写像しゃぞう $f$ （ $a \leq b ならば f (a) \leq f (b)$ ）を射いとして、全ぜん順序じゅんじょ集合しゅうごうの全体ぜんたいは半はん順序じゅんじょ集合しゅうごうの圏けんの充満じゅうまん部分ぶぶん圏けんになる。

このとき、二ふたつの全ぜん順序じゅんじょ集合しゅうごうの間あいだの全ぜん単たん射しゃな射いはこの圏けんにおける同型どうけい射しゃになる。

順序じゅんじょ位相いそう

任意にんいの全ぜん順序じゅんじょ集合しゅうごう $X$ に対たいして、開ひらき区間くかんが

(a, b) = {x | a < x and x < b}

(-\infty, b) = {x | x < b}

(a, \infty) = {x | a < x}

(-\infty, \infty) = X

で定義ていぎできる。これらの開ひらき区間くかんを用もちいて任意にんいの順序じゅんじょ集合しゅうごう上じょうに位相いそうを定義ていぎすることができる（順序じゅんじょ位相いそう（英語えいご版ばん）の項こうを参照さんしょう）。

一ひとつの集合しゅうごう上じょうに複数ふくすうの順序じゅんじょが定義ていぎされているとき、そのそれぞれから誘導ゆうどうされる順序じゅんじょ位相いそうについて考かんがえることができる。例たとえば、自然しぜん数すうの集合しゅうごう $N$ に小しょうなり $<$ と大だいなり $>$ の二ふたつの全ぜん順序じゅんじょを考かんがえると、 $<$ の誘導ゆうどうする $N$ の順序じゅんじょ位相いそうも $>$ の誘導ゆうどうする $N$ の順序じゅんじょ位相いそうも考かんがえられる（今いまの場合ばあいは両者りょうしゃは一致いっちするが、一般いっぱんには必かならずしも一致いっちしない）。

全ぜん順序じゅんじょの誘導ゆうどうする順序じゅんじょ位相いそうは、遺伝いでん的てき正規せいきであることが示しめせる。

完備かんび性せい

全ぜん順序じゅんじょ集合しゅうごうが完備かんび (complete) であるとは、空そらでなく上うえ界かいを持もつ任意にんいの部分ぶぶん集合しゅうごうが上限じょうげんを持もつことをいう。例たとえば実数じっすう全体ぜんたいの成なす集合しゅうごう $R$ は完備かんびだが、有理数ゆうりすう全体ぜんたいの成なす集合しゅうごう $Q$ はそうでない。

集合しゅうごう X が完備かんびとなるような順序じゅんじょ位相いそうの性質せいしつについての結果けっかはいくつもある。

X 上うえの順序じゅんじょ位相いそうが連結れんけつならば X は完備かんびである。
X が順序じゅんじょ位相いそうに関かんして連結れんけつとなる必要ひつよう十じゅう分ふん条件じょうけんは、それが完備かんびかつ X に「ギャップ」がないことである（ここで「ギャップ」は X の適当てきとうな二に点てん a, b ( $a < b$ ) に対たいして $a < c < b$ を満みたす点てん c が存在そんざいしないことをいう）。
X が完備かんびとなる必要ひつよう十じゅう分ふん条件じょうけんは、その順序じゅんじょ位相いそうに関かんする任意にんいの閉有界かい集合しゅうごうがコンパクトとなることである。

完備かんび束たばを成なす全ぜん順序じゅんじょ集合しゅうごうはその順序じゅんじょ位相いそうに関かんしてコンパクトである。実数じっすうからなる閉区間あいだ（例たとえば単位たんい閉区間あいだ $[0,1]$ ）や、拡大かくだい実数じっすう直線ちょくせんはそういった例れいである。この二ふたつの例れいの間あいだには順序じゅんじょを保たもつ同相どうしょうがある。

順序じゅんじょの和わ

二ふたつの順序じゅんじょ $(A_{1},\leq _{1})$ と $(A_{2},\leq _{2})$ の非ひ交和と呼よばれる自然しぜんな順序じゅんじょ $\leq _{+}$ が和わ集合しゅうごう $A_{1}\cup A_{2}$ 上うえに定義ていぎされる。しばしばこれを順序じゅんじょ集合しゅうごうの和わと呼よび、単たんに $A_{1}+A_{2}$ で表あらわす。

x,y\in A_{1}\cup A_{2}

に対たいし

x\leq _{+}y

は以下いかの何いずれかひとつを満足まんぞくすることと定さだめられる:

$x,y\in A_{1}$ かつ $x\leq _{1}y$
$x,y\in A_{2}$ かつ $x\leq _{2}y$
$x\in A_{1}$ かつ $y\in A_{2}$

直観ちょっかん的てきにはこれは二に番目ばんめの集合しゅうごうの各かく元もとを一いち番目ばんめの集合しゅうごうの最大さいだい元もとの後うしろに並ならべることを意味いみする。

より一般いっぱんに、全ぜん順序付じゅんじょづけられた添字そえじ集合しゅうごう $(I,\leq )$ の各かく元もと $i\in I$ に対たいして全ぜん順序じゅんじょ集合しゅうごう $(A_{i},\leq _{i})$ が対応たいおうして、各かく集合しゅうごうは対たいごとに交まじわらないものとするとき、 $\bigcup _{i}A_{i}$ 上うえの自然しぜんな全ぜん順序じゅんじょが

x,y\in \bigcup _{i\in I}A_{i}

に対たいして

x\leq y

であるとは、

適当てきとうな $i\in I$ について $x\leq _{i}y$ となるか
$I$ 上うえで $i<j$ なる添字そえじについて $x\in A_{i}$ かつ $y\in A_{j}$ となること

と置おくことにより定義ていぎされる。