Hi, I am trying to prove a claim about order isomorphisms (similarity) between well ordered sets. I have an argument for it, but it seems needlessly complicated:grumpy: and I was wondering if anyone might have a simpler proof. Before stating the claim and my proof, I will define a few things:(adsbygoogle = window.adsbygoogle || []).push({});

1. Awell orderedset is a partially ordered set for which every non-empty subset has a least element.

2. Two posets aresimilarif there exists a bijective map between them that preserves order in both directions. Such a map is called asimilarity.

3. Let [tex]X[/tex] be a poset with order [tex]\leq_X[/tex] and let [tex]a\in X[/tex]. Then, theinitial segmentdetermined by [tex]a[/tex] is the set [tex]s(a)=\{x\in X: x\leq_X a, x\neq a\}[/tex]. (i.e. all elements strictly smaller than [tex]a[/tex])

4. If [tex]X[/tex] is a poset, and [tex]E\subset X[/tex], then aproperlower bound of [tex]E[/tex] in [tex]X[/tex] is an element which is strictly smaller than every member of [tex]E[/tex].

CLAIM:

Let [tex]X[/tex] and [tex]Y[/tex] be well ordered sets such that neither is similar to an initial segment of the other. Consider a map [tex]U:X\to Y[/tex] such that for each [tex]a\in X[/tex], [tex]U[/tex] maps the set [tex]s(a)[/tex] in [tex]X[/tex] bijectively to the set [tex]s(U(a))[/tex] in [tex]Y[/tex]. Then [tex]U[/tex] is a similarity.

My PROOF:

First, we must show that [tex]U[/tex] is indeed a bijection. Suppose [tex]a<b[/tex] for some [tex]a,b\in X[/tex]. Then, [tex]a\in s(b)[/tex] and since [tex]U(s(b))=s(U(b))[/tex], [tex]U(a)\in s(U(b))[/tex]. So, [tex]U(a)<U(b)[/tex]. Since, [tex]a[/tex] and [tex]b[/tex] can be interchanged, we conclude that [tex]U[/tex] is one-to-one. Notice that this also shows that [tex]U[/tex] preserves order in the direction [tex]X\to Y[/tex]. Now, assume that [tex]x,y\in U(X)[/tex] such that [tex]x<y[/tex]. Let [tex]x=U(a)[/tex] and [tex]y=U(b)[/tex] for some [tex]a,b\in X[/tex]. Since [tex]U[/tex] is one-to-one, [tex]U^{-1}(s(y))=s(b)[/tex]. So [tex]a\in s(b)[/tex] and we have [tex]a<b[/tex].

Assertion: [tex]U(X)=Y[/tex]. Well, if [tex]Y-U(X)[/tex] is non-empty, it has a smallest element [tex]t[/tex]. Then, for all [tex]y<t[/tex], [tex]y\in U(X)[/tex]. Suppose [tex]U(a)\in U(X)[/tex] for some [tex]a\in X[/tex]. Then, [tex]s(U(a))\subset U(X)[/tex]. If [tex]U(X)[/tex] has a proper lower bound [tex]k[/tex], then [tex]t\leq k[/tex], which means [tex]t\in s(U(a))[/tex] in particular, which contradicts the choice of [tex]t[/tex]. So, [tex]U(X)[/tex] does not have any proper lower bounds. Therefore, [tex]U(a)<t[/tex] and we conclude that [tex]U(X)=s(t)[/tex]. This, however, implies that there is a similarity between [tex]X[/tex] and an initial segment of [tex]Y[/tex] which contradicts our initial assumption about [tex]X[/tex] and [tex]Y[/tex]. So, the assertion is true, and [tex]U[/tex] is similarity.

Any help would be appreciated, thanks.

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Order isomorphism

Loading...

Similar Threads - Order isomorphism | Date |
---|---|

I Order of "Extracted Factors" in SPSS Factor Analysis | Jul 24, 2017 |

A Transcription from SQL to FOL (First Order Logic) | Jun 3, 2017 |

A First order logic : Predicates | Jun 1, 2017 |

Order isomorphism | Dec 26, 2011 |

Order isomorphism f:R->R | Jan 4, 2009 |

**Physics Forums - The Fusion of Science and Community**