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最小元さいしょうげん.

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順序じゅんじょ.

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.

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.

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.

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.

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

8Exercise links