Distinct well-orderings of the same set - MathOverflow

Distinct well-orderings of the same set

2010-09-29T18:24:52Z

An easy consequence of the Erdős-Dushnik-Miller theorem $\kappa\to(\kappa,\omega)^2$ is the following, that will denote $(*)$ (it appears as an exercise in Kunen's book, it was probably mentioned explicitly earlier by Dushnik-Miller or Erdős, but I haven't found a reference):

If $X$ is infinite and $<_1$ and $<_2$ are two well-orderings of $X$, then there is a subset $Y$ of $X$ with $|Y|=|X|$ where $<_1$ and $<_2$ coincide.

The proof uses choice, but it follows that it holds in ZF: We may as well assume $X$ is an ordinal $\kappa$, so we can code $<_1$ and $<_2$ with a set $A\subseteq \kappa^2$, and argue in $L[A]$, which is a model of choice.

This proof has always looked bizarre to me. I remember a few years ago discussing this with Clinton Conley, and I believe we found a combinatorial argument, but I don't recall how it went, so I am not sure.

What I am asking then is for a combinatorial proof of $(*)$ in ZF.

(``Combinatorial'' may signify several things, what I mostly mean is that no metamathematics appear in the proof.)

Perhaps there is some kind of inductive argument (I vaguely recall that's what we had), but I don't think it can be completely straightforward. For example, $X=\omega_1$ could have cofinality $\omega$, so the obvious approach may run out of room before $\omega_1$ steps.

Answer by Alessandro Sisto for Distinct well-orderings of the same set

2010-09-29T19:36:04Z

Here is a quick sketch (probably it can be made much cleaner). Using an inductive argument it should not be difficult to reduce to studying the case that $(X,<_1)$ is isomorphic to a cardinal, say $\kappa$. For convenience, let us identify $(\kappa,<)$ and $(X,<_1)$ . Let us now construct $Y$ using transfinite induction. Let $X'\subseteq X$ be the initial segment of $X$ (with respect to $<_2$ ) which, endowed with the order $<_2$ , is isomorphic to $\kappa$. For $\alpha<k$ define $$y_\alpha=\min\{\beta\in X': \forall \alpha'<\alpha\; \beta> y_{\alpha'}\textrm{\ and\ }\beta>_2 y_{\alpha'}\}.$$ The set above is not empty, and so $y_\alpha$ is well defined, because $|\{\gamma\in X':\exists \alpha'<\alpha\; \gamma\leq y_{\alpha'}\}|<k$ and also $|\{\gamma\in X':\exists \alpha'<\alpha\; \gamma\leq_2 y_{\alpha'}\}|<k$ (this depends on $\{y_{\alpha'}\}_{\alpha'<\alpha}$ not being cofinal in $(k,<)$ and $(X',<_2)$ ), so their complements in $X'$ intersect. The set $Y=\{y_\alpha\}_{\alpha<k}$ is what we were looking for.

Answer by Justin Palumbo for Distinct well-orderings of the same set

2010-09-29T21:28:56Z

A couple of years ago I solved the Kunen exercise together with Anush Tserunyan (like myself and Clinton at the time, a grad student at UCLA). We weren't aware of Dushnik-Miller so we gave the following direct proof of the exercise. Edit: As Andres pointed out, this argument does not answer the question: it only proves it for the cases where $|X|$ is regular or the limit of regular cardinals (which consistently, may only be the case where $|X|$ is countable).

First we reduce the problem to something a little easier to state. Let $\kappa=|X|$. Then $<_1$ has an initial segment of order-type $\kappa$ and so by restricting $X$ to this initial segment we may assume that $<_1$ is the usual well-order on $\kappa$. Furthermore, we may similarly restrict $<_2$ to an initial segment in order-type $\kappa$. Thus we see it is sufficient to prove:

(a) Whenever $\kappa$ is a cardinal, $f:\kappa\rightarrow\kappa$ is bijective there is a set $A\subseteq\kappa$ of size $\kappa$ on which $f$ is strictly increasing (in the usual order on the ordinals).

In fact, by identifying the range of $f$ with an ordinal, and again restricting down to an initial segment of ordertype $\kappa$ we see that (a) is equivalent to the following:

(b) Whenever $\kappa$ is a cardinal, and $\lambda$ is an ordinal, and $f:\kappa\rightarrow\lambda$ is injective there is a set $A\subseteq\kappa$ of size $\kappa$ on which $f$ is strictly increasing.

Proving (a) when $\kappa$ is regular is a straightforward transfinite recursion. Let's say $\kappa$ is singular, and in fact I'll just explain the case $\kappa=\aleph_\omega$ (the argument generalizes higher by writing $\kappa$ as a limit of regular cardinals above the cofinality of $\kappa$).

