## Formalized Name Weak Compactness and $\Pi^1_1$ Indescribability ## Formalized Statement Let $\kappa$ be an inaccessible cardinal, meaning an uncountable regular strong-limit cardinal. Fix, uniformly for every ordinal $\alpha\leq\kappa$, first-order definable coding relations in $(V_\alpha,\in)$ for finite tuples, ordered pairs, relations, functions, and finite sequences of elements of $V_\alpha$, compatible with restriction from $V_\beta$ to $V_\alpha$ whenever $\alpha<\beta\leq\kappa$. A $\kappa$-tree means a partially ordered set $(T,<_{T})$ equipped with a height map $\ell_T:T\to\kappa$ such that every level $T_\alpha:=\{t\in T:\ell_T(t)=\alpha\}$ is nonempty and has cardinality $<\kappa$, every predecessor set $\{s\in T:s<_{T}t\}$ is well-ordered by $<_{T}$ with order type $\ell_T(t)$, and $s<_{T}t$ implies $\ell_T(s)<\ell_T(t)$. A cofinal branch is a linearly ordered subset of $T$ meeting every level below $\kappa$. Then the following are equivalent: 1. $\kappa$ is weakly compact, in the sense that every $\kappa$-tree has a cofinal branch. 2. $\kappa$ is $\Pi^1_1$ indescribable: for every $A \subset V_\kappa$ and every $\Pi^1_1$ sentence $\varphi$ in the second-order language $\{\in,\dot A\}$ with full second-order semantics, if $(V_\kappa,\in,A)\models \varphi$, then there exists an ordinal $\alpha<\kappa$ such that $(V_\alpha,\in,A\cap V_\alpha)\models \varphi^\alpha$, where $\varphi^\alpha$ is obtained from $\varphi$ by restricting first-order quantifiers to $V_\alpha$ and second-order quantifiers to $\mathcal P(V_\alpha)$. ## Proof [proofplan] We prove both implications by coding second-order reflection failures into trees. For the forward direction, write a $\Pi^1_1$ sentence as $\forall X\,\theta(X)$ with $\theta$ first-order; if reflection fails at every $\alpha<\kappa$, the bounded counterexamples form a $\kappa$-tree, and a cofinal branch gives a global counterexample to the truth of $\forall X\,\theta(X)$ over $V_\kappa$. For the converse, a branchless $\kappa$-tree can be coded by a unary predicate over $V_\kappa$; the assertion that this code is a $\kappa$-tree with no cofinal branch is $\Pi^1_1$, and reflection produces an initial segment that externally has a branch, contradicting the reflected branchlessness. [/proofplan] [step:Put the $\Pi^1_1$ sentence into one-predicate universal form] Let $A\subset V_\kappa$ and let $\varphi$ be a $\Pi^1_1$ sentence in the language $\{\in,\dot A\}$. By the definition of $\Pi^1_1$, and using the uniform finite-tuple coding map $\operatorname{Code}_m:\mathcal P(V_\alpha)^m\to\mathcal P(V_\alpha)$ induced by a fixed first-order definable pairing function on $V_\alpha$ for every ordinal $\alpha$, we may replace finitely many second-order variables by one coded second-order variable. Thus we may write $\varphi \equiv \forall X\,\theta(X,\dot A)$, where $X$ is a unary second-order variable and $\theta$ is a first-order formula in the language $\{\in,\dot A,\dot X\}$. The coding is absolute under relativization to $V_\alpha$, because all quantifiers defining tuple membership in the code are first-order bounded to the current ambient $V_\alpha$. For each ordinal $\alpha\leq \kappa$ and each $B\subset V_\alpha$, write $M_\alpha(A,B) := (V_\alpha,\in,A\cap V_\alpha,B)$. Then $M_\alpha(A,B)\models \theta^\alpha(B,A\cap V_\alpha)$ means that all first-order quantifiers in $\theta$ are interpreted over $V_\alpha$. We shall use the following standard coding fact: because $\kappa$ is inaccessible, for every $\alpha<\kappa$ the set $V_\alpha$ has cardinality $<\kappa$, and hence $\mathcal P(V_\alpha)$ has cardinality $<\kappa$. Thus any level whose elements are subsets of $V_\alpha$, or finite codes built from such subsets, has size $<\kappa$. [/step] [step:Build a $\kappa$-tree from failures of $\Pi^1_1$ reflection] Assume that $\kappa$ has the tree property. We prove $\Pi^1_1$ indescribability by contraposition. Suppose that $(V_\kappa,\in,A)\models\forall X\,\theta(X,\dot A)$ but that no ordinal $\alpha<\kappa$ reflects $\varphi$. Thus for every $\alpha<\kappa$ there exists a subset $B_\alpha\subset V_\alpha$ such that $M_\alpha(A,B_\alpha)\models \neg\theta^\alpha(B_\alpha,A\cap V_\alpha)$. We use the standard weak-compactness counterexample-tree lemma for $\Pi^1_1$ reflection. Applied to the first-order matrix $\theta$, the parameter $A\subset V_\kappa$, and the family of local counterexamples $B_\alpha\subset V_\alpha$, it produces a $\kappa$-tree $\mathcal T$ whose nodes are coherent finite-rank approximation systems to possible counterexamples. A node of height $\alpha$ records, using the fixed tuple-coding relations, a predicate approximation on every $V_\beta$ for $\beta\leq\alpha$, and the coherence requirement is part of the node definition: if a node has height $\alpha$ and $\beta<\alpha$, then its restriction to height $\beta$ is again a node. The lemma verifies the tree axioms as follows. Nonemptiness of the $\alpha$-th level follows from the assumed existence of a local counterexample at every stage below $\kappa$. The size of each level is $<\kappa$ because its nodes are coded by subsets of $V_\alpha$ and $|\mathcal P(V_\alpha)|<\kappa$ by inaccessibility. The predecessor set of a node of height $\alpha$ consists exactly of its coherent restrictions to heights $\beta<\alpha$, and is therefore well-ordered by restriction with order type $\alpha$. Hence $\mathcal T$ is a genuine $\kappa$-tree. [guided] The point of the construction is to turn local failures of reflection into compatible approximations to one global second-order predicate. A node at level $\alpha$ is not merely an ordinal; it is a candidate subset $B\subset V_\alpha$ witnessing that $\varphi^\alpha$ fails at height $\alpha$. Formally, a node on level $\alpha$ is not just a single predicate $B\subset V_\alpha$. That would be insufficient, because a predicate witnessing failure at height $\alpha$ need not restrict to a witness at every smaller height. Instead, a node is a coherently coded system of approximations through all levels $\beta\leq\alpha$, and coherence is required in the definition: restricting the system from height $\alpha$ to any height $\beta<\alpha$ gives the unique predecessor at height $\beta$. This is the point at which the naive construction would fail. First-order satisfaction with predicate parameters is not downward absolute, so one cannot simply take a witness at height $\alpha$ and assume all of its restrictions are lower witnesses. The counterexample-tree lemma avoids this by building the closure under restriction into the object being ordered. We must check the tree-size condition. The level $\mathcal T_\alpha$ is coded by subsets of $V_\alpha$. Since $\kappa$ is inaccessible, $\kappa$ is strongly inaccessible, so $|V_\alpha|<\kappa$ and $|\mathcal P(V_\alpha)|<\kappa$ for every $\alpha<\kappa$. Therefore $|\mathcal T_\alpha|<\kappa$. The failure of reflection gives nonemptiness of every level. Since predecessors are exactly coherent restrictions, the predecessor set of a height-$\alpha$ node has order type $\alpha$. Hence $\mathcal T$ is a genuine $\kappa$-tree, not merely a proper-class construction. [/guided] [/step] [step:Use a cofinal branch to obtain a global counterexample] By the tree property, the $\kappa$-tree $\mathcal T$ has a cofinal branch $\mathcal B$. Define the global predicate $B_*\subset V_\kappa$ by taking the union of the predicate components along the branch $\mathcal B$. Since $\mathcal B$ is linearly ordered by coherent restriction and has nodes of cofinally many heights below $\kappa$, the restriction of $B_*$ to each branch height is exactly the predicate component coded by the corresponding node. For every branch node of height $\alpha$, the coherent system coded by that node records the local failure of the first-order matrix at height $\alpha$; hence \begin{align*} (V_\alpha,\in,A\cap V_\alpha,B_*\cap V_\alpha)\models \neg\theta^\alpha(B_*\cap V_\alpha,A\cap V_\alpha). \end{align*} We use the first-order reflection theorem for the cumulative hierarchy with finitely many predicate parameters in the following form: if $\psi$ is a first-order formula in the language $\{\in,\dot A,\dot B\}$ and $A,B\subset V_\kappa$, then, because $\kappa$ is regular and inaccessible, the set of ordinals $\alpha<\kappa$ such that truth of $\psi$ in $(V_\kappa,\in,A,B)$ reflects to truth of $\psi^\alpha$ in $(V_\alpha,\in,A\cap V_\alpha,B\cap V_\alpha)$ is closed and unbounded in $\kappa$. Its hypotheses apply here because $\theta$ is first-order and $A,B_*\subset V_\kappa$ are unary predicate parameters. If $(V_\kappa,\in,A,B_*)\models \theta(B_*,A)$, then there is a closed unbounded set of $\alpha<\kappa$ such that \begin{align*} (V_\alpha,\in,A\cap V_\alpha,B_*\cap V_\alpha)\models \theta^\alpha(B_*\cap V_\alpha,A\cap V_\alpha). \end{align*} This club meets the cofinal set of branch levels, contradicting the displayed negation at that common ordinal. Therefore $(V_\kappa,\in,A,B_*)\models \neg\theta(B_*,A)$. But this contradicts $(V_\kappa,\in,A)\models \forall X\,\theta(X,A)$. Hence some $\alpha<\kappa$ reflects $\varphi$, and $\kappa$ is $\Pi^1_1$ indescribable. [/step] [step:Encode a branchless $\kappa$-tree by one predicate] Assume now that $\kappa$ is $\Pi^1_1$ indescribable. Let $T$ be a $\kappa$-tree. We show that $T$ has a cofinal branch. First replace $T$ by an isomorphic tree whose nodes are rank-bounded codes. For each $\beta<\kappa$, choose an ordinal $\rho(\beta)<\kappa$ such that $|V_{\rho(\beta)}|\geq |T_\beta|$ and $\beta<\rho(\beta)$. This is possible because $\kappa$ is inaccessible, so the cardinalities $|V_\gamma|$ for $\gamma<\kappa$ are cofinal in $\kappa$. Recursively thin the coding ordinals so that $\rho(\beta)<\rho(\gamma)$ whenever $\beta<\gamma$, and choose injections $e_\beta:T_\beta\to V_{\rho(\beta)}$. Replacing each node $t\in T_\beta$ by the pair-coded object $(\beta,e_\beta(t))$, and replacing the order relation by its transported copy, gives an isomorphic $\kappa$-tree whose level-$\beta$ nodes all lie in $V_{\rho(\beta)+1}$. The predicate code below records the level coordinate explicitly, so reflected initial segments decode exactly the levels whose coded ranks are present. Fix a rank-respecting code $A_T\subset V_\kappa$ for the structure $(T,<_{T},\ell_T)$, where $<_{T}$ is the tree order and $\ell_T:T\to\kappa$ is the level map. The predicate $A_T$ codes the domain, order relation, and level relation by a fixed first-order definable tuple-coding relation on $V_\kappa$. The code is chosen so that, for every $\alpha<\kappa$, the predicate $A_T\cap V_\alpha$ decodes exactly $T{\upharpoonright}\alpha$ with its inherited order and level map. There is a first-order formula $\operatorname{TreeCode}(\dot A)$ saying that $\dot A$ decodes a domain $D$, an order relation $<_{D}$, and a level relation whose levels are indexed by the ambient ordinals, such that every ambient level is nonempty, every level is a set in the ambient universe, and every predecessor set is well-ordered by $<_{D}$ with the prescribed order type. There is also a first-order formula $\operatorname{Branch}(\dot B,\dot A)$ saying that the second-order predicate $\dot B$ is a subset of the decoded domain, is linearly ordered by the decoded tree order, and meets every decoded level of ambient height. The formula $\operatorname{Branch}$ is first-order once the predicate variables $\dot A$ and $\dot B$ are supplied; in the relativized structure $(V_\alpha,\in,A_T\cap V_\alpha)$, the second-order quantifier $\forall B$ ranges over all subsets $B\subset V_\alpha$. Hence the assertion $\operatorname{TreeCode}(\dot A)\wedge \forall B\,\neg\operatorname{Branch}(B,\dot A)$ is a $\Pi^1_1$ sentence. If $T$ had no cofinal branch, then $(V_\kappa,\in,A_T)\models \operatorname{TreeCode}(\dot A)\wedge \forall B\,\neg\operatorname{Branch}(B,\dot A)$. By $\Pi^1_1$ indescribability, there is an ordinal $\alpha<\kappa$ such that $(V_\alpha,\in,A_T\cap V_\alpha)\models \operatorname{TreeCode}(\dot A)^\alpha\wedge \forall B\,\neg\operatorname{Branch}(B,\dot A)^\alpha$. Thus $A_T\cap V_\alpha$ decodes the initial tree $T{\upharpoonright}\alpha$ and asserts that this initial tree has no branch meeting every level below $\alpha$. [/step] [step:Derive a reflected branch from a node at the reflected height] Because $T$ is a $\kappa$-tree, level $\alpha$ of $T$ is nonempty. Choose a node $t\in T$ with $\ell_T(t)=\alpha$. Define $b_t:=\{s\in T:s<_{T}t\}$. The set $b_t$ is linearly ordered by $<_{T}$, and for each $\beta<\alpha$ it contains exactly one node on level $\beta$, because the predecessors of a node in a tree are well-ordered by height. Therefore $b_t$ is a branch through $T{\upharpoonright}\alpha$ meeting every level below $\alpha$. By the rank-respecting choice of the code, every node of $T{\upharpoonright}\alpha$ is an element of $V_\alpha$, so $b_t\subset V_\alpha$. We do not need $b_t$ itself to be an element of $V_\alpha$; under full second-order semantics it is an admissible interpretation of the second-order predicate $B$, because the second-order quantifiers over $(V_\alpha,\in,A_T\cap V_\alpha)$ range over $\mathcal P(V_\alpha)$. Hence $(V_\alpha,\in,A_T\cap V_\alpha)\models \operatorname{Branch}(b_t,A_T\cap V_\alpha)^\alpha$. This contradicts the reflected assertion $(V_\alpha,\in,A_T\cap V_\alpha)\models \forall B\,\neg\operatorname{Branch}(B,\dot A)^\alpha$. Thus the assumption that $T$ has no cofinal branch is impossible. Every $\kappa$-tree has a cofinal branch, so $\kappa$ is weakly compact. [/step] [step:Conclude the equivalence] We have shown that the tree property for $\kappa$ implies $\Pi^1_1$ indescribability, and that $\Pi^1_1$ indescribability implies that every $\kappa$-tree has a cofinal branch. Since weak compactness was defined here as inaccessibility together with the tree property, and $\kappa$ was assumed inaccessible throughout, the two stated conditions are equivalent. [/step]