Matching well orders

[head's up: very mathy entry]

Lately I have been thinking a little bit about well orders, and I stumbled across this cute fact:

-------------------------
Mostly Theorem: (modulo rigorization of proof)
Given any infinite set X and two well orders on X, there is a subset Y of X with the same cardinality of X on which both well orders agree.

-------------------------
(I say "mostly theorem" because I'm not certain that the proof is 100% rigorous, although I believe it is essentially correct modulo some polishing up.)

This is kind of interesting because Y is no insignificant piece of X, and this is certainly not true for non-well-founded orders, or for finite X. For any finite X, we can just sort them in opposite directions, so that no pair of elements allows an agreement between the orders. Also, if the orders need not be well-founded, then we could still define them to be opposite orders, and this still works as a counterexample.

-------------------------
Proof idea via a special case:
First let's check out the proof for countable X. This is easier to grok, and the more general proof below can be understood as an extension to this.

First we isolate a countably infinite sequence
W = (w1, w2, w3, ...)
in X which is in order by <1. Note that this may not be all of X, since there could be some x0 with wn <1 x0 for all the wn in the sequence. No problem -- we will just find our desired subset Y from within W.

Next we choose a subsequence
U = (u1, u2, u3, ...)
so that every set (<2 un) intersect W is finite. It is perfectly possible that such a set (I'll call it a "2-prefix") is infinite. Let V = (v1, v2, v3, ...) be the complementary sequence within W ; so that U and V partition W. If V is empty, then U = W, and we know U is infinite. If V is nonempty, let vi be the <2-min element of V. Then every element w which has w <2 vi is in U and there are infintely many of them. Hence we know that U is an infinite sequence.
[By the way, u1, u2, ... is still kept in order by <1.]

Now we will go through and choose yet another subsequence
Y = (y1, y2, ...)
Start with Y = U. Then throw out every yi in Y which has y1 <1 yi <2 y1. We are only throwing out a finite number of elements by the way we formed U. Now we look at y2 (which may be different from u2), and throw out every yi in Y which has y2 <1 yi <2 y2. Etc.

In the end, we will have a countably infinite set Y on which both <1 and <2 agree, as desired.

QED for this special case of the mostly theorem :)

-------------------------
The more general "proof sketch" here is not 100% rigorous mostly because I am new to this style of proof. After writing this down I'll go teach myself how to do it properly (or feel free to tell me in the comments / by email!)

-------------------------
Proof sketch:
Remember our goal: we start with an infinite set X well ordered by <1 and <2, and we will find a subset Y with card(Y) = card(X) so that <1, <2 agree on Y.

Let
A = {x: card(<1 x) < card(X)}.
If X-A is empty then clearly card(A) = card(X). Otherwise, let a0 be the <1-min of X-A, so that A = (<1 a0), and we see that
card(A) = card(<1 a0) = card(X).

Next let
B = {x in A: card((<2 x) isect A) < card(A)}.
Similar to above -- if A-B is empty, then
card(B) = card(A) = card(X).
Otherwise, let b0 be the <2-min of A-B so that
B = (<2 b0) isect A, and
card(B) = card((<2 b0) isect A) = card(A) = card(X).

Thus we have subset B with card(B) = card(X) and every 1-prefix and every 2-prefix has smaller cardinality.

Let C be another set, well ordered by <C, which is order isomorphic to B under <1. We will build Y by transfinite induction on C.

We will work with a series of functions f_{<= z} : C -> B, for each z in C. Each f will have these properties:
* the set f_{<= z}(<=C z) agrees between <1 and <2,
* the entire map f_{<=z} agrees between <C on C and <1 on B.

Suppose the map f_{<= y} has been defined for all y <C z. We must define f_{<= z} in terms of those earlier mappings.

As an intermediate step, we'll define f_{< z}. Let
B_{< z} = intersect_{y <C z} of   f_{<= y} (C).
(We will verify in a moment that card(B_{<z}) = card(B).)
Now choose f_{< z} : C -> B_{<z} so that f_{< z} is an order isomorphism between <C and <1. Now let
w = f_{<z}(z), and
B_{<= z} = B_{< z} - {b : w <1 b <2 w}.
We are removing all the elements from B_{<z} which would destroy order agreement between <1 and <2 with element w. Now let f_{<=z} be the order isomorphism between C and B_{<=z}.
[By the way, when z is the first element of C, we can just define B_{<z} as all of B; and w as the <1-min element of B.]

Let's check that B_{<z} has the right cardinality. Start with
card(<C z) < card(B), and
card(<2 f_{<=y}(y)) < card(B).
Now let
Dz = union_{y <C z} of (<2 f_{<=y}(y)), and
card(Dz) < card(B).
Thus we can see that
card(B_{<z}) >= card(B - Dz) = card(B),
as needed to keep the above definition valid.

Let Y = {y in B: y = f_{<=z}(z) for some z in C}.

It is not hard to check that <1 and <2 agree on Y, by our definition of the functions f_{<=z} above, and the properties they maintain. We also have that
card(Y) = card(C) = card(B) = card(X),
which completes the proof!

mostly QED! [modulo some possible rigorizing, as mentioned above]