- #1
dmuthuk
- 41
- 1
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 and I was wondering if anyone might have a simpler proof. Before stating the claim and my proof, I will define a few things:
1. A well ordered set is a partially ordered set for which every non-empty subset has a least element.
2. Two posets are similar if there exists a bijective map between them that preserves order in both directions. Such a map is called a similarity.
3. Let [tex]X[/tex] be a poset with order [tex]\leq_X[/tex] and let [tex]a\in X[/tex]. Then, the initial segment determined 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 a proper lower 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.
1. A well ordered set is a partially ordered set for which every non-empty subset has a least element.
2. Two posets are similar if there exists a bijective map between them that preserves order in both directions. Such a map is called a similarity.
3. Let [tex]X[/tex] be a poset with order [tex]\leq_X[/tex] and let [tex]a\in X[/tex]. Then, the initial segment determined 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 a proper lower 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.
Last edited: