順序同型じゅんじょどうけいと整列順序せいれつじゅんじょ

半順序関係はんじゅんじょかんけいpartial orderを学まなぶ目的もくてきは、大小だいしょうを数値すうちだけでなく構造こうぞうとして扱あつかうことである。そこで重要じゅうようになるのが、順序じゅんじょを保たもつ写像しゃぞうmapと、順序構造じゅんじょこうぞうが本質的ほんしつてきに同おなじであることを表あらわす順序同型じゅんじょどうけいorder isomorphismである。

順序同型じゅんじょどうけいorder isomorphismでは、元げんの名前なまえや表示ひょうじではなく、比較関係ひかくかんけいそのものが同おなじかを見みる。整列順序せいれつじゅんじょwell-orderでは、全体ぜんたいだけでなく任意にんいの空からでない部分集合ぶぶんしゅうごうに最小元さいしょうげんleast elementがあることまで要求ようきゅうする。

1順序じゅんじょを保たもつ写像しゃぞう

順序上じゅんじょじょうの注意ちゅういとして、写像しゃぞうmapと全単射ぜんたんしゃbijectionの正式せいしきな講義こうぎは後あとにある。このページでは、写像しゃぞうを「各かく元げんに行いき先さきを 1 つ割わり当あてる規則きそく」、全単射ぜんたんしゃを「重かさなりも余あまりもない対応たいおう」として使つかう。

半順序集合はんじゅんじょしゅうごうpartially ordered set $$P,Q$$P,Q に対たいして、写像しゃぞう $$f:P\to Q$$f:P\to Q が順序保存写像じゅんじょほぞんしゃぞうorder-preserving mapであるとは、

が任意にんいの $$x,y\in P$$x,y\in P について成立せいりつすることである。

これは「比較ひかくできる関係かんけいを壊こわさない」ことを意味いみする。異ことなる元げんを異ことなる先さきへ送おくる必要ひつようや、数値すうちとしての距離きょりを保たもつ必要ひつようはない。保存ほぞんするのは順序じゅんじょである。

2順序同型じゅんじょどうけい

写像しゃぞう $$f:P\to Q$$f:P\to Q が全単射ぜんたんしゃbijectionであり、さらに

を任意にんいの $$x,y\in P$$x,y\in P について満みたすとき、$$f$$f を順序同型じゅんじょどうけいorder isomorphismという。

順序同型じゅんじょどうけいorder isomorphismがあるとき、$$P$$P と $$Q$$Q は順序構造じゅんじょこうぞうとして同おなじである。元げんの名前なまえは違ちがっても、どれがどれ以下いかかという情報じょうほうは完全かんぜんに対応たいおうする。

3鎖くさりと反鎖はんくさり

鎖くさりchainとは、任意にんいの 2 元げんが比較ひかく可能かのうな部分集合ぶぶんしゅうごうsubsetである。反鎖はんくさりantichainとは、異ことなる 2 元げんが比較ひかく不能ふのうな部分集合ぶぶんしゅうごうsubsetである。

冪集合べきしゅうごうpower set $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(\right\{1,2\left\}\right)$$\mathcal P(\{1,2\}) を包含ほうがんで順序じゅんじょづけると、

は鎖くさりchainである。一方いっぽう、

は互たがいに包含ほうがんしないので反鎖はんくさりantichainである。

鎖くさりchainでは任意にんいの 2 元げんが比較可能ひかくかのうであり、反鎖はんくさりantichainでは異ことなる 2 元げんが比較不能ひかくふのうである。部分集合ぶぶんしゅうごうとして取とり出だしたときの内部ないぶの比較ひかくだけを見みる。

4整列順序せいれつじゅんじょ

全順序集合ぜんじゅんじょしゅうごうtotally ordered set $$P$$P が整列順序せいれつじゅんじょwell-orderであるとは、空からでない任意にんいの部分集合ぶぶんしゅうごうsubsetが最小元さいしょうげんleast elementを持もつことである。

自然数しぜんすう全体ぜんたい $$\mathbb{N}$$\mathbb N は通常つうじょうの大小だいしょうで整列順序せいれつじゅんじょwell-orderである。一方いっぽう、整数せいすう全体ぜんたい $$\mathbb{Z}$$\mathbb Z は通常つうじょうの大小だいしょうで全順序集合ぜんじゅんじょしゅうごうtotally ordered setだが、整列順序せいれつじゅんじょwell-orderではない。なぜなら $$\mathbb{Z}$$\mathbb Z 自身じしんが最小元さいしょうげんを持もたないからである。

整列順序せいれつじゅんじょwell-orderは全順序ぜんじゅんじょtotal orderより強つよい条件じょうけんである。全体集合ぜんたいしゅうごうに最小元さいしょうげんがあるだけでは足たりず、どの空からでない部分集合ぶぶんしゅうごうを見みても最小元さいしょうげんが必要ひつようである。

5何なにを変かえずに見みているか

順序保存写像じゅんじょほぞんしゃぞうorder-preserving mapは、順序じゅんじょの向むきを保たもつ。順序同型じゅんじょどうけいorder isomorphismは、比較可能性ひかくかのうせい、最大元さいだいげんgreatest element、最小元さいしょうげんleast element、極大元きょくだいげんmaximal element、極小元きょくしょうげんminimal element、鎖くさりchain、反鎖はんくさりantichainなど、ここまでに定義ていぎした順序的じゅんじょてきな性質せいしつを保たもつ。

逆ぎゃくに、元げんの名前なまえ、具体的ぐたいてきな表示ひょうじ、数値すうちとしての距離きょりは保存対象ほぞんたいしょうではない。

たとえば $$f:P\to Q$$f:P\to Q が順序同型じゅんじょどうけいorder isomorphismで、$$g$$g が $$P$$P の最大元さいだいげんなら、任意にんいの $$q\in Q$$q\in Q に対たいして $$f\left(p\right)=q$$f(p)=q となる $$p\in P$$p\in P が存在そんざいし、$$p{\text{[PARSE ERROR: Undefined("Command("le")")]}}_{P}g$$p\le_P g だから $$q=f\left(p\right){\text{[PARSE ERROR: Undefined("Command("le")")]}}_{Q}f\left(g\right)$$q=f(p)\le_Q f(g) である。したがって $$f\left(g\right)$$f(g) は $$Q$$Q の最大元さいだいげんである。

この後あとの束そくlatticeの講義こうぎでは、上界じょうかいupper bound・下界かかいlower bound・結むすびjoin・交まじわりmeetを定義ていぎし、これらも順序同型じゅんじょどうけいで保存ほぞんされることを扱あつかう。

6まとめ

順序同型じゅんじょどうけいorder isomorphismは、元げんの名前なまえを変かえても順序構造じゅんじょこうぞうが本質的ほんしつてきに同おなじであることを表あらわす。整列順序せいれつじゅんじょwell-orderは、任意にんいの空からでない部分集合ぶぶんしゅうごうに最小元さいしょうげんがあるという強つよい条件じょうけんで、帰納法きのうほうや最小反例法さいしょうはんれいほうを支ささえる。

7関連かんれんリンク

8演習えんしゅうリンク