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.

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

,

≤

S

)

{\displaystyle (S,\leq _{S})}

and

(

T

,

≤

T

)

{\displaystyle (T,\leq _{T})}

, an order isomorphism from

(

S

,

≤

S

)

{\displaystyle (S,\leq _{S})}

to

(

T

,

≤

T

)

{\displaystyle (T,\leq _{T})}

is a bijective function

f

{\displaystyle f}

from

S

{\displaystyle S}

to

T

{\displaystyle T}

with the property that, for every

x

{\displaystyle x}

and

y

{\displaystyle y}

in

S

{\displaystyle S}

,

x

≤

S

y

{\displaystyle x\leq _{S}y}

if and only if

f

(

x

)

≤

T

f

(

y

)

{\displaystyle f(x)\leq _{T}f(y)}

. That is, it is a bijective order-embedding.

It is also possible to define an order isomorphism to be a surjective order-embedding. The two assumptions that

f

{\displaystyle f}

cover all the elements of

T

{\displaystyle T}

and that it preserve orderings, are enough to ensure that

f

{\displaystyle f}

is also one-to-one, for if

f

(

x

)

=

f

(

y

)

{\displaystyle f(x)=f(y)}

then (by the assumption that

f

{\displaystyle f}

preserves the order) it would follow that

x

≤

y

{\displaystyle x\leq y}

and

y

≤

x

{\displaystyle y\leq x}

, implying by the definition of a partial order that

x

=

y

{\displaystyle x=y}

.

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