3 mathand -> land correction.

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

2 deleted 4 characters in body

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 \mathand 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 the argument 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.)

1

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 \mathand 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 the argument this 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.)