World Library  
Flag as Inappropriate
Email this Article

Order isomorphism

Article Id: WHEBN0023916899
Reproduction Date:

Title: Order isomorphism  
Author: World Heritage Encyclopedia
Language: English
Subject: Dense order, Prefix order, Subset, Duality (mathematics), Real line
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

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

Definition

Formally, given two posets (S,\le_S) and (T,\le_T), an order isomorphism from (S,\le_S) to (T,\le_T) is a bijective function f from S to T with the property that, for every x and y in S, x \le_S y if and only if f(x)\le_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\le y and y\le 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]

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 \le denotes the usual numerical comparison), since −x ≥ −y if and only if xy.[5]
  • 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.[6]

Order types

If f is an order isomorphism, then so is its inverse function. Also, if f is an order isomorphism from (S,\le_S) to (T,\le_T) and g is an order isomorphism from (T,\le_T) to (U,\le_U), then the function composition of f and g is itself an order isomorphism, from (S,\le_S) to (U,\le_U).[7]

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

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

Notes

  1. ^ Block (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. ^ See example 4 of Ciesielski (1997), p. 39., for a similar example with integers in place of real numbers.
  6. ^ Ciesielski (1997), example 1, p. 39.
  7. ^ Ciesielski (1997); Schröder (2003).
  8. ^ Ciesielski (1997).

References

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.