Let $f:\kappa\rightarrow\kappa$. The idea is to build $A_1,A_2,\ldots$ with $A_n$ of ordertype $\aleph_n$, $A_n$ < $A_{n+1}$, and the values $f$ takes on $A_{n+1}$ strictly larger than those it takes on $A_n$. We use (b) for this. Consider $f_1$ the restriction of $f$ to $\aleph_1$. By (b) there is $A_1\subseteq\aleph_1$ on which $f_1$ is increasing. Let $\gamma_1=\sup f[A_1]$. Since $\gamma_1$ has cofinality $\omega_1$, $\gamma_1<\aleph_\omega$. Let $X_1=\kappa\setminus(\aleph_1\cup\{\alpha<\kappa:f(\alpha)<\gamma)\})$. Then $X_1$ still has cardinality $\kappa$, and we can extract $A_2$ from it just as we did for $A_1$. Continue doing this, and at the end let $A$ be the union of the $A_n$.

Answer by David Speyer for Distinct well-orderings of the same set

2010-09-30T02:10:05Z

UPDATE: This is dead wrong. See comments below.

Can you give a combinatorial proof of the infinite Ramsey theorem? That is:

Let $X$ be an infinite well ordered set. Let $G$ be a graph with vertex set $X$. Then there is a subset $Y$ of $X$, with $|Y|=|X|$, such that either every two elements of $Y$ are joined by an edge of $G$, or no two elements of $Y$ are joined by an edge of $G$.

If you can get that, let $G$ be the graph where there is an edge $(u,v)$ if $<_1$ and $<_2$ give the same relation between $u$ and $v$. You want to prove that the first alternative in the alternate Ramsey theorem applies.

Assume, for contradiction, that there is an infinite $Y$ such that, for $u$ and $v$ in $Y$, the inequality $u <_1 v$ implies $u >_2 v$. Then $Y$ is well ordered by $<_1$. Let $z$ be the $<_1$ smallest element of $Y$ such that $\{ y \in Y, \ y <_1 z\}$ is infinite. You should be able to give a combinatorial proof that $<_1$ restricted to $\{ y \in Y, \ y <_1 z\}$ is $\omega$. Then $<_2$ restricted to $\{ y \in Y, \ y <_1 z\}$ is not well ordered, a contradiction.

Answer by Michael Blackmon for Distinct well-orderings of the same set

2011-01-24T14:37:14Z

I am hesitant to attempt this, so If this makes no sense, or is not in keeping with what you are looking for I'm sorry.

Firstly, let $R_1, R_2 \subset \kappa\times\kappa$, be the two well-orderings of $\kappa$ we are considering. Then, as $\kappa \times \kappa$ has a well-ordering $\lt_O$ which has order type with $\kappa$ via some isomorphism $P:\kappa \times \kappa \rightarrow \kappa$, with for each $(\alpha,\beta)\in \kappa \times \kappa$:

$\gamma = max(\alpha,\beta) \implies P((\alpha,\beta)) = P(\alpha,\beta) \in P''((\gamma+1)\times(\gamma+1)).$

(This is a modification of the global ordering from Set Theory and The Continuum Hyp. by R. M. Smullyan and M. Fitting, p. 119).

This ordering is defined as follows: $(\alpha,\beta)\lt_O(\gamma,\delta)$ iff one of the following holds

$max(\alpha,\beta) \lt max(\gamma,\delta)$, or
$max(\alpha,\beta) = max(\gamma,\delta)$, and $\alpha \lt \gamma$, or
$max(\alpha,\beta) = max(\gamma,\delta)$, and $\beta \lt \delta$

As such, we may form the following construction: Let $r^k_0=min_{\lt_O} (R_k)$ and for $\alpha \lt \kappa$ define $r^k_\alpha = min_{\lt_O} (R_k \backslash \{r^k_\gamma :\gamma \lt \alpha\} )$ for $k=1,2.$

Next following along with the answer from, Alessandro Sisto, we may define the sequence $u_\alpha$

$u_\alpha = min\{ \beta \in P''(\alpha+1)\times(\alpha+1): \forall \gamma \lt \alpha ( P^{-1}(u_{\gamma}) \lt_O r^1_{\beta} \text{ and } P^{-1}(u_\gamma) \lt_O r^2_\beta) \}.$

Then $u_\alpha$ will be defined for every $\alpha \lt \kappa$, and so preforming the same bit that Alessandro did, with $y_\alpha = min \{ \beta \in \kappa: \exists \gamma \lt \alpha( (\eta,\beta) = P^{-1}(y_\gamma)) \}$ should produce the result.

Answer by Andres Caicedo for Distinct well-orderings of the same set

2011-01-28T22:19:25Z

Clinton Conley has found a nice argument that solves the problem. I daresay that even in the presence of choice, it is nicer than the standard approach, and avoids having to separate the argument by cases depending on the cofinality of the cardinal in question. Clinton and I are curious whether the "König lemma"-like statement below has been explicitly mentioned previously. Any pointers are welcome.

Here is a sketch of his argument. I am posting it with his permission, but blame me for any mistakes:

We first establish a lemma about partial orders on a well-ordered set $X$. A partial order $\preceq$ on $X$ is well-founded if any nonempty subset of $X$ has a $\preceq$-minimal element. To any such well-founded partial order we can associate an ordinal-valued rank function on $X$ by $$ {\rm rank}_\preceq(x) = \sup\{{\rm rank}_\preceq(y) +1\mid y \prec x\}. $$

