Order isomorphism

<h2 id="definition">Definition</h2>
Formally, given two <a href="/facts/Partially_ordered_set/qb4a3FAX">posets</a> 
 
 
 
 (
 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 <a href="/facts/Bijection/j4gTuTmW">bijective function</a> 
 
 
 
 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 <a href="/facts/Order-embedding/1wCVBrRH">order-embedding</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
It is also possible to define an order isomorphism to be a <a href="/facts/Surjective/KezhLpCb">surjective</a> 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 <a href="/facts/Monotone_function/MjQK0YL2">monotone</a> <a href="/facts/Bijection/j4gTuTmW">bijections</a> that have a monotone inverse.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
An order isomorphism from a partially ordered set to itself is called an order <a href="/facts/Automorphism/WnyxNFkQ">automorphism</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
When an additional algebraic structure is imposed on the posets 
 
 
 
 (
 S
 ,
 
 ≤
 
 S
 
 
 )
 
 
 {\displaystyle (S,\leq _{S})}
 
 and 
 
 
 
 (
 T
 ,
 
 ≤
 
 T
 
 
 )
 
 
 {\displaystyle (T,\leq _{T})}
 
, a function from 
 
 
 
 (
 S
 ,
 
 ≤
 
 S
 
 
 )
 
 
 {\displaystyle (S,\leq _{S})}
 
 to 
 
 
 
 (
 T
 ,
 
 ≤
 
 T
 
 
 )
 
 
 {\displaystyle (T,\leq _{T})}
 
 must satisfy additional properties to be regarded as an isomorphism. For example, given two <a href="/facts/Partially_ordered_group/xoLNpEqH">partially ordered groups</a> (po-groups) 
 
 
 
 (
 G
 ,
 
 ≤
 
 G
 
 
 )
 
 
 {\displaystyle (G,\leq _{G})}
 
 and 
 
 
 
 (
 H
 ,
 
 ≤
 
 H
 
 
 )
 
 
 {\displaystyle (H,\leq _{H})}
 
, an isomorphism of po-groups from 
 
 
 
 (
 G
 ,
 
 ≤
 
 G
 
 
 )
 
 
 {\displaystyle (G,\leq _{G})}
 
 to 
 
 
 
 (
 H
 ,
 
 ≤
 
 H
 
 
 )
 
 
 {\displaystyle (H,\leq _{H})}
 
 is an order isomorphism that is also a <a href="/facts/Group_isomorphism/LC4N1aDw">group isomorphism</a>, not merely a bijection that is an <a href="/facts/Order_embedding/1wCVBrRH">order embedding</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h2 id="examples">Examples</h2>
<ul><li>The <a href="/facts/Identity_function/9AtsP0LC">identity function</a> on any partially ordered set is always an order automorphism.</li>
<li><a href="/facts/Additive_inverse/n8gKUmCf">Negation</a> is an order isomorphism from 
 
 
 
 (
 
 R
 
 ,
 ≤
 )
 
 
 {\displaystyle (\mathbb {R} ,\leq )}
 
 to 
 
 
 
 (
 
 R
 
 ,
 ≥
 )
 
 
 {\displaystyle (\mathbb {R} ,\geq )}
 
 (where 
 
 
 
 
 R
 
 
 
 {\displaystyle \mathbb {R} }
 
 is the set of <a href="/facts/Real_number/R02gw5Pb">real numbers</a> and 
 
 
 
 ≤
 
 
 {\displaystyle \leq }
 
 denotes the usual numerical comparison), since −x ≥ −y if and only if x ≤ y.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li>
<li>The <a href="/facts/Open_interval/e9se3vTe">open interval</a> 
 
 
 
 (
 0
 ,
 1
 )
 
 
 {\displaystyle (0,1)}
 
 (again, ordered numerically) does not have an order isomorphism to or from the <a href="/facts/Closed_interval/e9se3vTe">closed interval</a> 
 
 
 
 [
 0
 ,
 1
 ]
 
 
 {\displaystyle [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.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a></li>
<li>By <a href="/facts/Cantor%2527s_isomorphism_theorem/FGxF46Dp">Cantor's isomorphism theorem</a>, every unbounded countable dense linear order is isomorphic to the ordering of the <a href="/facts/Rational_number/VJQmyY05">rational numbers</a>.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> Explicit order isomorphisms between the quadratic algebraic numbers, the rational numbers, and the <a href="/facts/Dyadic_rational/LPwRYKaD">dyadic rational</a> numbers are provided by <a href="/facts/Minkowski%2527s_question-mark_function/gum3I0pX">Minkowski's question-mark function</a>.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a></li></ul>
<h2 id="order-types">Order types</h2>
If 
 
 
 
 f
 
 
 {\displaystyle f}
 
 is an order isomorphism, then so is its <a href="/facts/Inverse_function/Tg5nnXlu">inverse function</a>.
Also, if 
 
 
 
 f
 
 
 {\displaystyle f}
 
 is an order isomorphism from 
 
 
 
 (
 S
 ,
 
 ≤
 
 S
 
 
 )
 
 
 {\displaystyle (S,\leq _{S})}
 
 to 
 
 
 
 (
 T
 ,
 
 ≤
 
 T
 
 
 )
 
 
 {\displaystyle (T,\leq _{T})}
 
 and 
 
 
 
 g
 
 
 {\displaystyle g}
 
 is an order isomorphism from 
 
 
 
 (
 T
 ,
 
 ≤
 
 T
 
 
 )
 
 
 {\displaystyle (T,\leq _{T})}
 
 to 
 
 
 
 (
 U
 ,
 
 ≤
 
 U
 
 
 )
 
 
 {\displaystyle (U,\leq _{U})}
 
, then the <a href="/facts/Function_composition/r5Pvnmth">function composition</a> of 
 
 
 
 f
 
 
 {\displaystyle f}
 
 and 
 
 
 
 g
 
 
 {\displaystyle g}
 
 is itself an order isomorphism, from 
 
 
 
 (
 S
 ,
 
 ≤
 
 S
 
 
 )
 
 
 {\displaystyle (S,\leq _{S})}
 
 to 
 
 
 
 (
 U
 ,
 
 ≤
 
 U
 
 
 )
 
 
 {\displaystyle (U,\leq _{U})}
 
.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
Two partially ordered sets are said to be order isomorphic when there exists an order isomorphism from one to the other.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> Identity functions, function inverses, and compositions of functions correspond, respectively, to the three defining characteristics of an <a href="/facts/Equivalence_relation/1MQ5rtkW">equivalence relation</a>: <a href="/facts/Reflexive_relation/NzTytEg9">reflexivity</a>, <a href="/facts/Symmetric_relation/ekCWDIAH">symmetry</a>, and <a href="/facts/Transitive_relation/9r90y50r">transitivity</a>. Therefore, order isomorphism is an equivalence relation. The class of partially ordered sets can be partitioned by it into <a href="/facts/Equivalence_class/1d2sh0TB">equivalence classes</a>, families of partially ordered sets that are all isomorphic to each other. These equivalence classes are called <a href="/facts/Order_type/koXjnax6">order types</a>.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Permutation_pattern/ytUU2b91">Permutation pattern</a>, a permutation that is order-isomorphic to a subsequence of another permutation</li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Bloch, Ethan D. (2011), <a href="https://books.google.com/books?id=QJ_537n8zKYC&pg=PA276">Proofs and Fundamentals: A First Course in Abstract Mathematics</a>, <a href="/facts/Undergraduate_Texts_in_Mathematics/MTjjHqWD">Undergraduate Texts in Mathematics</a> (2nd ed.), Springer, pp. 276–277, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781441971265.</li>
<li>Ciesielski, Krzysztof (1997), <a href="https://books.google.com/books?id=tTEaMFvzhDAC&pg=PA38">Set Theory for the Working Mathematician</a>, London Mathematical Society Student Texts, vol. 39, Cambridge University Press, pp. 38–39, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9780521594653.</li>
<li>Schröder, Bernd Siegfried Walter (2003), <a href="https://books.google.com/books?id=2esoXnolEWgC&pg=PA11">Ordered Sets: An Introduction</a>, Springer, p. 11, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9780817641283.</li>
<li>Fuchs, Laszlo (1963), <a href="https://books.google.com/books?id=V_k79sVPcqYC">Partially Ordered Algebraic Systems</a>, Dover Publications; Reprint edition (March 5, 2014), pp. 2–3, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0486483878 {{citation}}: ISBN / Date incompatibility (help).</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Bloch (2011); Ciesielski (1997). - 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 <a href="https://books.google.com/books?id=QJ_537n8zKYC&pg=PA276" target="_blank">https://books.google.com/books?id=QJ_537n8zKYC&pg=PA276</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">This is the definition used by Ciesielski (1997). For Bloch (2011) and Schröder (2003) it is a consequence of a different definition. - Ciesielski, Krzysztof (1997), Set Theory for the Working Mathematician, London Mathematical Society Student Texts, vol. 39, Cambridge University Press, pp. 38–39, ISBN 9780521594653 <a href="https://books.google.com/books?id=tTEaMFvzhDAC&pg=PA38" target="_blank">https://books.google.com/books?id=tTEaMFvzhDAC&pg=PA38</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">This is the definition used by Bloch (2011) and Schröder (2003). - 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 <a href="https://books.google.com/books?id=QJ_537n8zKYC&pg=PA276" target="_blank">https://books.google.com/books?id=QJ_537n8zKYC&pg=PA276</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Schröder (2003), p. 13. - Schröder, Bernd Siegfried Walter (2003), Ordered Sets: An Introduction, Springer, p. 11, ISBN 9780817641283 <a href="https://books.google.com/books?id=2esoXnolEWgC&pg=PA11" target="_blank">https://books.google.com/books?id=2esoXnolEWgC&pg=PA11</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">This definition is equivalent to the definition set forth in Fuchs (1963). - Fuchs, Laszlo (1963), Partially Ordered Algebraic Systems, Dover Publications; Reprint edition (March 5, 2014), pp. 2–3, ISBN 0486483878 <a href="https://books.google.com/books?id=V_k79sVPcqYC" target="_blank">https://books.google.com/books?id=V_k79sVPcqYC</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">See example 4 of Ciesielski (1997), p. 39., for a similar example with integers in place of real numbers. - Ciesielski, Krzysztof (1997), Set Theory for the Working Mathematician, London Mathematical Society Student Texts, vol. 39, Cambridge University Press, pp. 38–39, ISBN 9780521594653 <a href="https://books.google.com/books?id=tTEaMFvzhDAC&pg=PA38" target="_blank">https://books.google.com/books?id=tTEaMFvzhDAC&pg=PA38</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Ciesielski (1997), example 1, p. 39. - Ciesielski, Krzysztof (1997), Set Theory for the Working Mathematician, London Mathematical Society Student Texts, vol. 39, Cambridge University Press, pp. 38–39, ISBN 9780521594653 <a href="https://books.google.com/books?id=tTEaMFvzhDAC&pg=PA38" target="_blank">https://books.google.com/books?id=tTEaMFvzhDAC&pg=PA38</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="81-85931-13-5" target="_blank">81-85931-13-5</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="/wiki/Journal_of_Mathematical_Analysis_and_Applications" target="_blank">/wiki/Journal_of_Mathematical_Analysis_and_Applications</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Ciesielski (1997); Schröder (2003). - Ciesielski, Krzysztof (1997), Set Theory for the Working Mathematician, London Mathematical Society Student Texts, vol. 39, Cambridge University Press, pp. 38–39, ISBN 9780521594653 <a href="https://books.google.com/books?id=tTEaMFvzhDAC&pg=PA38" target="_blank">https://books.google.com/books?id=tTEaMFvzhDAC&pg=PA38</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Ciesielski (1997). - Ciesielski, Krzysztof (1997), Set Theory for the Working Mathematician, London Mathematical Society Student Texts, vol. 39, Cambridge University Press, pp. 38–39, ISBN 9780521594653 <a href="https://books.google.com/books?id=tTEaMFvzhDAC&pg=PA38" target="_blank">https://books.google.com/books?id=tTEaMFvzhDAC&pg=PA38</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
</ol>

Order isomorphism open-in-new

Order isomorphism