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

半順序関係はんじゅんじょかんけい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であるとは、

が成なり立たつことである。

これは「比較ひかくできる関係かんけいを壊こわさない」ことを意味いみする。等号とうごうや距離きょりを保存ほぞんする必要ひつようはない。保存ほぞんするのは順序じゅんじょである。

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

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であり、さらに

を満みたすとき、$$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

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は、比較ひかく可能かのう性せい、最大元さいだいげん、最小元さいしょうげん、上界じょうかい、下界かかい、結むすび、交まじわりなどの順序的じゅんじょてき性質せいしつを保たもつ。

ここで挙あげた結むすびjoinと交まじわりmeetは、次つぎの束そくlatticeの講義こうぎで正式せいしきに定義ていぎする。この段階だんかいでは、順序じゅんじょだけから決きまる性質せいしつの例れいとして名前なまえだけを先さきに挙あげている。

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

とくに $$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 の最大元さいだいげんである。

順序同型じゅんじょどうけいorder isomorphismで保存ほぞんされるのは、比較ひかく、極大元きょくだいげんmaximal element、最大元さいだいげんgreatest element、上界じょうかいupper bound、下界かかいlower boundなどの順序的じゅんじょてきな性質せいしつである。数値すうちの差さや元げんの名前なまえは保存ほぞんの対象たいしょうではない。

5What we are viewing without changing

An order-preserving map順序保存写像じゅんじょほぞんしゃぞう preserves the direction of order. An order isomorphism順序同型じゅんじょどうけい preserves order-theoretic properties such as comparability, greatest elements, least elements, upper bounds, lower bounds, joins, and meets.

The joins結むすび and meets交まじわり listed here are defined formally in the next lecture on lattices束そく. At this point, they are only being named in advance as examples of properties determined by the order alone.

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

In particular, if $$f:P\to Q$$f:P\to Q is an order isomorphism順序同型じゅんじょどうけい, then greatest elements, least elements, maximal elements, minimal elements, upper bounds, lower bounds, chains, antichains, joins, and meets are preserved. For example, if $$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.

What an order isomorphism順序同型じゅんじょどうけい preserves is order-theoretic structure such as comparison, maximal elements極大元きょくだいげん, greatest elements最大元さいだいげん, upper bounds上界じょうかい, and lower bounds下界かかい. Numerical differences and element names are not the preserved data.

6演習えんしゅうリンク

6Exercise links

7まとめ

順序同型じゅんじょどうけいorder isomorphismは、順序構造じゅんじょこうぞうが本質的ほんしつてきに同おなじであることを表あらわす。整列順序せいれつじゅんじょwell-orderは、帰納法きのうほうや最小さいしょう反例はんれい法ほうを支ささえる順序構造じゅんじょこうぞうである。

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

8関連かんれんリンク

7Summary

Order isomorphism順序同型じゅんじょどうけい expresses that two order structures are essentially the same. A well-order整列順序せいれつじゅんじょ is an order structure that supports induction帰納法きのうほう and minimal-counterexample arguments.

An order isomorphism順序同型じゅんじょどうけい says that the order structure stays the same after renaming elements. A well-order整列順序せいれつじゅんじょ is the strong order condition that every nonempty subset has a least element.

8Related links