Set-theoretic tree

A partial order in which the strict predecessors of each node form a well-order. The height of a node is the order type of its predecessors; nodes of a common height form a level. This order-theoretic meaning is distinct from a graph-theoretic tree.

For an uncountable cardinal $\kappa$, this convention requires a cofinal branch in every separated rooted tree of height $\kappa$ with fewer than $\kappa$ immediate successors per node, without bounding level sizes. It is stronger than the usual tree property away from inaccessible cardinals. If $\mathrm{cf}(\kappa )<\kappa$, attach chains of cofinally increasing lengths below $\kappa$ above fewer than $\kappa$ children of one root; this contradicts the property. If $2^{\lambda }\ge \kappa$ for $\lambda <\kappa$, take a binary tree through level $\lambda$, choose $\kappa$ distinct nodes there, and attach to the $\xi$th a chain of length $\xi$. It has height $\kappa$, binary branching, and no cofinal branch. Hence the property implies that $\kappa$ is a strongly inaccessible cardinal. At such a cardinal a separated tree with small immediate branching has small levels, so this convention agrees with the usual tree property. It is not the different notion called the strong tree property in modern set theory.

A tree is splitting if every node has two incompatible extensions. This property is additional to height and level-size bounds in a kappa-tree. A cofinal branch through a splitting tree of regular uncountable height produces an equally large antichain by taking off-branch extensions and proceeding beyond their divergence heights. Thus a splitting ${\omega }_1$-tree with countable antichains has no uncountable chains; the nonsplitting chain ${\omega }_1$ itself is a counterexample to omitting splitting.

At a limit level, two nodes with the same predecessor at every smaller level must be equal. This is a uniqueness condition; it need not provide an upper node for every cofinal branch through the lower levels.

Every node has an extension at every higher level below the height of the set-theoretic tree. Equivalently, its extension heights are unbounded in the set-theoretic tree height. Having no terminal nodes alone is weaker.

For a kappa-tree, retain nodes whose extension heights are unbounded in $\kappa$. The retained nodes are predecessor-closed. Each level remains nonempty: otherwise regularity would bound the union of fewer than $\kappa$ bounded extension sets. The same argument above a retained node ensures retained extensions at every later level. Singular height invalidates this proof and the unrestricted conclusion.

For a regular uncountable cardinal number $\kappa$, a set-theoretic tree of height $\kappa$ with nonempty levels of cardinality less than $\kappa$. The regular-height convention is important for the unbounded-extension kernel of a regular tree.

For an infinite cardinal $\kappa$, the tree property says that every tree of height $\kappa$ with nonempty levels of cardinality less than $\kappa$ has a cofinal branch. In the all-trees-of-size-$\kappa$ convention it also forces regularity: disjoint chains of lengths cofinal in a singular $\kappa$ form a counterexample. It does not, by itself, imply strong inaccessibility. A strong limit cardinal with the tree property satisfies the self-partition relation by applying it to the end-homogeneous coloring tree. At a strongly inaccessible cardinal this is the usual weak-compactness characterization.

For infinite regular cardinals $\kappa <\lambda$, a $\lambda$-tree whose levels all have size less than $\kappa$ has a cofinal branch. At levels of cofinality $\kappa$, bound all heights distinguishing distinct predecessor chains. The Fodor lemma makes this bound constant on a stationary set; one predecessor at that height occurs stationarily often. The resulting predecessor chains agree below their common heights and unite into a branch through every level. Distinct limit-level nodes with identical predecessor chains do not affect this argument.

A set-theoretic tree of height ${\omega }_1$ with countable levels and at least ${\aleph }_2$ distinct cofinal branches.

Let $\kappa$ be strongly inaccessible cardinal in the ground model and perform the finite Lévy collapse to omega-one. The ground full binary set-theoretic tree of height $\kappa$ has all levels of size less than $\kappa$, so these levels become countable. Its at least $({\kappa }^{+}{)}^M$ ground branches remain distinct. The chain in a partial order condition preserves $({\kappa }^{+}{)}^M$, which is the extension ${\aleph }_2$. The unchanged ground set-theoretic tree therefore witnesses the Kurepa hypothesis.

There exists an ${\omega }_1$-tree with countable levels and at least ${\aleph }_2$ distinct cofinal branches.

There is $\mathcal{F}\subseteq \mathcal{P}({\omega }_1)$ of size ${\aleph }_2$ such that $\{X\cap \alpha :X\in \mathcal{F}\}$ is countable for every $\alpha <{\omega }_1$. Its initial-segment tree, pruned and leveled to be normal, is a Kurepa tree.

A set-theoretic tree of height ${\omega }_1$ with countable levels and no cofinal branch. More generally, a $\kappa$-Aronszajn tree has height a regular uncountable $\kappa$, levels of size less than $\kappa$, and no cofinal branch.

Given coherent coinfinite injections into omega, use all restrictions $e_{\alpha }\upharpoonright \beta$, where $\beta \le \alpha <{\omega }_1$, ordered by proper extension. Every level is countable because its nodes differ finitely from a fixed function on a countable domain. An uncountable chain in a partial order would have unbounded domain heights, and its union would inject ${\omega }_1$ into $\omega$, which is impossible.

An Aronszajn tree with no uncountable tree antichain. A normal splitting Suslin tree yields a Suslin line by a lexicographic ordering followed by Dedekind completion.

A well-pruned set-theoretic tree that is an Aronszajn tree and a Suslin tree gives a forcing with the countable chain condition for forcing: stronger nodes extend weaker ones. The ${\omega }_1$ dense subsets of a forcing order of nodes at or above each level cannot all be met by a filter in an ordered set, since that would produce a cofinal branch. Thus ${\mathrm{MA}}_{{\aleph }_1}$ fails. When the continuum exceeds ${\aleph }_1$, full Martin axiom includes this instance.

An Aronszajn tree that is a union of countably many tree antichains. Equivalently, it admits a map into a countable set that is injective on each chain.

Construct countable levels of bounded increasing rational sequences, maintaining the bounded rational extension property. At successor stages append every allowed rational. At a countable limit, handle each earlier-node/rational-cap pair by a cofinal sequence of extensions with values approaching a rational strictly below the cap. Its union has that rational supremum. Countably many requirements give a countable new level. Strictly increasing labels exclude uncountable chains, and label fibers are tree antichains, so the result is a special Aronszajn tree.

For every earlier node and rational cap above its label, an extension at each later level remains below the cap. In the rationally labelled Aronszajn tree construction this reserves space for limit-stage unions. Choosing an intermediate rational and forcing successive values toward it ensures a rational supremum and strictly increasing labels even at limit levels.

A set-theoretic tree of height ${\omega }_2$, levels of size at most ${\aleph }_1$, and no cofinal branch. The Continuum hypothesis supplies one through the minimal-walk tree.

A set-theoretic tree with one root, extensions of every node at every higher level, at least two immediate successors for every node, and distinct limit-level nodes distinguished by their predecessor chains. If splitting occurs only at later levels, a continuous cofinal selection of levels can enforce immediate splitting.

A maximal chain with nodes at unbounded heights in a set-theoretic tree. Taking predecessor closure gives one node at each level below the tree height.

A set of pairwise incomparable nodes in a set-theoretic tree. A maximal tree antichain has a comparable member for every node of the tree.