How Much Large-Cardinal Strength Does a Monadic Definition of a Tree Need?

A tree of height $\omega_1$ is a tree whose levels are indexed by the countable ordinals and each of whose levels is countable. A cofinal branch is a path through every level. Some such trees have no cofinal branch at all, and the most extreme of these are Souslin trees, which also contain no uncountable family of pairwise incomparable nodes. Whether every tree in some class has a cofinal branch is the kind of question that ordinary mathematics (the ZFC axioms) cannot settle. Its answer is measured by how much large-cardinal strength it needs, meaning how strong an axiom asserting the existence of very large infinite numbers is required to make the statement consistent. Leshem calibrated one such statement exactly. "Every $\omega_1$-tree first-order definable over the hereditarily countable sets has a cofinal branch" is equiconsistent with a $\Pi^1_1$ reflecting cardinal (On The Consistency of The Definable Tree Property on Alef-Symbol1). He also left open what happens for other logics. Separately, verification researchers have shown that infinite trees generated by higher-order programs are closed under two operations. The first is MSO-interpretation: building a new graph whose edges are defined by monadic second-order formulas, a logic that quantifies over elements and sets of elements but not over relations. The second is unfolding: turning a graph into the tree of all paths through it (Recursion Schemes and Logical Reflection, Higher-order Recursion Schemes and Collapsible Pushdown Automata: Logical Properties).

This note proposes carrying interpretation-plus-unfolding over to the uncountable, and asking a precise question. Start from the ordinals below $\omega_1$, alternately interpret in monadic logic and unfold. At which stage of the resulting hierarchy does a branchless tree first become definable, and how much large-cardinal strength does it cost to rule one out? The bet is a threshold phenomenon. Monadic definitions by themselves are too weak to build a branchless tree, so ZFC alone suffices. Each unfolding manufactures sequences, and enough unfoldings rebuild the hereditarily countable sets, at which point Leshem's $\Pi^1_1$ reflecting cardinal becomes necessary. Locating the threshold exactly would be the first consistency-strength calibration indexed by a structural operation rather than by a logic.

Core Claim

Fix the structure $\mathcal{O} = (\omega_1, <)$. Use countable-set MSO: monadic second-order logic whose set quantifiers range over countable subsets of $\omega_1$. Call a structure an MSO-interpretation of another if its domain and relations are defined by such formulas, possibly with countable parameters. Define transfinite unfolding $\mathrm{Unf}^{<\omega_1}(G)$ of a graph $G$ with a distinguished "limit" relation. Its nodes are sequences of $G$-vertices indexed by countable ordinals. Consecutive vertices must be $G$-edges, and at each limit stage the next vertex must be related by the limit relation to the sequence so far. The hierarchy is

$$\mathcal{T}_0 = \{\text{MSO-interpretations of } \mathcal{O}\}, \qquad \mathcal{T}_{n+1} = \{\mathrm{Unf}^{<\omega_1}(I(S)) : S \in \mathcal{T}_n,\ I \text{ an MSO-interpretation}\}.$$

Write $\mathrm{TP}_n$ for "every $\omega_1$-tree in $\mathcal{T}_n$ has a cofinal branch." There are three claims, in decreasing order of confidence.

  1. Every $\omega_1$-tree in $\mathcal{T}_n$ is first-order definable over the hereditarily countable sets. Every $\mathrm{TP}_n$ therefore follows from Leshem's property, and the Lévy collapse of a $\Pi^1_1$ reflecting cardinal gives all of them simultaneously.
  2. $\mathrm{TP}_0$ is a theorem of ZFC. Monadic definitions over $(\omega_1,<)$ do not have enough binary-relational power to encode the sequences of maps that branchless trees require.
  3. There is a least $n^\ast$, conjectured to be $1$ or $2$, at which $\mathcal{T}_{n^\ast}$ can define the hereditarily countable sets up to coding. From that stage on, $\mathrm{TP}_n$ has exactly the strength of a $\Pi^1_1$ reflecting cardinal.

Claim 3 is the new content. Its key ingredient is the transfer of the "closed under interpretation followed by unfolding" theorem from recursion schemes into this setting.

Relation to Prior Work

