Every well-founded partial order can be extended to a well order
Theorem:
Every well-founded partial order can be extended to a well order.
[This is another mathy entry.]
I was recently working on a problem in which I wanted to extend a well-founded partial order to a well order, and I didn't know for sure that this was always possible. The proof below confirms that it is. I'd be really interested to hear about any other proofs (maybe something more elegant?) of this fact.
Proof:
Suppose we have a well-founded partial order <=p on the set X. By the well-ordering theorem, there exists some well order <=w on X as well (at this point <=w has no relation to <=p). We will use transfinite induction on X as ordered by <=w to create a new order <=n (n here is for "new"), so that <=n is a well order which extends <=p. Our induction is on element x: given x, we will assume that <=n is a well order extending <=p on every subset of the form (<=w y) for all y <w x, and we will:
(0) define <=n for all pairs in (<=w x), and
(1) see that for any y <w x,
(<w y) \isect (>n y) = (<w y) \isect (>p y),
(2) check that <=n is a well order on (<w x),
(3) verify <=n is still a well order on (<=w x).
Why these steps? (0) is where we define <=n. (1) is a lemma towards (2). Note that (2) does not follow from the inductive assumption since it is possible that (<w x) is not equal to (<=w y) for any y <w x -- e.g., if x is the first infinite ordinal. (3) is essentially the main point of the induction.
Let's go --
Definition for (0):
Given x, let F(X) = {x' : x' <w x and x <p x'}. If F(x) is empty, then we say that y <n x for all y <w x. Otherwise, let x' = the <n-min of F(X). [We will confirm in a moment that this exists.]
For any y <w x, define <n by:
y <n x if y <n x', and
y >n x if y >=n x'.
This essentially makes x' = x + 1 in <n, intuitively.
Proof of (1):
Suppose it's not true. Then let y be the <w-first element which defies (1) -- and thus there exists z so that z <w y, z >n y, and y,z are not <p-comparable. As above, let F(y) = {y' : y' <w y and y <p y'}. If F(y) is empty, then by definition of <n, every z <w y must also have z <n y, which contradicts our assumptions about y. Hence F(y) is nonempty, and we may let y' be the <n-min of F(y) [which exists since <n is assumed to
be a well order on (<=w y)]. Notice that (1) holds for y', since y' <w y, and we chose y as the <w-first which defies (1). Also, y' != z, since y',y are comparable under <p, but y,z are not. Then by the definition of <n (and z != y), we have
z >n y implies z >n y',
but then (using (1) on y),
z >n y' implies z >p y' implies z >p y,
which contradicts our assumptions about y,z. Hence no such y exists, and we have proven (1).
It will be useful to extract this from (1):
(1') For any a,b <w x,
a <w b and a >n b implies a >p b.
Proof of (2):
It is easy to see that <n is a total order on (<w x); if any of the necessary rules were violated, there would exist a finite set of elements to act as a counterexample, and hence there would exist some y <w x for which <n was not a total order on (<=w y).
All that remains is to check that <n is well-founded. Suppose not. Then there is an infinite decreasing sequence x1 >n x2 >n x3 >n ... . Without loss of generality, x1 <w x2 <w x3 <w ... . Why WLOG? Because we can take the <w-min element of the first sequence, and rename that x1, throwing away a finite number of earlier elements in the sequence. Then, take the <w-min of everything after x1, and rename that x2, again throwing out some finite portion of the sequence. In the end we get a <n-decreasing, <w-increasing infinite sequence. [This inspired me to write the matching well orders entry a few weeks ago.]
Now simply apply (1') to see that
x1 >p x2 >p x3 >p ... ,
which is impossible since <p is well-founded. This finishes the proof of (2).
Check (3):
We now know that <n is well-defined. It is impossible to "break" well-foundedness by adding a single element; in other words, since <n is well-founded on (<w x), it must also be well-founded on (<=w x).
It is relatively easy to check the remaining properties of <n being a total order on (<=w x); we won't fill in all those details.
We'll check one case of transitivity (other cases left to the reader): suppose v <n w, and w <n x. If F(x) is empty, then v <n x by definition of <n. Otherwise, let x' be the <n-min of F(x). We know that w <n x', so that v <n x' by induction, and then v <n x again using our definition of <n.
Now we'll check that <n does indeed extend <p on (<=w x). If x <p y (and y <w x), then y is in F(x), so x' <=n y, and x <n y. On the other hand, suppose
x >p y. If F(x) is empty, then x >n y by definition of <n. If F(x) is nonempty, x' exists, and we claim that y <n x. First notice y is not in F(x) since y <p x. Next, if y >n x', then y >p x' by (1), and we would get y >p x by transitivity of <p. This contradicts our assumption, so it must be y <n x as claimed.
Technically, steps (1)-(3) only very if that <n is a well order on every set of the form (<=w x). We can extend this result to all of X by using the argument for step (2). To be rigorous, one could artificially add element omega as a new <p- and <w-max of X, so that X' = (<=w omega), and <n is a well order on all of X' and hence also all of X.
QED
Every well-founded partial order can be extended to a well order.
[This is another mathy entry.]
I was recently working on a problem in which I wanted to extend a well-founded partial order to a well order, and I didn't know for sure that this was always possible. The proof below confirms that it is. I'd be really interested to hear about any other proofs (maybe something more elegant?) of this fact.
Proof:
Suppose we have a well-founded partial order <=p on the set X. By the well-ordering theorem, there exists some well order <=w on X as well (at this point <=w has no relation to <=p). We will use transfinite induction on X as ordered by <=w to create a new order <=n (n here is for "new"), so that <=n is a well order which extends <=p. Our induction is on element x: given x, we will assume that <=n is a well order extending <=p on every subset of the form (<=w y) for all y <w x, and we will:
(0) define <=n for all pairs in (<=w x), and
(1) see that for any y <w x,
(<w y) \isect (>n y) = (<w y) \isect (>p y),
(2) check that <=n is a well order on (<w x),
(3) verify <=n is still a well order on (<=w x).
Why these steps? (0) is where we define <=n. (1) is a lemma towards (2). Note that (2) does not follow from the inductive assumption since it is possible that (<w x) is not equal to (<=w y) for any y <w x -- e.g., if x is the first infinite ordinal. (3) is essentially the main point of the induction.
Let's go --
Definition for (0):
Given x, let F(X) = {x' : x' <w x and x <p x'}. If F(x) is empty, then we say that y <n x for all y <w x. Otherwise, let x' = the <n-min of F(X). [We will confirm in a moment that this exists.]
For any y <w x, define <n by:
y <n x if y <n x', and
y >n x if y >=n x'.
This essentially makes x' = x + 1 in <n, intuitively.
Proof of (1):
Suppose it's not true. Then let y be the <w-first element which defies (1) -- and thus there exists z so that z <w y, z >n y, and y,z are not <p-comparable. As above, let F(y) = {y' : y' <w y and y <p y'}. If F(y) is empty, then by definition of <n, every z <w y must also have z <n y, which contradicts our assumptions about y. Hence F(y) is nonempty, and we may let y' be the <n-min of F(y) [which exists since <n is assumed to
be a well order on (<=w y)]. Notice that (1) holds for y', since y' <w y, and we chose y as the <w-first which defies (1). Also, y' != z, since y',y are comparable under <p, but y,z are not. Then by the definition of <n (and z != y), we have
z >n y implies z >n y',
but then (using (1) on y),
z >n y' implies z >p y' implies z >p y,
which contradicts our assumptions about y,z. Hence no such y exists, and we have proven (1).
It will be useful to extract this from (1):
(1') For any a,b <w x,
a <w b and a >n b implies a >p b.
Proof of (2):
It is easy to see that <n is a total order on (<w x); if any of the necessary rules were violated, there would exist a finite set of elements to act as a counterexample, and hence there would exist some y <w x for which <n was not a total order on (<=w y).
All that remains is to check that <n is well-founded. Suppose not. Then there is an infinite decreasing sequence x1 >n x2 >n x3 >n ... . Without loss of generality, x1 <w x2 <w x3 <w ... . Why WLOG? Because we can take the <w-min element of the first sequence, and rename that x1, throwing away a finite number of earlier elements in the sequence. Then, take the <w-min of everything after x1, and rename that x2, again throwing out some finite portion of the sequence. In the end we get a <n-decreasing, <w-increasing infinite sequence. [This inspired me to write the matching well orders entry a few weeks ago.]
Now simply apply (1') to see that
x1 >p x2 >p x3 >p ... ,
which is impossible since <p is well-founded. This finishes the proof of (2).
Check (3):
We now know that <n is well-defined. It is impossible to "break" well-foundedness by adding a single element; in other words, since <n is well-founded on (<w x), it must also be well-founded on (<=w x).
It is relatively easy to check the remaining properties of <n being a total order on (<=w x); we won't fill in all those details.
We'll check one case of transitivity (other cases left to the reader): suppose v <n w, and w <n x. If F(x) is empty, then v <n x by definition of <n. Otherwise, let x' be the <n-min of F(x). We know that w <n x', so that v <n x' by induction, and then v <n x again using our definition of <n.
Now we'll check that <n does indeed extend <p on (<=w x). If x <p y (and y <w x), then y is in F(x), so x' <=n y, and x <n y. On the other hand, suppose
x >p y. If F(x) is empty, then x >n y by definition of <n. If F(x) is nonempty, x' exists, and we claim that y <n x. First notice y is not in F(x) since y <p x. Next, if y >n x', then y >p x' by (1), and we would get y >p x by transitivity of <p. This contradicts our assumption, so it must be y <n x as claimed.
Technically, steps (1)-(3) only very if that <n is a well order on every set of the form (<=w x). We can extend this result to all of X by using the argument for step (2). To be rigorous, one could artificially add element omega as a new <p- and <w-max of X, so that X' = (<=w omega), and <n is a well order on all of X' and hence also all of X.
QED
posted by Tyler | 3:31 PM
|
0 comments
