Order isomorphism

In the mathematical field of order theory, an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever two posets are order isomorphic, they can be considered to be "essentially the same" in the sense that either of the orders can be obtained from the other just by renaming of elements. Two strictly weaker notions that relate to order isomorphisms are order embeddings and Galois connections.^[1]

The idea of isomorphism can be understood for finite orders in terms of Hasse diagrams. Two finite orders are isomorphic exactly when a single Hasse diagram (up to relabeling of its elements) expresses them both, in other words when every Hasse diagram of either can be converted to a Hasse diagram of the other by simply relabeling the vertices.

Definition

Formally, given two posets $(S,\leq _{S})$ and $(T,\leq _{T})$ , an order isomorphism from $(S,\leq _{S})$ to $(T,\leq _{T})$ is a bijective function $f$ from $S$ to $T$ with the property that, for every $x$ and $y$ in $S$ , $x\leq _{S}y$ if and only if $f(x)\leq _{T}f(y)$ . That is, it is a bijective order-embedding.^[2]

It is also possible to define an order isomorphism to be a surjective order-embedding. The two assumptions that $f$ cover all the elements of $T$ and that it preserve orderings, are enough to ensure that $f$ is also one-to-one, for if $f(x)=f(y)$ then (by the assumption that $f$ preserves the order) it would follow that $x\leq y$ and $y\leq x$ , implying by the definition of a partial order that $x=y$ .

Yet another characterization of order isomorphisms is that they are exactly the monotone bijections that have a monotone inverse.^[3]

An order isomorphism from a partially ordered set to itself is called an order automorphism.^[4]

When an additional algebraic structure is imposed on the posets $(S,\leq _{S})$ and $(T,\leq _{T})$ , a function from $(S,\leq _{S})$ to $(T,\leq _{T})$ must satisfy additional properties to be regarded as an isomorphism. For example, given two partially ordered groups (po-groups) $(G,\leq _{G})$ and $(H,\leq _{H})$ , an isomorphism of po-groups from $(G,\leq _{G})$ to $(H,\leq _{H})$ is an order isomorphism that is also a group isomorphism, not merely a bijection that is an order embedding.^[5]

Examples

The identity function on any partially ordered set is always an order automorphism.
Negation is an order isomorphism from $(\mathbb {R} ,\leq )$ to $(\mathbb {R} ,\geq )$ (where $\mathbb {R}$ is the set of real numbers and $\leq$ denotes the usual numerical comparison), since −x ≥ −y if and only if x ≤ y.^[6]
The open interval $(0,1)$ (again, ordered numerically) does not have an order isomorphism to or from the closed interval $[0,1]$ : the closed interval has a least element, but the open interval does not, and order isomorphisms must preserve the existence of least elements.^[7]
By Cantor's isomorphism theorem, every unbounded countable dense linear order is isomorphic to the ordering of the rational numbers.^[8] Explicit order isomorphisms between the quadratic algebraic numbers, the rational numbers, and the dyadic rational numbers are provided by Minkowski's question-mark function.^[9]

Order types

If $f$ is an order isomorphism, then so is its inverse function. Also, if $f$ is an order isomorphism from $(S,\leq _{S})$ to $(T,\leq _{T})$ and $g$ is an order isomorphism from $(T,\leq _{T})$ to $(U,\leq _{U})$ , then the function composition of $f$ and $g$ is itself an order isomorphism, from $(S,\leq _{S})$ to $(U,\leq _{U})$ .^[10]

Two partially ordered sets are said to be order isomorphic when there exists an order isomorphism from one to the other.^[11] Identity functions, function inverses, and compositions of functions correspond, respectively, to the three defining characteristics of an equivalence relation: reflexivity, symmetry, and transitivity. Therefore, order isomorphism is an equivalence relation. The class of partially ordered sets can be partitioned by it into equivalence classes, families of partially ordered sets that are all isomorphic to each other. These equivalence classes are called order types.

Notes

^ Bloch (2011); Ciesielski (1997).
^ This is the definition used by Ciesielski (1997). For Bloch (2011) and Schröder (2003) it is a consequence of a different definition.
^ This is the definition used by Bloch (2011) and Schröder (2003).
^ Schröder (2003), p. 13.
^ This definition is equivalent to the definition set forth in Fuchs (1963).
^ See example 4 of Ciesielski (1997), p. 39., for a similar example with integers in place of real numbers.
^ Ciesielski (1997), example 1, p. 39.
^ Bhattacharjee, Meenaxi; Macpherson, Dugald; Möller, Rögnvaldur G.; Neumann, Peter M. (1997), "Rational numbers", Notes on infinite permutation groups, Texts and Readings in Mathematics, vol. 12, Berlin: Springer-Verlag, pp. 77–86, doi:10.1007/978-93-80250-91-5_9, ISBN 81-85931-13-5, MR 1632579
^ Girgensohn, Roland (1996), "Constructing singular functions via Farey fractions", Journal of Mathematical Analysis and Applications, 203 (1): 127–141, doi:10.1006/jmaa.1996.0370, MR 1412484
^ Ciesielski (1997); Schröder (2003).
^ Ciesielski (1997).

References

Bloch, Ethan D. (2011), Proofs and Fundamentals: A First Course in Abstract Mathematics, Undergraduate Texts in Mathematics (2nd ed.), Springer, pp. 276–277, ISBN 9781441971265.
Ciesielski, Krzysztof (1997), Set Theory for the Working Mathematician, London Mathematical Society Student Texts, vol. 39, Cambridge University Press, pp. 38–39, ISBN 9780521594653.
Schröder, Bernd Siegfried Walter (2003), Ordered Sets: An Introduction, Springer, p. 11, ISBN 9780817641283.
Fuchs, Laszlo (1963), Partially Ordered Algebraic Systems, Dover Publications; Reprint edition (March 5, 2014), pp. 2–3, ISBN 0486483878.

[1] Bloch (2011); Ciesielski (1997).

[2] This is the definition used by Ciesielski (1997). For Bloch (2011) and Schröder (2003) it is a consequence of a different definition.

[3] This is the definition used by Bloch (2011) and Schröder (2003).

[4] Schröder (2003), p. 13.

[5] This definition is equivalent to the definition set forth in Fuchs (1963).

[6] See example 4 of Ciesielski (1997), p. 39., for a similar example with integers in place of real numbers.

[7] Ciesielski (1997), example 1, p. 39.

[8] Bhattacharjee, Meenaxi; Macpherson, Dugald; Möller, Rögnvaldur G.; Neumann, Peter M. (1997), "Rational numbers", Notes on infinite permutation groups, Texts and Readings in Mathematics, vol. 12, Berlin: Springer-Verlag, pp. 77–86, doi:10.1007/978-93-80250-91-5_9, ISBN 81-85931-13-5, MR 1632579

[9] Girgensohn, Roland (1996), "Constructing singular functions via Farey fractions", Journal of Mathematical Analysis and Applications, 203 (1): 127–141, doi:10.1006/jmaa.1996.0370, MR 1412484

[10] Ciesielski (1997); Schröder (2003).

[11] Ciesielski (1997).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

v t e Order theory
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice

Definition

Examples

Order types

See also

Notes

References