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
4 Comments:
Thanks! Do you know if any well-founded relation can be extended into a partial order?
Hi Tyler,
It's surprising how hard it is to find proofs of this online.
I'd like to try an alternative proof based on https://en.wikipedia.org/wiki/Szpilrajn_extension_theorem
However, the wiki article has a serious flaw that I can discuss if interested.
I'm attempting my proof here now for the first time.
So please bear with me.
Let W be the set with the well-founded partial order.
Call this partial ordering R.
By the well-ordering theorem, index the elements of W with a well-ordered set, alpha.
By transfinite induction, for each lambda in alpha define an extension of R, R_lambda,
assuming that R_gamma has been defined for each gamma < lambda.
The construction will make it clear that whenever gamma < lambda, R_lambda extends R_gamma.
By the transfinite construction, it will be clear that each w in W is a member of R_beta for some beta in alpha.
Now the ordering on W is defined as follows.
Let w_i, w_j belong to W where i and j belong to alpha.
Define w_i < w_j iff w_i < w_j in R_max(i, j).
It will need to be checked that this ordering is consistent -- in other words,
w_i < w_j must also be true with respect to all extensions of R, R_beta, where beta > max(i, j).
Finally, we define the extensions.
R is well_founded.
Let beta belong to alpha. We need to define R_beta.
Assume by transfinite induction that for all gamma < beta, R_gamma is a well-founded
relation extending R.
Let R' be the union of the relations in R together with the relations in R_gamma for
all gamma < beta. Call the underlying set S. In other words S = the union of the sets
{x, y} such that x < y under R'.
Add all of the following relations: For all s in S, w_beta > s if w_beta is incomparable to s
under the partial ordering R'.
R' has now been extended (and therefore R has been extended too).
Redefine R' so that R' is this new extension.
For all s_1, s_2 in S, if, with > defined via R', s_1 > w_beta and w_beta > s_2 then
add the relation s_1 > s_2.
Define R_beta to be this extension of R.
It must be checked (the induction assumption will be needed here, assuming that
s_1, s_2 have been introduced at an earlier stage than the new w_beta)
that R_beta doesn't reverse any x > y relations. R_beta sometimes makes x > y where
previously x was incomparable to y but R_beta introduces no reversals.
That fact means that the ordering is consistent.
It should be clear, by transfinite induction, that the set {w_gamma where gamma <= beta (using the ordering in alpha)}
is a totally ordered set.
After all, any incomparability introduced at stage beta must involve w_beta and such incomparabilities have been explicitly eliminated.
By transfinite induction, R_beta is well-founded since clearly w_beta can't introduce
infinite descending chains if they didn't exist previously.
Since W is indexed by alpha, every w in W gets introduced at some stage R_gamma.
By construction R_lambda extends R_gamma whenever lambda > gamma (using the ordering of
alpha).
The R_gamma sets form a chain of well-founded partially ordered sets with union W.
If x and y both belong to W, then x belongs to some R_gamma, y belongs to some R_lambda
and both x and y belong to R_max(gamma, lambda). Hence the ordering in W is well-defined.
Since every w belongs to W, this ordering is total.
It's not quite clear (to me) that this is a well-ordering so I continue.
Now introduce a new element w_alpha that did not previously belong to W.
Let W' = W U {w_alpha}
Extend the ordering of the indexing set alpha so that alpha > all the members of alpha.
(Basically, I'm reiterating the basic theory of ordinals).
Now R_alpha defined on W' makes sense and R_alpha extends the previous ordering on W by simply defining w_alpha to be > every element of W.
By transfinite induction, R_alpha is a well_ordering on W'. W' extends W so W must be
well-ordered too, which completes the proof.
Paul Epstein
There are always typos in a first draft.
R' (not R) always refers to the latest extension.
I'm moderately confident in the proof but I'm suspicious of the
fact that I never used Zorn's lemma.
Maybe Zorn's lemma makes the proof easier or more rigorous.
Such a proof is too long to write completely without gaps but I'm hoping that
the gaps are routine. It's crucial to realise that in a chain of relations
like s_1 > s_2 > w_beta, we can inductively assume that s_1 and s_2 were already
present in R' at a stage before beta. Since s_2 is present at this early stage,
we've already been able to deduce s_1 > w_beta at a pre-beta stage, so we don't need
to add it again. But, in any case, I'm just rehashing the theory of the transitive
closure which must be googlable.
There's a major conceptual flaw in my proof (unsurprising for a first draft). But it's very easy to repair. And now that I've repaired it mentally, I'm much more confident in it. At the beta stage, the ordering of the set {w_lambda : lambda <= beta} need not be compatible with R or its extensions. This is a problem. We repair it by simply forcing the compatibility. Let the beta stage be the stage where we introduce w_beta. Supppose there is an ordinal gamma < beta such that, with respect to R', the new extension of R, w_beta < w_gamma, then let lambda be the least such ordinal. Now reindex such that w_beta = w_lambda, and for all ordinals gamma such that beta > gamma >= lambda, w_gamma = w_(gamma + 1)
Post a Comment
<< Home