Proof of Order Isomorphism Claim for Well Ordered Sets

[dmuthuk]

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 X be a poset with order \leq_X and let a\in X. Then, the initial segment determined by a is the set s(a)=\{x\in X: x\leq_X a, x\neq a\}. (i.e. all elements strictly smaller than a)
4. If X is a poset, and E\subset X, then a proper lower bound of E in X is an element which is strictly smaller than every member of E.


CLAIM:

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


My PROOF:

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

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


Any help would be appreciated, thanks.

 

[matt grime]

I'm not sure that I see that U is defined at all. Am I missing some obvious statement (probably via transitive induction) that allows you to state what U(a) is? I think there is, but you've not said it.You also assume surjectivity without justification at some point (penultimate sentence of the first paragraph of your proof).

The proof in my mind goes like this:

define an identification between X and Y as follows.

1. Send the smallest element of X to the smallest element of Y.

2. By induction suppose we have an bijection between s(x) and s(y) for some x,y, then identify the smallest element in X\s(x) with the smallest element in Y\s(y).

Since neither X<Y nor Y<X, this must be an order isomorphism.

Actually, all I'm showing is that given any two well ordered sets, either X<=Y or Y<=X, or if you will there is only one isomorphism class of well ordered set per order type.

 

[dmuthuk]

I'm not sure that I see that U is defined at all. Am I missing some obvious statement (probably via transitive induction) that allows you to state what U(a) is? I think there is, but you've not said it.

The claim defines U:X\to Y as a map with the stated properties (i.e. it bijectively maps initial segments of elements to initial segments of their images). Since a\in X, isn't U(a) defined?

You also assume surjectivity without justification at some point (penultimate sentence of the first paragraph of your proof).

I think you might be referring to the sentence, "Since U is one-to-one, U^{-1}(s(y))=s(b)". Well, by definition, U maps the set s(b) bijectively to s(U(b))=s(y). So, we certainly have s(b)\subset U^{-1}(s(y)). Injectivity of U guarantees equality as well.

 

[matt grime]

Nope, you failed to understand me, or I failed to be make myself understood.

You assert that the map U is defined to map s(a) bijectively to s(U(a)). That supposes that U(a) makes sense, which it doesn't because you failed to define U(a).

Your assumption of srujectivity is precisely the point where you take x and y in Y, and then choose a,b in X so that U(a)=x, etc. That assumes surjectivity without any justification. Not least because you have completely failed to define what U is!

 

[dmuthuk]

You assert that the map U is defined to map s(a) bijectively to s(U(a)). That supposes that U(a) makes sense, which it doesn't because you failed to define U(a).

I think I'm certainly missing something here I'm still not sure about what you mean by "define". The fact is that U is any map between X and Y such that for each a\in X the correspondence between s(a)\subset X and s(U(a))\subset Y is bijective. I mean, if a\in X, then U(a)\in Y, whatever it is. That such a map exists of course can be shown using the transfinite recursion theorem.

Your assumption of srujectivity is precisely the point where you take x and y in Y, and then choose a,b in X so that U(a)=x, etc. That assumes surjectivity without any justification. Not least because you have completely failed to define what U is!

Actually, I have chosen the points x,y\in U(X).

 

[matt grime]

How was I supposed to know that you knew such a U exists? You didn't invoke anything to do with transfinite induction.

The point is that the transifinte induction argument makes the question completely trivial - given any two well ordered sets one is a well ordered subset of the other.

There is only one map to define (well ordered sets are isomorphic upto unique isomorphism) and I defined it in my first reply.

I now notice my mistake about the surjectivity.

 

[dmuthuk]

How was I supposed to know that you knew such a U exists? You didn't invoke anything to do with transfinite induction.

Sorry about the confusion, but why is it necessary to prove the existence of the function in this problem? I know it can be constructed using transfinite recursion, but why is that imporant here? Can we not assume its existence to begin with and then prove that its a similarity. Does it matter how it was constructed? Here's my thought on this. If such a function really did not exist, then we will be beginning with a false premise and the conclusion will automatically be true. So, I wonder if my confusion was related to logic.

 

[fopc]

I have an argument for it, but it seems needlessly complicated and I was wondering if anyone might have a simpler proof.

It looks like the comparability theorem for well ordered sets.
If you're interested in simpler proofs, you might look at Halmos (Naive Set Theory), p.73.
There he presents two fairly detailed proof sketches, one that uses transfinite recurrsion theorem
and one that doesn't.

 

[matt grime]

Sorry about the confusion, but why is it necessary to prove the existence of the function in this problem? I know it can be constructed using transfinite recursion, but why is that imporant here? Can we not assume its existence to begin with and then prove that its a similarity. Does it matter how it was constructed? Here's my thought on this. If such a function really did not exist, then we will be beginning with a false premise and the conclusion will automatically be true. So, I wonder if my confusion was related to logic.

If you want to prove something to someone else it is usually a good idea never to assume anything without explicitly stating you are assuming it. Otherwise that person has no idea if you've written something that happens to be correct purely by fluke.

Moreover, the method by which it is constructed instantly shows that the result you're claiming to be true is in fact true without any further work.

Thus, it is not only good practice to help others, but helps you answer the question.

Suppose we construct U as we know we can. There are subsets M and N in X and Y resp. Such that U maps X - M bijectively to Y - N. Let us pick the minimal M and N. Clearly, at least one must be empty, otherwise we can extend U by picking the smallest element in each and identifying them. So, wlog M is empty. That means X maps bijectively onto Y-N. If Y is empty, then this is a bijection between X and Y and if N is not empty then this identifies X with an initial segment of Y, Y-N=s(min(N)).

 

[dmuthuk]

It looks like the comparability theorem for well ordered sets.
If you're interested in simpler proofs, you might look at Halmos (Naive Set Theory), p.73.
There he presents two fairly detailed proof sketches, one that uses transfinite recurrsion theorem
and one that doesn't.

Hey! Actually, that's precisely the theorem (in Halmos) that I have been trying to work out the details for This statement in particular was in fact the last portion of his first proof in which he sort of left it to the reader. Thanks.