Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

6 Answers 6

up vote 7 down vote accepted

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.)

share|improve this answer
    
indeed, this is very nice. And the final claim exceeds anything one would expect. Very nice. –  Michael Blackmon Jan 28 '11 at 22:43

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.

share|improve this answer

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$.

share|improve this answer
1  
Hi Justin, This nice idea unfortunately uses choice. What do you do if all uncountable cardinals are singular? –  Andres Caicedo Sep 29 '10 at 21:42
    
Ah you are right of course. Thanks. –  Justin Palumbo Sep 29 '10 at 22:10
    
I edited my answer to point out the fact it only works in cases where |X| is a regular cardinal or the limit of regular cardinals. –  Justin Palumbo Sep 29 '10 at 22:14
    
There's another use of choice in this argument, but it's probably easy to avoid. You seem to be choosing the $A_n$'s. Fortunately, I think the proof when $\kappa$ is regular provides a canonical construction of the required $A_n$'s. –  Andreas Blass Sep 30 '10 at 0:23

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.

share|improve this answer
    
Hi Michael, Thanks! The appeal to NBG is unnecesary, your argument easily formalizes in ZF. I believe this argument runs into the same issue as the others, though. I will check later, once I find a second. –  Andres Caicedo Jan 24 '11 at 14:51
    
Yeah, I just realized I didn't need NBG and was editing it when you posted your comment. Guess thats what I get for jumping the gun. –  Michael Blackmon Jan 24 '11 at 14:55

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.

share|improve this answer
    
I think you have to be careful in the case where $\kappa$ is singular; as then the sequence of y's you build might be cofinal at an early stage. –  Justin Palumbo Sep 29 '10 at 21:36
1  
Hi Alessandro. As Justin pointed out, this construction quickly runs into difficulties if you are at a singular cardinal. For example, if $X=\omega_1$ has cofinality $\omega$, then $y_\omega$ may already be undefined. –  Andres Caicedo Sep 29 '10 at 21:43
    
I'm sorry I forgot to add "regular" after cardinal, implying basically what you wrote at the very end of your answer (even though I have to admit it is somehow trickier than I thought). In any case, your answer is much clearer... –  Alessandro Sisto Sep 29 '10 at 21:47

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.

share|improve this answer
1  
Hi David. This is false. The appropriate result for infinite sets is the Erd˝os-Rado theorem. It is usually proved under choice, but there is an appropriate version that holds without choice; it has been found independently a few times (by Keisler and Morley in 1967, by Kleinberg and Seiferas in 1973, and by Forster in 2007.) The result is that for any set $x$, any ordinal $\delta$, and any nonzero $n<\omega$, there is some ordinal $\kappa$ such that $\kappa\to(\delta)^n_x$. This results contains the Ramsey theorem for graphs, corresponding to $n=x=2$. Typically, the least witness $\kappa$... –  Andres Caicedo Sep 30 '10 at 2:43
    
...is much larger than $\delta$. See for example my notes at caicedoteaching.wordpress.com/2009/04/24/… To be concrete about your statement being false: There is a graph with vertex set the reals such that there is no complete subgraph with $\omega_1$ many vertices and no empty subgraph with $\omega_1$ many vertices. This is a result of Erd˝os-Kakutani. –  Andres Caicedo Sep 30 '10 at 2:47
    
Thanks for the correction! –  David Speyer Sep 30 '10 at 2:48
    
By the way, most proofs of the Erd˝os-Rado theorem are definitely combinatorial. –  Andres Caicedo Sep 30 '10 at 2:49
    
Andres: Could you give references for the Keisler-Morley and Kleinberg-Seiferas results? Incidentally I think I can prove that consistently ER is false when the target is not well orderable. Namely, it is consistent that every set is the union of continuum many sets, none embedding the reals (and AC fails). This is probably well known. The model used is the standard symmetric model for an infinite Dedekind finite set. –  Péter Komjáth Sep 30 '10 at 7:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.