Ranking theories via encoded $\beta$-models

This paper introduces a well-founded ranking of arbitrary theories based on the encoding power of their $\beta$-models, establishing that while every theory has a countable rank, the ranks of $\mathcal{L}_\in$ and $\mathcal{L}_2$ theories are cofinal in $\omega_1$, with the supremum of ranks for finitely axiomatized theories being $\delta^1_2$.

The Gist

Imagine you are trying to organize a massive library of rulebooks. Some rulebooks are simple, like a set of instructions for a board game. Others are incredibly complex, like the rulebooks for the entire universe of mathematics.

In the world of logic, mathematicians have long tried to rank these rulebooks (called "theories") by how "strong" they are. Usually, they do this by asking: "If I believe Rulebook A, can I prove that Rulebook B isn't broken?" This method is messy; it's like trying to sort a pile of tangled headphones. It doesn't create a clean line from weakest to strongest.

This paper introduces a new, much cleaner way to sort these rulebooks. Instead of just asking about proofs, the authors look at models. Think of a "model" as a working simulation or a miniature universe that follows the rules of a specific book.

Here is the simple breakdown of their new ranking system:

1. The New Rule: "The Nested Universe"

The authors introduce a concept called a $\beta$-model. You can think of a $\beta$-model as a "perfect" simulation. It's a universe that doesn't have any hidden glitches or fake numbers; it sees the world exactly as it truly is.

Their new ranking rule, called $<_{\beta}$, works like this:

• Theory A is "weaker" than Theory B if every perfect simulation of Theory B contains a tiny, coded copy of a perfect simulation of Theory A.

The Analogy:
Imagine Theory B is a giant, high-tech spaceship. Inside that spaceship, there is a small, fully functional toy car (Theory A).

• If every time you build a spaceship of Type B, you can find a toy car of Type A inside it, then Type A is "weaker" than Type B.
• If you can build a spaceship of Type B that doesn't have a toy car of Type A inside it, then Type B isn't necessarily stronger than A in this specific way.

2. Why This is a Big Deal

The authors discovered something surprising: This new ranking system is perfectly organized.

• The old way of ranking (based on consistency) is like a messy pile where you can find loops (A is stronger than B, B is stronger than C, but C is stronger than A).
• This new way ($<_{\beta}$) is like a straight ladder. You can never go in a circle. There is always a clear "bottom" and a clear "top." If you keep climbing up the ladder of stronger theories, you will eventually reach a limit.

3. How High Does the Ladder Go?

The paper calculates exactly how tall this ladder is.

• For all theories: The ladder goes up to a height called $\omega_1$. In simple terms, this is the first "infinite" step that you can't reach by just counting 1, 2, 3... forever. It's the ceiling for any theory that has a perfect simulation.
• For simple, finite theories: If you look only at theories that can be written down with a finite number of rules (or rules that a computer could generate), the ladder stops at a specific, very high point called $\delta^1_2$. This is a specific type of infinite number that represents the limit of what can be defined using certain logical tools.

4. What About Specific Theories?

The authors didn't just build the ladder; they placed specific, famous rulebooks on it to see where they land:

• ATR0 (a standard system for arithmetic) is at the very bottom (Rank 0).
• $\Pi^1_1$-CA0 (a stronger system) is at Rank $\omega$ (the first infinite step).
• KPi (a set theory about "admissible" sets) lands at the "least recursively inaccessible ordinal." Think of this as a very high, special rung that requires a specific kind of mathematical "power" to reach.
• ZF$^-$ (a version of standard set theory without the "Power Set" axiom) lands at the "least gap ordinal," another specific high rung.

5. The "V = L" Twist

The paper also looks at what happens if we add a specific rule to our universe: "Everything is constructible" (V = L).

• Without this rule, the ladder goes up to the standard infinite ceiling ($\omega_1$).
• With this rule, the ladder is shorter. It only goes up to $\omega_1^L$ (the "constructible" version of infinity). It's like building the ladder inside a smaller, more restricted room; you can't reach as high, but the structure is still perfectly straight.

Summary

The authors have created a new, perfectly straight ladder to rank mathematical theories based on how many "perfect simulations" one theory can hide inside another.

• The Ladder is Straight: No loops, no confusion.
• The Ceiling is Known: For all theories, the top is $\omega_1$. For simple theories, the top is $\delta^1_2$.
• The Map is Complete: They have calculated exactly where major mathematical theories sit on this ladder.

This gives logicians a precise, unambiguous way to say, "Theory X is strictly stronger than Theory Y," based on the ability of one to contain the other in a perfect simulation.

Technical Summary

Technical Summary: Ranking Theories via Encoded $\beta$-Models

1. Problem Statement
The paper addresses the challenge of ranking mathematical theories according to their strength. While relative consistency strength is a standard metric, it often yields an ill-founded, non-linear order. Although restrictions to "natural" theories often produce well-ordered hierarchies, the authors seek a more robust, semantic foundation for this ordering that applies to arbitrary (not necessarily recursively axiomatized) theories. The specific goal is to define a well-founded hierarchy based on the existence of well-founded models (specifically $\beta$-models) rather than syntactic proofs of consistency.

