The P-Ideal Dichotomy and the Souslin Hypothesis

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 {\mathrm{\aleph }}_0}$, exactly one of the following holds:

• There exists an uncountable $A\subseteq Z$ such that $[A{]}^{{\mathrm{\aleph }}_0}\subseteq \mathcal{I}$;
• There exists a sequence $⟨Z_n\mid n<\omega ⟩$ such that $\bigcup _{n<\omega }{Z}_n=Z$, and $[Z_n{]}^{{\mathrm{\aleph }}_0}\cap \mathcal{I}=\mathrm{\varnothing }$ 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 {\mathrm{\aleph }}_0}\mid \mathrm{\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 \to \bigcup _{n<\omega }{X}_n$ . Let $$\delta :=sup\{\text{ht}(x)\mid x\in \bigcup _{n<\omega }{X}_n\}.$$ 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 \to \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 \to \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\notin \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 }^{\ast }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\ne \mathrm{\varnothing }$. 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)\notin X$, contradicting the choice of $z=\psi (m)$ is in $X$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

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{]}^{{\mathrm{\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 $\phi :{\omega }_1\to A$ such that $⟨\text{ht}(\phi (\alpha ))\mid \alpha <{\omega }_1⟩$ is a strictly-increasing sequence.
Define a coloring $f:[{\omega }_1{]}^2\to \{0,1\}$ by letting $f(\alpha ,\beta )=0$ iff $\phi (\alpha )$ is ${<}_T$-incomparable with $\phi (b)$. Then, by the Dushnik-Miller theorem ${\omega }_1\to ({\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, $\phi [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 $\phi [B\cap \beta ]\in [A{]}^{{\mathrm{\aleph }}_0}\subseteq \mathcal{I}$. In particular, $(\phi [B\cap \beta ]\cap \phi (\beta {)}_{\downarrow })$ is finite, contradicting the fact that $\phi [B\cap \beta ]\subseteq \phi (\beta {)}_{\downarrow }$. So, this case is void. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Alternative II. There exists a sequence $⟨Z_n\mid n<\omega ⟩$ such that $\bigcup _{n<\omega }{Z}_n=T$, and $[Z_n{]}^{{\mathrm{\aleph }}_0}\cap \mathcal{I}=\mathrm{\varnothing }$ 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\to \{0,1\}$ by letting $f(x,y)=0$ iff $x$ and $y$ are ${<}_T$-comparable. Then, by the Dushnik-Miller theorem ${\omega }_1\to ({\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{]}^{{\mathrm{\aleph }}_0}$ such that $f“[A{]}^2=\{1\}$. Then, by $[Z_n{]}^{{\mathrm{\aleph }}_0}\cap \mathcal{I}=\mathrm{\varnothing }$, we know that $A\notin \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. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

For completeness, we mention that James Hirschorn proved that the strong dichotomy principle $(\star {)}_c$ entails that all Aronszajn trees are special.