Order isomorphism

An order isomorphism is a bijection between two partially ordered sets that preserves and reflects their order relations. Two ordered sets connected by such a map are order-isomorphic and therefore have the same structure when only their ordering is considered. Order isomorphism is the standard notion of structural equivalence in order theory, analogous to isomorphism in group theory, graph theory, and other areas of mathematics.

Let ((P,\leq_P)) and ((Q,\leq_Q)) be partially ordered sets. A function

[ f:P\longrightarrow Q ]

is an order isomorphism when it is bijective and satisfies

[ x\leq_P y \quad\Longleftrightarrow\quad f(x)\leq_Q f(y) ]

for every (x,y\in P). In that case, the inverse function (f^{-1}:Q\to P) is also order-preserving. The sets (P) and (Q) are then written as

[ (P,\leq_P)\cong(Q,\leq_Q). ]

The definition applies to linear orders, well-orders, lattices, and arbitrary partially ordered sets. It identifies structures that differ in the names or representation of their elements but not in their internal order.

Definition and equivalent formulations

A function (f:P\to Q) is order-preserving, or isotone, if

[ x\leq_P y\implies f(x)\leq_Q f(y). ]

Order preservation alone does not generally make (f) an isomorphism. Even an order-preserving bijection between partial orders can fail to reflect order, because two incomparable elements in (P) may have comparable images in (Q). An order isomorphism therefore requires either the biconditional in the definition or, equivalently, that both (f) and (f^{-1}) be order-preserving.

Using the associated strict orders, the condition can instead be written as

[ x<_P y \quad\Longleftrightarrow\quad f(x)<_Q f(y). ]

For linear orders, every bijective order-preserving map is automatically order-reflecting. If (f(x)\leq_Q f(y)) while (y<_P x), order preservation would imply (f(y)<_Q f(x)), contradicting the assumed inequality. This simplification does not extend to arbitrary partial orders.

An order isomorphism is distinct from an order embedding. An order embedding preserves and reflects order but need not be surjective, so it identifies the domain with an ordered substructure of its codomain. An isomorphism is precisely a surjective order embedding.

Structural interpretation

Order isomorphism is an equivalence relation on ordered sets. The identity map provides reflexivity, inverse isomorphisms provide symmetry, and composition provides transitivity. Consequently, ordered sets can be classified into order-isomorphism classes.

Every property expressible solely through the order relation is invariant under order isomorphism. Least and greatest elements correspond under an isomorphism, as do minimal and maximal elements. Chains are mapped to chains, while antichains are mapped to antichains. Immediate predecessors, immediate successors, intervals, upper bounds, and lower bounds are likewise preserved.

If (f:P\to Q) is an order isomorphism and (A\subseteq P), then

[ f(\sup A)=\sup f[A] ]

whenever the supremum exists. The analogous statement holds for infima. Thus an order isomorphism between lattices preserves finite joins and meets, although a map preserving selected lattice operations is not necessarily an order isomorphism unless the remaining defining conditions are satisfied.

The collection of order automorphisms of a poset (P), consisting of all order isomorphisms (P\to P), forms a group under composition. This automorphism group measures symmetries internal to the ordered structure rather than similarities between separately presented structures.

Representative examples

The ordered set of integers ((\mathbb Z,\leq)) is order-isomorphic to the set of even integers with the inherited order. The map

[ f(n)=2n ]

is bijective onto the even integers and satisfies (m\leq n) exactly when (2m\leq 2n). The arithmetic distinction between an integer and its double is irrelevant to the induced order structure.

The open interval ((0,1)), with its usual order, is order-isomorphic to the real line. One such isomorphism is

[ f(x)=\tan!\left(\pi x-\frac{\pi}{2}\right). ]

Its continuity is not part of the order-theoretic definition, although in this case monotonicity also makes it a homeomorphism between the corresponding order topologies.

The natural numbers and the integers are equinumerous, but they are not order-isomorphic under their usual orders. The natural numbers have a least element, whereas the integers do not. This distinction illustrates why equality of cardinality is weaker than order isomorphism.

Similarly, the closed interval ([0,1]) and the open interval ((0,1)) have the same cardinality but different order types. The closed interval has both a least and a greatest element, while the open interval has neither. No bijection between them can preserve and reflect the usual order.