2. Methodology and Definitions
The authors introduce a new ranking relation, denoted $<_{\beta}$, defined via the encoding power of $\beta$-models.

• $\beta$-Models: An $L_2$ $\beta$-model is an $\omega$-model of second-order arithmetic that is $\Sigma^1_1$-absolute (i.e., it correctly decides all $\Sigma^1_1$ sentences with parameters from the model). For set theory, a $\beta$-model is a well-founded model.
• Encoding: For countable $\beta$-models $M$ and $N$, $N \dot{\in} M$ denotes that $N$ is encoded within $M$.
• The Ranking Relation: For theories $S, T$ extending a base theory $T_0$ (such as $ATR_0$ or $PRS + \text{Beta}$), $S <_{\beta} T$ if for every $\beta$-model $M$ of $T$, there exists a $\beta$-model $N \dot{\in} M$ such that $N \models S$.
• Well-Foundedness: The paper establishes that the restriction of $<_{\beta}$ to theories possessing $\beta$-models is well-founded. This is proven by showing that an infinite descending chain of theories would imply an infinite descending chain of $\beta$-models under the encoded membership relation, which is impossible.
• Equivalence of Frameworks: The authors demonstrate that this ranking is robust across different formalisms. The $\beta$-rank for second-order arithmetic theories is equivalent to the $\beta$-rank for their set-theoretic counterparts (via bi-interpretations between $ATR_0$ and $ATR^{set}_0$). Furthermore, using transitive models instead of well-founded models yields the same ranking.

3. Key Contributions and Results

• Countability of Ranks: The authors prove that for any theory $T$ with a $\beta$-model, its $\beta$-rank is strictly less than $\omega_1$. This holds even for theories that are not recursively axiomatized. The proof relies on the fact that the rank of a theory is bounded by the rank of its transitive models, and any countable transitive model contains only countably many transitive sub-models.
• Supremum for General Extensions: The supremum of the $\beta$-ranks of all extensions of $ATR_0$ is exactly $\omega_1$. This is established by showing that the ranks are cofinal in $\omega_1$ for theories extending $Z^{set}_2$ (the set-theoretic version of full second-order arithmetic), utilizing forcing techniques to encode reals into the structure of constructibility degrees.
• Supremum for $V=L$ Theories: For theories extending $PRS + \text{Beta} + (V=L)$, the supremum of the $\beta$-ranks is $\omega_1^L$ (the first uncountable ordinal in the constructible universe). The authors provide two proofs for this: one using the uncountability of the set of theories of $L_\alpha$ within $L$, and a second, more effective proof involving limit admissibles and definability.
• Ranks of Effectively Definable Theories: The paper characterizes the ranks of recursively axiomatized and finitely axiomatized theories.
  • The supremum of the $\beta$-ranks for finitely axiomatized, recursively axiomatized, or $\Sigma^1_2$-singleton extensions of a recursive base theory $T_0$ (where $H_{\omega_1} \models T_0$) is exactly $\delta^1_2$.
  • $\delta^1_2$ is defined as the supremum of the order-types of $\Delta^1_2$-definable well-orderings of $\omega$.
  • The authors construct specific theories $T_\alpha$ for $\alpha < \delta^1_2$ using $\Sigma^1$-definitions of ordinals to demonstrate that the ranks reach arbitrarily high below $\delta^1_2$.
• Calculations for Specific Theories: The authors calculate the precise $\beta$-ranks for several systems of interest:
  • $|ATR_0|_{\beta} = 0$
  • $|ATR_0 + \Pi^1_1\text{-}CA^-_0|_{\beta} = 1$
  • $|\Pi^1_1\text{-}CA_0|_{\beta} = \omega$
  • $|KPi|_{\beta}$ equals the least recursively inaccessible ordinal.
  • $|\Pi^1_2\text{-}CA_0|_{\beta}$ equals the least non-projectible ordinal.
  • $|ZF^-|_{\beta}$ equals the least gap ordinal.

4. Significance
The paper claims that the $<_{\beta}$ ordering provides a well-founded hierarchy that mirrors the behavior of consistency strength on "natural" theories but applies to a much broader class of theories, including those that are not recursively axiomatized. By shifting the focus from syntactic consistency proofs to the semantic existence of well-founded models, the authors establish a rigorous framework for comparing the strength of arbitrary theories. The results delineate the precise boundaries of this hierarchy: $\omega_1$ for general extensions of $ATR_0$, $\omega_1^L$ for $V=L$ extensions, and $\delta^1_2$ for effectively definable theories. This work bridges the gap between the ill-founded nature of general consistency strength and the well-ordered nature observed in natural hierarchies, offering a semantic analogue to Gödel's second incompleteness theorem.