Lemma (König?). Suppose that $\preceq$ is a well-founded partial order on a well-ordered set $X$. Suppose further that $\kappa$ is an infinite aleph such that for each $\alpha \lt \kappa$ the set $X_\alpha = \{x \in X \mid {\rm rank}_\preceq(x) = \alpha\}$ is finite and nonempty. Then there is a $\preceq$-chain $A \subseteq X$ of order type $\kappa$.

Proof.

We first prune. For each $\alpha \lt \kappa$ define the set $Y_\alpha$ by $$ Y_\alpha = \{x \in X_\alpha\mid \forall \alpha\lt\beta\lt\kappa\exists y \in X_\beta (x \prec y)\}. $$ That is, $Y_\alpha$ is the set of $x \in X_\alpha$ with extensions to each $X_\beta$, for $\beta$ strictly between $\alpha$ and $\kappa$. Each $Y_\alpha$ is nonempty since each $X_\alpha$ is finite and ${\rm cof}(\kappa)$ is infinite.

Claim. Each $\preceq$-chain $A_\alpha \subseteq \bigcup_{\beta \lt \alpha} Y_\beta$ of order type $\alpha$ may be extended to a $\preceq$-chain $A_{\alpha+1} \subseteq \bigcup_{\beta \lt \alpha+1} Y_\beta$ of order type $\alpha+1$.

Proof of the claim.

This is immediate when $\alpha$ is a successor $\beta + 1$, since by the pruning we have $$Y_\beta \subseteq \{x\mid \exists y \in Y_{\beta+1}\ x \prec y\}.$$ When $\alpha$ is a limit, there is some element $x \in Y_\alpha$ above cofinally many elements of $A_\alpha$, since $Y_\alpha$ is finite and ${\rm cof}(\alpha)$ is infinite. Clearly $A_{\alpha+1} = A_\alpha \cup \{x\}$ is as desired. $\Box$

From the claim we may build a $\preceq$-chain of order type $\kappa$ simply by following the "leftmost" (with respect to the well-order of $X$) branch. Explicitly, for each $\alpha \lt \kappa$ let $A_\alpha$ be the unique leftmost chain of order type $\alpha$ in $\bigcup_{\beta \lt \alpha} Y_\alpha$, which exists at successors by the above claim and at limits by taking unions. Finally, set $A = \bigcup_{\alpha \lt \kappa} A_\alpha$. $\Box$

From the lemma, the result follows easily.

Proposition. Suppose that $R_0$ and $R_1$ are two well-orders of an infinite set $X$. Then there is some $A \subseteq X$ such that ${}|A| = |X|$ and $R_0\upharpoonright A^2 = R_1\upharpoonright A^2$.

Proof.

Let $\kappa$ be the (unique) aleph equinumerous with $X$. We define a partial order $\preceq$ on $X$ by $$x \preceq y \Longleftrightarrow (x \mathrel{R_0} y \land x \mathrel{R_1} y). $$ We verify that this well-founded partial order satisfies the hypotheses of the lemma.

Certainly $X$ is well-ordered. Also, each set $X_\alpha = \{x \in X \mid {\rm rank}_\preceq(x) = \alpha\}$ is finite; indeed, we have something even stronger.

Claim. Every set whose elements are pairwise $\preceq$-incomparable is finite.

Proof.

Suppose towards a contradiction we had an infinite set $A$ of pairwise $\preceq$-incomparable elements. Then $A$ contains an $R_0$-increasing $\omega$-sequence. But that would be an $R_1$-decreasing $\omega$-sequence! $\Box$

Finally, we check that each $X_\alpha$ is nonempty for $\alpha \lt \kappa$. But if $X_\alpha=\emptyset$, we could write $X = \bigcup_{\beta \lt \alpha} X_\beta$. Since each $X_\beta$ is finite, using $R_0$ we can well-order each $X_\beta$ in order type less than $\omega$, and thus well-order $X$ in order type at most $\omega \cdot \alpha \lt \kappa$, which contradicts our choice of $\kappa$.

The lemma then grants us a $\preceq$-chain $A \subseteq X$ of order type $\kappa$, and certainly this $A$ satisfies the conclusion of the proposition. $\Box$

Let me close by pointing out that this argument does not quite give the Erdős-Dushnik-Miller theorem, since we are requiring that $\preceq$ is a well-founded partial order, not just a well-founded relation. Given $f:[\kappa]^2\to2$, it would have been natural to set $x\prec y$ iff $x\lt y$ and $f(x,y)=0$. But $\prec$ is not transitive! (Certainly, this does not seem like a serious obstacle, and I expect a variant of the argument above to give a combinatorial ZF proof of this result as well.)

Answer by Clinton Conley for Distinct well-orderings of the same set

2011-05-08T12:18:10Z

Just a little update on this question. The argument in Andres' answer actually gives the following (in principle stronger but who knows) fact in ZF: any ordinal-valued function on a wellordered set $X$ is nondecreasing on a subset equinumerous with $X$. This doesn't seem particularly revolutionary. I don't see an adaptation of the argument that gives the full E-D-M theorem in the choiceless setting.