MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A family of functions $F$ is coherent when for every $f,g \in F$, $\{ x \in dom(f) \cap dom(g) : f(x) \not= g(x) \}$ is finite. A tree on $\omega_1$ is coherent if it is a coherent collection of functions whose domain is a countable ordinal, ordered by extension.

In Todorcevic's chapter of the Handbook of Set Theory, he has:

Theorem 13.21 Assuming the P-ideal dichotomy, for every coherent family of functions $f_a : a \to \omega (a \in \mathfrak{J})$ indexed by some P-ideal $\mathfrak{J}$ of countable subsets of some set $\Gamma$, either

(1) there is an uncountable $\Delta \subseteq \Gamma$ such that $f_a \restriction \Delta$ is finite-to-one for all $a \in \mathfrak{J}$, or

(2) there is a $g: \Gamma \to \omega$ such that $g \restriction a =^* f_a$ for all $a \in \mathfrak{J}$.

The proof he gives is really opaque at the end, but the two alternatives are supposed to correspond to the two alernatives of the P-ideal dichotomy for a sub-ideal $\mathfrak{L} \subseteq \mathfrak{J}$. Now suppose we have a coherent tree $T$ on $\omega_1$ consisting of functions that take values in some finite set $A$, say $A = \{ 0,...,n\}$, which is closed under finite modifications. Then the first alternative is not applicable, so we get (2), and thus $T$ has a branch.

This seems really incredible to me because the written proof does not give any indication why this is true. He just defines the sub-ideal $\mathfrak{L}$ of sets for which the corresponding function is finite-to-one and proves it is a P-ideal. This will automatically be the ideal of finite subsets of $\Gamma$ if we assume the coherent family takes values in a fixed finite set $A$. Somehow the second alternative of PID (the decomposition into countably many pieces all orthogonal to $\mathfrak{L}$) is supposed to give the branch in an obvious way.

But it is NOT obvious! Because there are models in which there are coherent Suslin $\omega_1$-trees of binary functions. For example, this happens under $\diamondsuit$, or when one Cohen real is added. So the second horn of PID does not tell you anything by itself about this situation.

So if Todorcevic's theorem is correct, we would have:

Theorem (ZFC+PID)??? Any coherent $\omega_1$-tree consisting of binary functions closed under finite modifications has a branch.

Is it because we have the following?

Theorem (ZFC)??? Any coherent $\omega_1$-tree consisting of binary functions closed under finite modifications is either Suslin or has a branch.

What's the deal? By the way, we can prove in ZFC that there are coherent Aronszajn trees consisting of binary functions, but these are not necessarily closed under finite modifications, so this closure must somehow be essential. Edit: We can get them closed under finite modifications, see below.

I am pretty sure the theorem is wrong. Please let me know if there is a mistake.

Proof #1 (in ZFC) Let $T$ be the $\omega_1$ tree given by a sequence of coherent injections $\langle e_\alpha : \alpha < \omega_1 \rangle$. That is, each $e_\alpha : \alpha \to \omega$ is an injection, and for all $\alpha < \beta$, $\{ \gamma < \alpha : e_\alpha(\gamma) \not= e_\beta(\gamma) \}$ is finite. $T$ is the closure of this family under finite modifications. This is standard and a construction can be found in Kunen's book.

Now define a tree $T'$ on $\omega_1 \times \omega$ by putting $f \in T'$ if for some $\alpha, dom(f) = \alpha \times \omega$, and for some $g \in T$ with domain $\alpha$, $f(\beta,n) = 1$ when $g(\beta) = n$, and $f(\beta,n) = 0$ otherwise. Clearly $T'$ is coherent. Let $T''$ be the closure of $T'$ under finite modifications. (Note this makes $T''$ code many relations which are not functions, but are only finitely many mistakes away from being a function.)

All this happens in ZFC, so assume PID holds as well. Let $b$ be the branch through $T''$ given by 13.21. There is a stationary $S_1 \subseteq \omega_1$ and a $\xi < \omega_1$, such that for all $\alpha \in S_1$, the modifications required to make $b \restriction (\alpha \times \omega)$ be in $T'$ are in $\xi \times \omega$. There is a stationary $S_2 \subseteq S_1$ such that for all $\alpha \in S_2$, the same modification $\sigma$ works. So $\sigma(b) \in T'$, and this codes a branch in $T$, which is impossible.

Proof #2 (assuming Con(ZFC+supercompact)) (This is reasonable because PID comes from PFA which comes from forcing from a supercompact cardinal, the currently best-known upper bound for the strength of PFA.)

Following Paul's observation, first add a Cohen real, and let $T$ be the coherent Suslin tree of functions from countable ordinals to $\{0,1\}$, closed under finite modifications, that is added. (This is also due to Todorcevic, but I know this is correct.) Or force $\diamondsuit$ with a continuum-sized forcing. Then specialize the tree using the standard c.c.c. specializing forcing. Then let $\kappa$ be supercompact, and use it to force PFA. The forcing, due to Baumgartner, is proper and preserves our special, coherent, Aronszajn $\omega_1$-tree. Then by 13.21, the tree has a cofinal branch. But this is impossible because the speciality is preserved by all $\omega_1$-preserving forcings, and special trees don't have branches.

share|cite|improve this question
The second theorem you mention (from ZFC) cannot be true; take a model where there is a coherent $\omega_1$-tree of binary functions which is Suslin. Now specialize it. – Paul McKenney Oct 18 '13 at 11:26
Thanks, Paul. I added to my answer in light of your comment. – Monroe Eskew Oct 18 '13 at 19:41
The existence of an Aronszajn subtree of ${}^{<\omega_1}2$ which is closed under finite modifications is a consequence of ZFC. – saf Oct 18 '13 at 20:10
@saf, This follows from the Proof#1 below, do you know another argument? – Monroe Eskew Oct 18 '13 at 20:12
You don't need the supercompact for the consistency of PID restricted to ideals over underlying sets of size $\omega_1$. Abraham and Todorcevic proved that this is equiconsistent with ZFC. In fact, starting with any model of GCH, you can force this principle without adding reals. Also, it appears that in that paper, Abraham and Todorcevic claim that this restricted form of PID entails that every coherent Aronszajn tree is special. – saf Oct 18 '13 at 22:13

The following statement appears on page 256 of Todorcevic´s "A dichotomy for P-ideals of countable sets", Fund.Math., 166, 2000.


For every family $\mathcal{F} = \{ f_A : A \to \omega : A \in \mathcal{A} \}$ of weakly coherent functions indexed by some $\sigma$-directed family $\mathcal{A}$ of countable subsets of some set $S$, either

(1) there is an uncountable $X \subseteq S$ such that $f \restriction X$ is finite-to-one for every $f \in \mathcal{F}$, or

(2) $S$ can be decomposed into countably many sets on which each of the functions from $\mathcal{F}$ is bounded.

The paper gives a proof of $PID \Rightarrow (*_d)$ which is essentially identical to the proof given for Theorem 13.21 in the Handbook.

Note that in the case of binary functions weak coherence is automatic and the conclusion of $(*_d)$ says nothing.

share|cite|improve this answer
The proof of 13.21 seems to just show the same conclusions for a family of coherent rather than just weakly coherent functions. So 13.21 is a special case of $(*)_d$, if we replace the (2) in the handbook with the (2) from this paper. – Monroe Eskew Oct 24 '13 at 22:45

Your Answer


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.