Partition Properties

Question

I'm currently trying to understand the proof of Erdős–Rado in Jech's Set Theory book.
But since I've already problems in the first steps, I went back to the proof of: $$2^\kappa \not\rightarrow (\omega)_{\kappa}^{2}$$

He wants to find a partition that has no homogeneous set of size 3. $S=\{0,1\}^{\kappa}$ and $F:[S]^2\rightarrow \kappa$ by $F(\{f,g\})=$ the least $\alpha < \kappa$ such that $f(\alpha)\not=g(\alpha)$.
Now comes the part I don't understand:
If $f,g,h$ distinct elements of $S$, then $F(\{f,g\})=F(\{f,h\})=F(\{g,h\})$ is impossible.
Why is it impossible? why can't there be an $\alpha$ s.t. $f(\alpha)\not= g(\alpha)\not=h(\alpha)$?

If someone also knows a nice proof of the Erdős–Rado theorem I'd be happy to hear about it!
Best, Luca

Answer 1

Assume that $F(\{f,g\})=F(\{g,h\})=F(\{f,h\})=\alpha$. Then for every $\beta<\alpha$ we have $f(\beta)=g(\beta)=h(\beta)$.

Suppose that $f(\alpha)=0$ then $g(\alpha)=1$, but then $h(\alpha)\neq g(\alpha)$ so $h(\alpha)=0$, in which case $h(\alpha)=f(\alpha)$.

This is a contradiction, since we assumed that $\alpha$ was such that $f$ and $h$ disagreed on its value (and agreed on its predecessors).

Answer 2

Miha Habič and Asaf Karagila have already answered your main question.

The simplest proof of the Erdős-Rado theorem that I’ve seen that does not explicitly use model-theoretic tools is this one. Peter Komjáth presents it in this video clip; I’ve expanded a few of the details, but I’ve kept pretty much the same notation, in case you want to see and hear the lecture as well.

Suppose that $F:\left[(2^\kappa)^+\right]^2\to\kappa$; we’ll show that $(2^\kappa)^+$ has a homogeneous subset of power $\kappa^+$.

Let $S=\{\alpha\in(2^\kappa)^+:\operatorname{cf}\alpha=\kappa^+\}$; $S$ is a stationary subset of $(2^\kappa)^+$. (The general fact is that $\{\alpha\in\lambda:\operatorname{cf}\alpha=\mu\}$ is stationary in $\lambda$ whenever $\mu$ and $\lambda$ are regular cardinals with $\mu<\lambda$.) For each $\alpha\in S$ and $i\in\kappa$ we’ll try to build an increasing sequence $\langle x_{\alpha,i}(\xi):\xi<\eta_{\alpha,i}\rangle$ of ordinals less than $\alpha$ so that if $X_{\alpha,i}=\{x_{\alpha,i}(\xi):\xi<\eta_{\alpha,i}\}$, then $X_{\alpha,i}\cup\{\alpha\}$ is homogeneous for color $i$.

Fix $\alpha\in S$ and $i\in\kappa$. If there is no $x<\alpha$ such that $\{x,\alpha\}$ is homogeneous for color $i$, then $\eta_{\alpha,i}=0$, and $X_{\alpha,i}=\varnothing$. Otherwise, let $x_{\alpha,i}(0)=\min\{x<\alpha:\{x,\alpha\}\text{ is homogeneous for color }i\}$. Suppose that $\eta\le\kappa^+$, and we’ve already chosen $x_{\alpha,i}(\xi)$ for all $\xi<\eta$. Let $X_{\alpha,i}(\eta)=\{x_{\alpha,i}(\xi):\xi<\eta\}$. If there is an ordinal $x<\alpha$ such that $X_{\alpha,i}\cup\{x,\alpha\}$ is homogeneous for color $i$, let $x_{\alpha,i}(\eta)$ be the least such ordinal. Otherwise, $\eta_{\alpha,i}=\eta$.

If there are an $\alpha\in S$ and $i\in\kappa$ such that $\eta_{\alpha,i}=\kappa^+$, we’re done: $X_{\alpha,i}\cup\{\alpha\}$ is homogeneous for $i$ and is certainly of power $\kappa^+$. Indeed, we’ve shown more: it’s of order type $\kappa^++1$. Suppose, then, that $\eta_{\alpha,i}<\kappa^+$ for each $\alpha\in S$ and $i\in\kappa$.

For $\alpha\in S$ let $X_\alpha=\bigcup_{i\in\kappa}X_{\alpha,i}$; $|X_{\alpha,i}|\le\kappa$ for each $i\in\kappa$, so $|X_\alpha|\le\kappa$. Let $f(\alpha)=\sup X_\alpha$; $\operatorname{cf}\alpha=\kappa^+$, so $f(\alpha)<\alpha$. Thus, $f:S\to(2^\kappa)^+$ is a pressing-down (or regressive) function on the stationary set, so by the pressing-down lemma (Fodor’s lemma) there are a stationary $S'\subseteq S$ and $\gamma\in(2^\kappa)^+$ such that $f(\alpha)=\gamma$ for each $\alpha\in S'$.

For each $\alpha\in S'$, then, $\big\langle\langle x_{\alpha,i}(\xi):\xi<\eta_{\alpha,i}\rangle:i\in\kappa\big\rangle$ is a $\kappa$-sequence of $\le\kappa$-sequences in $\gamma$. Now $|\gamma|\le 2^\kappa$, so there are at most $(2^\kappa)^\kappa=2^\kappa$ $\le\kappa$-sequence in $\gamma$, and similarly there are at most $2^\kappa$ $\kappa$-sequences of these sequences. On the other hand, $S'$, being stationary, is certainly cofinal in $(2^\kappa)^+$, so $|S'|>2^\kappa$. Thus, there must be distinct $\alpha,\beta\in S'$ such that $\eta_{\alpha,i}=\eta_{\beta,i}$ for each $i\in\kappa$ and $x_{\alpha,i}(\xi)=x_{\beta,i}(\xi)$ for each $i\in\kappa$ and $\xi<\eta_{\alpha,i}$.

Without loss of generality assume that $\alpha<\beta$, let $i=F(\{\alpha,\beta\})$, and let $\eta=\eta_{\alpha,i}=\eta_{\beta,i}$; then $$X_{\beta,i}\cup\{\alpha,\beta\}=X_{\alpha,i}\cup\{\alpha,\beta\}$$ is homogeneous for $i$. But this means that $\{\alpha,\beta\}\cup X_{\beta,i}(\eta)$ is homogeneous for color $i$, where $\alpha<\beta$, and therefore in the third paragraph we would have defined the ordinal $x_{\beta,i}(\eta)$ and ensured that $\eta_{\beta,i}>\eta$. This contradiction shows that in fact there must be some $\alpha\in S'$ and $i\in\kappa$ such that $\eta_{\alpha,i}=\kappa^+$, which completes the proof.