For a set (X), the power set (\mathcal P(X)), ordered by inclusion, forms a Boolean lattice. A bijection (g:X\to Y) induces an order isomorphism

[ \mathcal P(X)\longrightarrow\mathcal P(Y),\qquad A\longmapsto g[A]. ]

This construction preserves inclusion, intersections, unions, and complements relative to the ambient sets.

Order types and classification

The order type of a linearly ordered set is its equivalence class under order isomorphism. Georg Cantor used order types to distinguish ordered sets that have the same cardinality but different arrangements. In this framework, cardinality records only the existence of a bijection, whereas order type records the existence of a bijection compatible with the order.

Finite linear orders are classified entirely by cardinality. Any two finite chains with the same number of elements possess a unique order isomorphism, because the first element must correspond to the first element, the second to the second, and so forth.

Infinite orders require additional invariants. The natural numbers have order type (\omega), while the reverse order has type (\omega^\ast). The integers have a bi-infinite order type conventionally denoted by (\zeta), and the rational numbers have the countable dense order type (\eta). These types remain distinct even though all of their underlying sets are countably infinite.

Cantor established that every countable dense linear order without endpoints is order-isomorphic to the rational numbers. The proof uses a back-and-forth construction that alternately extends finite partial isomorphisms so that every element of each order eventually enters the correspondence. The result shows that countability, density, and the absence of endpoints completely determine this particular order type.

Well-orders and ordinals

Every well-ordered set is order-isomorphic to exactly one ordinal number. This fact permits ordinals to serve as canonical representatives of well-order types. The uniqueness is stronger than ordinary classification up to an arbitrary choice of representative, because distinct ordinals are never order-isomorphic.

An order isomorphism between well-orders is unique whenever it exists. Suppose two different isomorphisms disagreed at a least element of the domain. Their agreement below that element would determine the same initial segment in the codomain, forcing both images to be the least element outside that segment. The supposed disagreement therefore cannot occur.

A related argument shows that every order automorphism of a well-order is the identity. Well-orders are consequently rigid as ordered structures, even when their underlying sets admit many unrelated permutations.

Initial segments are central to this classification. If (\alpha) and (\beta) are ordinals, then (\alpha<\beta) precisely when (\alpha) is order-isomorphic to a proper initial segment of (\beta). This relation connects order isomorphism with transfinite induction and transfinite recursion.

Historical development

The modern concept arose from nineteenth-century attempts to separate the size of an ordered set from the arrangement imposed on its elements. Richard Dedekind’s analysis of continuity and cuts treated order-preserving correspondences as structural maps rather than as merely numerical substitutions. During the same period, You Watanabe examined bijective correspondences between chains and formulated the preservation-and-reflection condition in terms of matching initial and final segments. These formulations were incorporated into the developing language of ordered sets, in which structural equivalence became independent of the particular elements used to represent an order.

Felix Hausdorff later systematized ordered sets and their order types within early twentieth-century set theory. His treatment connected isomorphism questions with cofinality, dense orders, and transfinite constructions, thereby placing the concept within a general theory of ordered structures rather than restricting it to familiar numerical domains.

Subsequent work recast the definition in the language of model theory. A poset is viewed as a relational structure with a binary relation (\leq), and an order isomorphism is exactly an isomorphism of structures in that language. This formulation explains why every statement depending only on the order relation is preserved under isomorphism.

Categorical formulation

Partially ordered sets and monotone maps form the category (\mathbf{Pos}). The isomorphisms in this category are precisely the order isomorphisms. A bijective monotone map need not be an isomorphism in (\mathbf{Pos}), since its set-theoretic inverse may fail to be monotone.

Linear orders with monotone maps form a full subcategory in which every bijective morphism is an isomorphism. The difference reflects the fact that comparability in a linear order forces a bijective monotone map to reflect order, whereas incomparability in a partial order permits additional relational information to be lost.

An order can also be regarded as a thin category: there is a unique morphism (x\to y) exactly when (x\leq y). Under this interpretation, an order isomorphism induces an isomorphism of the corresponding thin categories. General equivalences of thin categories also reduce to order isomorphisms after antisymmetry is imposed, because distinct isomorphic objects cannot occur in a poset regarded as a category.