Leshem's paper supplies both the method and the upper bound. Its lower-bound argument builds an ultrafilter inside Gödel's constructible universe $L$ from a definable branchless tree, and its upper bound is a Lévy collapse. We reuse both. The only change is that we ask how little definitional power the lower-bound argument actually needs, which is the question Leshem raised but did not pursue.

Two papers on recursion schemes supply the closure theorem we aim to imitate. Recursion Schemes and Logical Reflection and Higher-order Recursion Schemes and Collapsible Pushdown Automata: Logical Properties prove, for countable trees, that the scheme-generated class is closed under MSO-interpretation followed by unfolding. They also prove effective MSO selection: if a formula has a satisfying set of nodes, a scheme can pick one out. That second property is the countable shadow of "a definable tree with a branch has a definable branch." Their results live at height $\omega$, where König's lemma makes the plain tree property trivial for finitely branching trees. We transfer the shape of their argument, not its theorems. Recursion Schemes and Logical Reflection also leaves open whether the countable hierarchy is strict under interpretation-plus-unfolding. Claim 3 asks the uncountable analogue of that question, about strength rather than expressiveness.

Three set-theory papers constrain the design. Souslin trees and successors of singular cardinals builds Souslin trees from diamond principles, which are combinatorial guessing axioms that hold in $L$. This tells us where to look for definable counterexamples in $L$. Large cardinals need not be large in HOD forces weakly homogeneous Souslin trees so that measurable and supercompact cardinals stop being weakly compact in HOD, the class of sets definable from ordinals. Weak homogeneity there exists precisely to keep branches undefinable, which is why our application asks whether such trees sit low in the hierarchy. The HOD Hypothesis and a supercompact cardinal pulls the other way. Under Woodin's HOD Hypothesis, measurable-in-HOD cardinals are dense below a supercompact, so tree-based failures in HOD cannot be universal. Finally, for preserving the large cardinal through preparatory forcing, we rely on the indestructibility patterns in Indestructibility properties of remarkable cardinals.

Research Program

Stage one: upper bound (claim 1). Show by induction on $n$ that each $\mathcal{T}_n$ tree is first-order definable over the hereditarily countable sets. Countable-set MSO over $\omega_1$ translates directly into first-order statements about countable sets. Transfinite unfolding of a definable graph produces sequences of countable length, which are themselves hereditarily countable once coded. Leshem's collapse then gives the property at every level at once. We also check that his Martin's Axiom variant, which needs a weakly compact cardinal, transfers to every level.

Stage two: ZFC result at level 0 (claim 2). Analyse which binary relations on $\omega_1$ are definable in countable-set MSO with countable parameters. The working hypothesis is that, modulo a club, they are generated by finitely many order types. A club is a closed unbounded subset of $\omega_1$, roughly a "large" set of countable ordinals. If that holds, any $\omega_1$-tree interpreted at level 0 is, on a club, a finite union of well-understood pieces, and one reads a branch off directly. A cheap failure mode exists here. If a countable parameter already lets level 0 code a branchless tree, then $n^\ast = 0$ and the threshold story collapses into a single level. That is still a clean result.

Stage three: the coding lemma and the threshold (claim 3). This is the core. We prove a closure lemma: an MSO-interpretation of a transfinite unfolding is again an unfolding of an interpretation of the previous level, mirroring the recursion-scheme closure theorem. We then prove a coding lemma: some $\mathcal{T}_{n^\ast}$ interprets a copy of the hereditarily countable sets, with its membership relation, using well-founded trees as codes.

Given both lemmas, Leshem's lower-bound argument runs inside $\mathcal{T}_{n^\ast}$ and yields a $\Pi^1_1$ reflecting cardinal in $L$. Below $n^\ast$ we aim for the converse. We plan to show that in $L$, where Leshem's argument does produce first-order definable Souslin trees, those trees are not in $\mathcal{T}_n$ for $n < n^\ast$. The method is a composition argument that bounds the "monadic type" of trees at each level.

Stage four: application to HOD. In the model built in Large cardinals need not be large in HOD, ask the same level question at a general cardinal $\kappa$, with $(\kappa,<)$ and parameters of size less than $\kappa$ in place of $\omega_1$. The question is whether the HOD-visible Souslin tree on $\kappa$ belongs to the analogous hierarchy over $(\kappa,<)$ with ordinal-definable parameters. A positive answer sharpens their theorem into "large in $V$ but monadically non-weakly-compact in HOD." This stage depends on stages one to three, and we drop it if the threshold is not found.

