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

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

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

Order isomorphisms順序同型じゅんじょどうけい and well-orders整列順序せいれつじゅんじょ

The purpose of studying partial orders半順序関係はんじゅんじょかんけい is to treat size and comparison not only as numerical values, but also as structure. The important ideas here are maps写像しゃぞう that preserve order and order isomorphisms順序同型じゅんじょどうけい, which express that two order structures are essentially the same.

For an order isomorphism順序同型じゅんじょどうけい, look not at the names or representations of elements, but at whether the comparison relation itself is the same. For a well-order整列順序せいれつじゅんじょ, every nonempty subset部分集合ぶぶんしゅうごう, not just the whole set, is required to have a 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 について成立せいりつすることである。

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

1Order-preserving maps

Order note: the formal lectures on maps写像しゃぞう and bijections全単射ぜんたんしゃ appear later. On this page, use a map as a rule assigning one destination to each element, and use a bijection as a correspondence with neither overlaps nor leftovers.

For partially ordered sets半順序集合はんじゅんじょしゅうごう $$P,Q$$P,Q, a map写像しゃぞう $$f:P\to Q$$f:P\to Q is an order-preserving map順序保存写像じゅんじょほぞんしゃぞう if, for every $$x,y\in P$$x,y\in P,

This means that the map does not destroy comparable relationships. It does not have to preserve the names of elements or numerical distances. What it preserves is the order順序じゅんじょ.

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 は順序構造じゅんじょこうぞうとして同おなじである。元げんの名前なまえは違ちがっても、どれがどれ以下いかかという情報じょうほうは完全かんぜんに対応たいおうする。

2Order isomorphism

A map写像しゃぞう $$f:P\to Q$$f:P\to Q is an order isomorphism順序同型じゅんじょどうけい if it is a bijection全単射ぜんたんしゃ and, for every $$x,y\in P$$x,y\in P,

When an order isomorphism順序同型じゅんじょどうけい exists, $$P$$P and $$Q$$Q are the same as order structures. Even if the element names are different, the information about which element is below which other element corresponds perfectly.

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 元げんが比較不能ひかくふのうである。部分集合ぶぶんしゅうごうとして取とり出だしたときの内部ないぶの比較ひかくだけを見みる。

3Chains and antichains

A chain鎖くさり is a subset部分集合ぶぶんしゅうごう in which every two elements are comparable. An antichain反鎖はんくさり is a subset in which any two distinct elements are incomparable.

If the power set冪集合べきしゅうごう $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(\right\{1,2\left\}\right)$$\mathcal P(\{1,2\}) is ordered by inclusion, then

is a chain鎖くさり. On the other hand,

is an antichain反鎖はんくさり, because neither set contains the other.

In a chain鎖くさり, every two elements are comparable. In an antichain反鎖はんくさり, any two distinct elements are incomparable. Only comparisons inside the chosen subset matter.

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より強つよい条件じょうけんである。全体集合ぜんたいしゅうごうに最小元さいしょうげんがあるだけでは足たりず、どの空からでない部分集合ぶぶんしゅうごうを見みても最小元さいしょうげんが必要ひつようである。

4Well-orders

A totally ordered set全順序集合ぜんじゅんじょしゅうごう $$P$$P is a well-order整列順序せいれつじゅんじょ if every nonempty subset部分集合ぶぶんしゅうごう has a least element最小元さいしょうげん.

The natural numbers自然数しぜんすう $$\mathbb{N}$$\mathbb N with the usual order are well-ordered. On the other hand, the integers整数せいすう $$\mathbb{Z}$$\mathbb Z with the usual order form a totally ordered set全順序集合ぜんじゅんじょしゅうごう, but not a well-order整列順序せいれつじゅんじょ, because $$\mathbb{Z}$$\mathbb Z itself has no least element.

A well-order整列順序せいれつじゅんじょ is a stronger condition than a total order全順序ぜんじゅんじょ. It is not enough for the whole set to have a least element; every nonempty subset must have a least element.

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を定義ていぎし、これらも順序同型じゅんじょどうけいで保存ほぞんされることを扱あつかう。

5What we are viewing without changing

An order-preserving map順序保存写像じゅんじょほぞんしゃぞう preserves the direction of order. An order isomorphism順序同型じゅんじょどうけい preserves properties defined so far purely from the order: comparability, greatest and least elements, maximal and minimal elements, chains, and antichains.

Conversely, element names, concrete representations, and numerical distances are not what is being preserved.

For example, if $$f:P\to Q$$f:P\to Q is an order isomorphism順序同型じゅんじょどうけい and $$g$$g is greatest in $$P$$P, then for every $$q\in Q$$q\in Q there is $$p\in P$$p\in P with $$f\left(p\right)=q$$f(p)=q, and $$p{\text{[PARSE ERROR: Undefined("Command("le")")]}}_{P}g$$p\le_P g gives $$q=f\left(p\right){\text{[PARSE ERROR: Undefined("Command("le")")]}}_{Q}f\left(g\right)$$q=f(p)\le_Q f(g). Thus $$f\left(g\right)$$f(g) is greatest in $$Q$$Q.

The following lecture on lattices束そく defines upper bounds上界じょうかい, lower bounds下界かかい, joins結むすび, and meets交まじわり], and explains why these are also preserved by order isomorphisms.

6まとめ

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

7関連かんれんリンク

6Summary

An order isomorphism順序同型じゅんじょどうけい says that two order structures remain essentially the same after renaming elements. A well-order整列順序せいれつじゅんじょ is the strong condition that every nonempty subset has a least element, supporting induction帰納法きのうほう and minimal-counterexample arguments.

7Related links

8演習えんしゅうリンク

8Exercise links