Open main menu

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 one 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]

Contents

DefinitionEdit

Formally, given two posets   and  , an order isomorphism from   to   is a bijective function   from   to   with the property that, for every   and   in  ,   if and only if  . 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   cover all the elements of   and that it preserve orderings, are enough to ensure that   is also one-to-one, for if   then (by the assumption that   preserves the order) it would follow that   and  , implying by the definition of a partial order that  .

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   and  , a function from   to   must satisfy additional properties to be regarded as an isomorphism. For example, given two partially ordered groups (po-groups)   and  , an isomorphism of po-groups from   to   is an order isomorphism that is also a group isomorphism, not merely a bijection that is an order embedding.[5]

ExamplesEdit

  • The identity function on any partially ordered set is always an order automorphism.
  • Negation is an order isomorphism from   to   (where   is the set of real numbers and   denotes the usual numerical comparison), since −x ≥ −y if and only if xy.[6]
  • The open interval   (again, ordered numerically) does not have an order isomorphism to or from the closed interval  : the closed interval has a least element, but the open interval does not, and order isomorphisms must preserve the existence of least elements.[7]

Order typesEdit

If   is an order isomorphism, then so is its inverse function. Also, if   is an order isomorphism from   to   and   is an order isomorphism from   to  , then the function composition of   and   is itself an order isomorphism, from   to  .[8]

Two partially ordered sets are said to be order isomorphic when there exists an order isomorphism from one to the other.[9] 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.

See alsoEdit

  • Permutation pattern, a permutation that is order-isomorphic to a subsequence of another permutation

NotesEdit

  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. ^ Ciesielski (1997); Schröder (2003).
  9. ^ Ciesielski (1997).

ReferencesEdit

  • 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, 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.