Baselines

Naive reference point. Use Leshem's result unchanged, treating every $\mathrm{TP}_n$ as costing a $\Pi^1_1$ reflecting cardinal because it is implied by the full first-order property. This is the do-nothing answer, and it is correct as an upper bound. The proposal beats it only by proving that some level $\mathrm{TP}_n$ is strictly weaker, provable in ZFC or at least not requiring the reflecting cardinal.

Strongest existing method. The strongest competitor is Leshem's own lower-bound technique applied directly to the restricted class, with no unfolding machinery at all. This means building the $L$-ultrafilter from whatever trees countable-set MSO happens to define. To keep the comparison fair, we use the same base structure, the same parameters, and the same target cardinal, and simply try his construction at level 0 first.

Ablation isolating unfolding. Replace transfinite unfolding with ordinary $\omega$-length unfolding and with pure iterated interpretation, and recompute the threshold. If the threshold is unchanged, unfolding is not the operative ingredient and claim 3 must be reformulated.

Computational sanity check. The countable shadow is tested against the effective-selection procedure of Higher-order Recursion Schemes and Collapsible Pushdown Automata: Logical Properties and the HORSATP parity checker from Streett Automata Model Checking of Higher-Order Recursion Schemes. The file reports only a qualitative comparison: HORSATP "outperforms previous parity automata model checkers (APTRECS, TRAVMC2) on most inputs." No reported result found on Lacuna for per-instance runtimes on that 97-problem suite, so we will rerun the tool ourselves under identical hardware and timeouts rather than quote a number.

Why not just…?

Why not just apply Leshem's theorem, since countable-set MSO is first-order over the hereditarily countable sets? That yields only the upper bound, which is stage one. The lower bound is exactly what is in question. This alternative is a real threat. If the coding lemma holds at level 0 with a trivial parameter trick, the proposal shrinks to a short corollary. Stage two is designed to detect this early. If it happens, we move the program to full MSO over $(\omega_1,<)$, with arbitrary subsets as parameters, where Leshem's framework does not apply.

Why not just build a definable Souslin tree from diamond in $L$, as in Souslin trees and successors of singular cardinals? A diamond construction shows that some definable branchless tree exists in $L$. It does not say at which hierarchy level that tree lives, and the level is the whole content of claim 3. We do use this construction as the source of candidate counterexamples in stage three. The proposal's contribution is the level bound on those candidates.

Why not just stay countable and run recursion-scheme model checkers? At height $\omega$, finitely branching trees always have branches, so the tree property carries no consistency strength there. The countable experiments can test the closure and selection patterns we hope to lift. They cannot test strength, and we treat them only as heuristics.

Proposed Experiments and Decisive Checks

The computational check uses the benchmark suites in Saturation-Based Model Checking of Higher-Order Recursion Schemes and the 97 parity problems of Streett Automata Model Checking of Higher-Order Recursion Schemes. For each scheme we apply one and two rounds of a fixed MSO-interpretation followed by unfolding. We then ask the selector for a branch satisfying a property chosen to need monadic power, such as "visits a marked node infinitely often." We record selection success, timeouts, and the growth of the scheme's order across rounds.

The prediction is that the order rises by at most one per round. This would be the countable analogue of the closure lemma, though Recursion Schemes and Logical Reflection leaves the corresponding strictness question open. Pathological instances such as "fibstring," where HORSAT already times out, are expected to dominate the failures.

The decisive mathematical checks are three theorems:

  1. a ZFC proof of $\mathrm{TP}_0$;
  2. the coding lemma at a specific $n^\ast$, which transfers Leshem's $\Pi^1_1$ reflecting lower bound to $\mathrm{TP}_{n^\ast}$;
  3. a proof that every Souslin tree that is first-order definable over the hereditarily countable sets in $L$ lies outside $\mathcal{T}_{n^\ast-1}$.

If check 1 fails, the threshold sits at level 0. If check 3 fails, the strength does not depend on level. Either negative result is publishable as a calibration, and either one ends the threshold program.