Set-Theoretic Trees, Delta Systems, and Diamond: Examples and Counterexamples

The predecessors of $s:n\to 2$ are exactly $s\upharpoonright k$ for $k<n$, ordered like $n$. Thus its height is $n$. There is one empty string at level zero; appending either $0$ or $1$ to each length-$n$ string gives all length-$(n+1)$ strings without repetition. Induction gives $\mathrm{\mid }{T}_n\mathrm{\mid }=2^n$, including $2^0=1$.

Put $z_n(k)=0$ for $k<n$. Then $z_n=z_{n+1}\upharpoonright n$, so $B=\{z_n:n<\omega \}$ is an infinite chain. A string $s$ of length $n$ comparable with every $z_k$ must equal $z_n$, since comparable strings of equal length coincide. Thus $B$ is maximal and is a cofinal branch.

If $S\subseteq 2^{<\omega }$ is infinite and prefix closed, it has finite levels, each of size at most $2^n$. Its lengths cannot be bounded by $N$, since then $\mathrm{\mid }S\mathrm{\mid }\le {\sum }_{n=0}^N{2}^n=2^{N+1}-1$. Its height is therefore $\omega$, and F1 supplies an infinite branch. This last appeal inherits the ZFC assumption; the explicit branch in step 2.1 needs no choice.

The predecessors of a sequence $s$ of length $n$ are exactly its restrictions to lengths $0,1,\dots ,n-1$, in that order. Thus the proper initial-segment relation is transitive and irreflexive, its predecessor orders are finite well-orders, and ${\mathrm{ht}}_T(s)=n$ by F1. The empty sequence is the unique root.

The level $T_0$ is a singleton. For each fixed $n$, the set ${\omega }^n$ of length-$n$ sequences is countable: start with the singleton ${\omega }^0$ and iterate F2 using ${\omega }^{n+1}\cong {\omega }^n\times \omega$. Since $T_n\subseteq {\omega }^n$, F3 makes every level countable. For $n>0$ the explicit sequence $(n-1,n-2,\dots ,0)$ has length $n$ and lies in $T_n$. Therefore all finite heights occur and the height is exactly $\omega$. The first level contains every $(m)$ for $m\in \omega$, so it is infinite.

If $B$ were a cofinal branch, its sequences would be nested and have unbounded lengths by F1. Their union would therefore be a function $b:\omega \to \omega$. For each $n$, take a node in $B$ of length at least $n+2$; its strict decrease gives $b(n+1)<b(n)$. The nonempty range of $b$ has a least element $b(k)$ by F4, but $b(k+1)$ is a smaller element of the same range, a contradiction. Thus the displayed countable-level tree has no cofinal branch. Its infinitely branching root and infinite first level explain precisely the failure of the finite-level hypothesis.

For each $\alpha$, $\alpha +1\mathrm{\ne }0$, so $a_{\alpha }$ has two elements. Distinct ordinals have distinct successors: if $\alpha <\beta$, then $\alpha +1\le \beta <\beta +1$. Thus $a_{\alpha }\cap a_{\beta }=\{0\}$ whenever $\alpha \mathrm{\ne }\beta$. Also $a_{\alpha }=a_{\beta }$ would identify their unique nonzero elements and force $\alpha =\beta$. Consequently the family has size ${\omega }_1$ and is a delta system with root $\{0\}$.

For $\alpha \mathrm{\ne }\beta$, $b_{\alpha }\cap b_{\beta }=\mathrm{\varnothing }$. The map $\alpha \mapsto b_{\alpha }$ is injective, so this is another ${\omega }_1$-sized delta system, with empty root. For instance $a_0\cap a_1=\{0,1\}\cap \{0,2\}=\{0\}$ whereas $b_0\cap b_1=\{0\}\cap \{1\}=\mathrm{\varnothing }$.

Every member of $\mathcal{F}$ is countable by $\alpha <{\omega }_1$, and infinite because $\omega \subseteq \alpha$. There are ${\omega }_1$ many such ordinals: the family is a subset of ${\omega }_1$, and if it were countable its union with the countable initial segment $\omega$ would make ${\omega }_1$ countable. Thus this family satisfies the proposed countability hypothesis but not F2's finiteness hypothesis.

For $\alpha <\beta <\gamma$ in $\mathcal{F}$, ordinal inclusion gives $\alpha \cap \beta =\alpha$ and $\beta \cap \gamma =\beta$. These intersections differ since $\alpha \mathrm{\ne }\beta$. Therefore no three members form a delta system, and in particular no uncountable subfamily does. This refutes the asserted strengthening.

Each of $p,q,q^{\mathrm{\prime }}$ has one-node domain, so there is no distinct comparable pair within its domain and F1 makes it a condition. Since $x{<}_{T}y$, the nodes are distinct; each intersection of the domain of $p$ with that of $q$ or $q^{\mathrm{\prime }}$ is empty, so the functions agree on overlap. But $(p\cup q)(x)=0=(p\cup q)(y)$ violates the required inequality on $x{<}_{T}y$. Thus $p\cup q$ is not a condition and F1 makes $p,q$ incompatible.

The function $u=p\cup q^{\mathrm{\prime }}=\{(x,0),(y,1)\}$ has finite domain $\{x,y\}$ and its only unordered pair of distinct nodes has labels $0\mathrm{\ne }1$. Therefore it is a specializing condition and $u\supseteq p,q^{\mathrm{\prime }}$, so $u\le p,q^{\mathrm{\prime }}$. This is the explicit common bound verifying compatibility.

F1 supplies the tree under the stated diamond and A1 hypotheses. Its successor sets contain at least two ordinal-coded nodes, so their first and second members define $t^0,t^1$ without further choices. The split-pair construction in F2 applies to exactly these selections. Each first successor determines its parent, so $t\mapsto (t^0,t^1)$ is injective and $\mathrm{\mid }E\mathrm{\mid }={\mathrm{\aleph }}_1$. For incomparable parents even the first successors are incompatible; for $t{<}_{T}u$, simultaneous coordinate compatibility would put the two distinct $t$-successors below $u$, impossible by unique predecessors, as calculated in F2. Thus the displayed $E$ is the explicit antichain, and $P$ is ccc.

If $P$ were Knaster, F3 would make $P\times P$ Knaster and F4 would make it ccc. This contradicts the antichain $E$ in step 1.1. Hence this conditional ccc example is not Knaster; the diamond assumption remains necessary for the tree supplied here.

Take the normal splitting special Aronszajn tree $T$ supplied by F1 under A1. By F3 and F2 it has height ${\omega }_1$ and countable levels, so it satisfies the proposed hypothesis, including its optional normality and splitting restrictions. Specialness supplies $f:T\to \omega$ with different values on comparable distinct nodes. In the construction this map is obtained by coding the strictly increasing rational labels by natural numbers.

If $B$ were a cofinal branch of $T$, its nodes would be pairwise comparable, so $f\upharpoonright B$ would be injective. Thus $B$ and its image under the height map would be countable. F4, using the countable choice supplied by A1, says that this height image cannot be cofinal in ${\omega }_1$. This contradicts the definition of a cofinal branch. Hence this concrete constructed tree refutes the statement.