John Krueger is visiting Toronto these days, and in a conversation today, we asked ourselves how do one prove the Abraham-Todorcevic theorem that PID implies SH. Namely, that the next statement implies that there are no Souslin trees:
Definition. The P-ideal Dichotomy asserts that for every uncountable set $Z$, and every P-Ideal $\mathcal I$ over $[Z]^{\le\aleph_0}$, exactly one of the following holds:
- There exists an uncountable $A\subseteq Z$ such that $[A]^{\aleph_0}\subseteq\mathcal I$;
- There exists a sequence $\langle Z_n\mid n<\omega\rangle$ such that $\bigcup_{n<\omega}Z_n=Z$, and $[Z_n]^{\aleph_0}\cap\mathcal I=\emptyset$ for all $n<\omega$.
It turns out that the proof is quite easy, so let us give the full details.
Suppose that $(T,<_T)$ is a Souslin tree. Denote $x_\downarrow:=\{ y\in T\mid y<_T x\}$. Then, define $$\mathcal I:=\{ X\in[T]^{\le\aleph_0}\mid \forall x\in T(X\cap x_\downarrow)\text{ is finite }\}.$$
It is clear that $\mathcal I$ is an ideal. Let us show that moreover it is a P-Ideal, namely, that $\mathcal I$ is closed under taking pseduo-unions of countable sets.
Lemma. For every $\{ X_n\mid n<\omega\}\subseteq\mathcal I$, there exists some $X\in\mathcal I$ such that $X_n\setminus X$ is finite for all $n<\omega$.
Proof. As $\mathcal I$ is downward closed, we shall avoid trivialities and assume that $\{ X_n\mid n<\omega\}$ are mutually disjoint. Fix a bijection $\psi:\omega\rightarrow \bigcup_{n<\omega}X_n$ . Let $$\delta:=\sup\left\{ \text{ht}(x)\mid x\in\bigcup_{n<\omega}X_n\right\}.$$ Evidently, $\delta<\omega_1$. Then, let $S:=\{ x\in T\mid \text{ht}(x)\le\delta+1\}$, and note that $S$ is countable. Next, for all $x\in S$, define $f_x:\omega\rightarrow\omega$ by letting for all $n<\omega$: $$f_x(n):=\min\{ m<\omega\mid X_n\cap x_\downarrow\subseteq \psi“m\}.$$
As $S$ is countable, we may pick a function $f:\omega\rightarrow\omega$ such that $\{ n<\omega\mid f_x(n)> f(n)\}$ is finite, for all $x\in S$. Now, let $X:=\bigcup\{X_n\setminus \psi[f(n)]\mid n<\omega\}$. Then, for every $n<\omega$, $X_n\setminus X\subseteq \psi[f(n)]$ is finite. Assume towards a contradiction that $X\not\in\mathcal I$. Then, in particular, there exists some $x\in T$ such that $X\cap x_\downarrow$ is infinite. Since $\text{ht}(y)<\delta+1$ for all $y\in X$, there exists then some $z$ of height $\le\delta+1$ which is compatible with $x$ and $X\cap z_\downarrow$ is infinite. Thus, without loss of generality, we may assume that $x\in S$.
As $f_x\le^* f$ while $X_n\cap x_\downarrow$ is finite for all $n<\omega$, let us pick a large enough $n<\omega$ such that $f_x(n)<f(n)$ and $(X\cap x_\downarrow)\cap X_n\neq\emptyset$. Pick $z\in X\cap x_\downarrow\cap X_n$, and let $m:=\psi^{-1}(z)$. Since $z\in X_n\cap x_\downarrow$, we get that $f_x(n)>m$. In particular, $f(n)>m$, and so by definition of $X$, we get that $\psi(m)\not\in X$, contradicting the choice of $z=\psi(m)$ is in $X$. $\square$
So $\mathcal I$ is a P-ideal, and we may invoke the dichotomy.
Alternative I. There exists an uncountable $A\subseteq T$ such that $[A]^{\aleph_0}\subseteq\mathcal I$. Let us show that $A$ contains an uncountable antichain.
Proof. Since $A$ is uncountable, while the levels of the tree are countable, we can fix an injection $\varphi:\omega_1\rightarrow A$ such that $\langle \text{ht}(\varphi(\alpha))\mid \alpha<\omega_1\rangle$ is a strictly-increasing sequence.
Define a coloring $f:[\omega_1]^2\rightarrow\{0,1\}$ by letting $f(\alpha,\beta)=0$ iff $\varphi(\alpha)$ is $<_T$-incomparable with $\varphi(b)$. Then, by the Dushnik-Miller theorem $\omega_1\rightarrow(\omega_1,\omega+1)^2$, one of the following holds.
- There exists an uncountable $B\subseteq\omega_1$ such that $f“[B]^2=\{0\}$. Clearly, $\varphi[B]$ is an uncountable antichain.
- There exists a subset $B\subseteq\omega_1$ of order-type $\omega+1$ such that $f“[B]^2=\{1\}$. Let $\beta:=\max(B)$. Then $\varphi[B\cap\beta]\in[A]^{\aleph_0}\subseteq\mathcal I$. In particular, $(\varphi[B\cap\beta]\cap\varphi(\beta)_\downarrow)$ is finite, contradicting the fact that $\varphi[B\cap\beta]\subseteq\varphi(\beta)_\downarrow$. So, this case is void. $\square$
Alternative II. There exists a sequence $\langle Z_n\mid n<\omega\rangle$ such that $\bigcup_{n<\omega}Z_n=T$, and $[Z_n]^{\aleph_0}\cap\mathcal I=\emptyset$ for all $n<\omega$. Let us show that $T$ contains an uncountable chain.
Proof. Fix $n<\omega$ such that $Z_n$ is uncountable, and define a coloring $f:[Z_n]^2\rightarrow\{0,1\}$ by letting $f(x,y)=0$ iff $x$ and $y$ are $<_T$-comparable. Then, by the Dushnik-Miller theorem $\omega_1\rightarrow(\omega_1,\omega)^2$, one of the following holds.
- There exists an uncountable $B\subseteq Z_n$ such that $f“[B]^2=\{0\}$. Clearly, such a $B$ is an uncountable chain.
- There exists some $A\in[Z_n]^{\aleph_0}$ such that $f“[A]^2=\{1\}$. Then, by $[Z_n]^{\aleph_0}\cap\mathcal I=\emptyset$, we know that $A\not\in\mathcal I$, and there exists some $x\in T$ such that $A\cap x_\downarrow$ is infinite. In particular, we can find distinct $y,z\in A$ such that $y<_T x$ and $z<_T x$. Recalling that $(T,<_T)$ is a tree, we conclude that $y,z$ are $<_T$-comparable, contradicting the fact that $f(y,z)=1$. So this case is void. $\square$
For completeness, we mention that James Hirschorn proved that the strong dichotomy principle $(\star)_c$ entails that all Aronszajn trees are special.
