On the hierarchy of natural theories

This paper addresses the mathematical challenge of defining "natural" axiomatic theories to explain their empirical pre-well-ordering by consistency strength, surveying strategies involving reflection principles, ordinal analysis, and recursion theory while highlighting open problems and future research directions.

The Gist

Imagine you are standing in a vast, foggy library. This library contains every possible set of rules (axioms) you could ever write down to do mathematics. Some rules are simple, like "1+1=2." Others are incredibly complex, dealing with infinite sets and the very nature of truth.

For a long time, mathematicians noticed a strange, almost magical pattern in this library. If you pick out the rules that humans actually use in real life—what the author calls "natural" theories—they seem to line up perfectly in a single, straight line from "weakest" to "strongest." You can always say, "Theory A is stronger than Theory B," or "Theory B is stronger than Theory A." They never cross paths, and they never loop back on themselves.

However, if you start inventing weird, artificial rules just to break the system (using logical tricks and self-reference), the line breaks. You get a tangled mess where some rules are incomparable, or you can find an infinite chain of rules getting weaker and weaker forever.

The Big Mystery: Why do the "natural" rules form a perfect ladder, while the "artificial" ones form a chaotic jungle? The problem is, we don't have a dictionary definition for what makes a rule "natural." It's like trying to prove that "all good songs are in the key of C" without being able to define what a "good song" is.

This paper, by James Walsh, tries to solve this mystery by looking at two different worlds of mathematics and seeing how they mirror each other.

1. The Ladder of Truth (Consistency Strength)

Think of a theory's "strength" as how many truths it can prove.

• Weak Theory: Can prove simple math.
• Strong Theory: Can prove simple math plus complex set theory.

The author explains that if you keep adding "I am consistent" (meaning, "I don't contain any contradictions") as a new rule to a theory, you get a stronger theory. You can keep doing this forever, climbing up a ladder.

• The Problem: If you use weird, artificial ways to write down the rules for "I am consistent," you can create a ladder that has gaps, loops, or branches.
• The Miracle: When mathematicians use the "natural" way to write these rules, the ladder is smooth, straight, and never breaks.

2. The Two Worlds: Math Rules vs. Computer Programs

To solve the mystery, the author compares the "Ladder of Math Rules" to the "Ladder of Computer Programs."

World A: The Math Ladder (Proof Theory)

• We have theories like Peano Arithmetic (basic math) and ZFC (set theory).
• They seem to line up perfectly by strength.

World B: The Computer Ladder (Recursion Theory)

• Imagine computer programs that try to solve problems. Some are easy (like checking if a number is even), and some are impossible (like the Halting Problem).
• Mathematicians found that if you look at "natural" computer problems, they also line up perfectly in a ladder of difficulty.
• But if you use weird, artificial tricks to build programs, you get a tangled mess.

The Connection: The author suggests that the reason the Math Ladder is straight is the same reason the Computer Ladder is straight. In both cases, "natural" things are built by stacking simple, reliable steps on top of each other.

3. The "Reflection" Mirror

The paper introduces a powerful tool called Reflection Principles.

• The Analogy: Imagine a mirror. A basic theory looks at the world and sees things. A "reflected" theory looks at the mirror and says, "Everything I see in the mirror is actually true."
• If you keep adding mirrors within mirrors (iterated reflection), you get a stronger and stronger theory.
• The Discovery: The author argues that "natural" mathematical theories are essentially just these mirrors stacked up in a specific order. Because the mirrors are stacked in a logical, natural way, the resulting tower is perfectly straight.

4. The "Pathological" Monsters

Why do the artificial theories break the pattern?

• The Analogy: Imagine you are building a tower of blocks.
  • Natural: You stack them neatly. The tower is straight.
  • Artificial: You use glue to stick a block to the side, or you carve a block to look like two blocks. You create a tower that wobbles, has hidden gaps, or loops back down.
• The paper shows that these "monsters" (artificial theories) rely on specific, weird tricks to exist. If you try to build a "natural" monster, it just turns out to be a normal block in the straight tower.

5. The Solution: Ordinal Analysis

How do we measure the height of these towers?

• Mathematicians use Ordinals (a special kind of number that goes beyond infinity) to measure the height.
• The paper argues that for every "natural" theory, there is a specific "height" (ordinal) it corresponds to.
• Because ordinals are perfectly ordered (1, 2, 3... $\omega$, $\omega+1$...), the theories that correspond to them must also be perfectly ordered.

The Big Picture Conclusion

The paper concludes that the "Great Mystery" of why natural math theories line up so perfectly is likely because natural theories are just different ways of stacking the same fundamental building blocks (reflection principles).

• The "Natural" theories are like a well-organized library where every book is filed in the correct spot.
• The "Artificial" theories are like a library where someone threw books on the floor and glued them together randomly.

The author suggests that if we can define "natural" as "built by stacking these specific reflection mirrors," we can finally prove mathematically why the ladder is straight. We don't need to guess what "natural" means; we just need to look at how the mirrors are stacked.

In short: Nature prefers order. When we build math the way nature does (using standard, honest steps), we get a perfect ladder. When we try to cheat with tricks, we get a mess. This paper proves that the "cheating" is the only thing that breaks the ladder, and the "honest" way always leads to a straight line.

Technical Summary

1. The Problem: The "Great Mystery" of Natural Theories

The paper addresses a central empirical phenomenon in mathematical logic: natural axiomatic theories (those arising in practice, e.g., PA, ZFC, subsystems of analysis) appear to be pre-well-ordered by consistency strength.

• The Phenomenon: If one restricts attention to "natural" theories, the relation $T \leq_{Con} U$ (meaning $U$ proves the consistency of $T$) forms a pre-well-ordering. There are no incomparable natural theories, and no infinite descending chains of natural theories.
• The Obstacle: This phenomenon is contrasted with the general case of all reasonable theories, where the ordering is neither linear nor well-founded (due to ad-hoc constructions using self-reference, Rosser sentences, etc.).
• The Core Issue: The term "natural" lacks a precise mathematical definition. Without a definition of "natural," the claim that these theories are pre-well-ordered cannot be formally proven or even precisely stated. The paper aims to provide a mathematical framework to explain this phenomenon without relying on an ill-defined notion of "naturalness."

2. Methodology and Framework

Walsh employs a multi-pronged approach combining Ordinal Analysis, Iterated Reflection Principles, and Recursion Theory analogies.

• Analogy with Recursion Theory: The paper draws a parallel between the pre-well-ordering of natural theories and the pre-well-ordering of natural Turing degrees. It utilizes Martin's Conjecture (which posits that degree-invariant functions are essentially iterates of the Turing jump) as a guiding heuristic.
• Reflection Principles: Instead of relying solely on consistency statements ($Con(T)$), the paper focuses on uniform reflection principles ($RFN(T)$). These principles assert the soundness of a theory for specific complexity classes (e.g., $\Pi_1$, $\Pi_1^1$).
• Beklemishev's Approach: The methodology builds on Beklemishev's work, which characterizes the proof-theoretic ordinal of a theory via iterations of consistency (or reflection) over a weak base theory (like $EA$).
• Oracle-Based Orderings: To bypass the "pathological" issues of ordinal notation systems (where different notations yield different strengths), the author introduces orderings defined relative to oracles for truth (specifically $\Sigma_1^1$ truth). This abstracts away from the specific presentation of ordinals.

3. Key Contributions and Results

A. Proof-Theoretic Analogues of Martin's Conjecture (Sections 8)

The author formulates and investigates analogues of Martin's Conjecture within proof theory, asking whether "canonical" operators (like consistency) are the only monotone functions that strengthen theories.

• Theorem 8.7 (Walsh 2020): For any recursive, monotone, and bounded function $g$ on sentences, if $g$ is "stronger" than the identity, it must eventually coincide with the consistency operator $Con_T$ on a "true cone" (a large set of true sentences).
  • Significance: This suggests there are no "natural" theories with strength strictly between $T$ and $T + Con(T)$.
• Limitations (Theorems 8.10, 8.12, 8.14):
  • If the monotonicity constraint is relaxed to extensionality, counter-examples exist (Shavrukov-Visser density functions).
  • If the recursiveness constraint is relaxed to limit-recursiveness, functions can oscillate between the identity and consistency, failing to converge.
  • For iterates of consistency ($Con^\alpha$), naive generalizations fail; functions can oscillate between different iterates.
• Positive Results (Theorems 8.15, 8.16): Despite the failures of naive generalizations, if a recursive monotone function $g$ is "bounded" by an iterate of consistency (i.e., $g$ is stronger than $Con^\beta$ but weaker than $Con^\alpha$), then $g$ must coincide with some iterate $Con^\beta$ on a cofinal set of true sentences. This establishes a form of canonicity for iterated consistency operators.

B. Well-Foundedness of Reflection Hierarchies (Section 9)

The paper proves that descending sequences of theories based on reflection principles are impossible under soundness constraints, mirroring Steel's results in recursion theory.

• Theorem 9.3 & 9.6: There are no recursively enumerable (r.e.) descending sequences of $\Sigma_2$-sound (or $\Pi_1^1$-sound) theories where each theory proves the soundness of the next.
  • Contrast: While descending sequences exist for weaker notions (like $\Sigma_1$-soundness or mere consistency), they vanish when requiring higher soundness ($\Sigma_2$ or $\Pi_1^1$).
• Theorem 9.7: Extends this to $\Sigma_1^1$-definable theories, ruling out descending sequences for $\Pi_1^1$-reflection.

C. Vindication of Ordinal Analysis via Oracle Orderings (Section 9.3)

The most significant technical contribution is the definition of orderings that do pre-well-order theories, thereby explaining the "natural" phenomenon.

• New Definitions:
  • $\Gamma$-Provability ($T \vdash_\Gamma \phi$): $T$ proves $\phi$ given an oracle for true $\Gamma$ sentences.
  • $\Gamma$-Reflection Strength ($T \leq_\Gamma^{RFN} U$): $U$ proves the $\Gamma$-reflection of $T$.
  • $\Gamma$-Inclusion ($T \subseteq_\Gamma^\Delta U$): Inclusion of $\Delta$ theorems provable with a $\Gamma$ oracle.
• Theorem 9.16 (Main Result): For $\Pi_1^1$-sound, arithmetically definable extensions of $ACA_0$:
  $$T \subseteq_{\Sigma_1^1}^{\Pi_1^1} U \iff |T|_{WF} \leq |U|_{WF} \iff T \leq_{\Sigma_1^1}^{RFN_{\Pi_1^1}} U$$
  • Here, $|T|_{WF}$ is the proof-theoretic ordinal.
  • Implication: When viewed through the lens of $\Sigma_1^1$ truth (an oracle), the ordering by $\Pi_1^1$-reflection strength, the ordering by $\Pi_1^1$-inclusion, and the ordering by proof-theoretic ordinals coincide and form a pre-well-ordering.

4. Significance and Conclusion

1. Mathematical Explanation of "Naturalness": The paper suggests that the "naturalness" of axiomatic theories is not a mystical property but a consequence of their relationship to iterated reflection principles. Natural theories are those that can be approximated by iterating reflection principles along well-orderings.
2. Resolution of Pathologies: The lack of pre-well-ordering in the general case is attributed to "pathological" ordinal notation systems and ad-hoc definitions. By moving to an oracle-based context (Theorem 9.16), these pathologies disappear, and the pre-well-ordering emerges naturally.
3. Unification of Fields: The work successfully unifies Ordinal Analysis (proof theory) with Recursion Theory (Turing degrees). It shows that just as natural Turing degrees are iterates of the jump, natural theories are iterates of reflection principles.
4. Future Directions: The paper concludes that the search for new axioms in set theory (e.g., large cardinals) is guided by this hierarchy. Since natural theories converge on arithmetic and analytic statements (Steel's observation), the pre-well-ordering provides a rational basis for choosing between competing extensions of set theory.

In summary, Walsh provides a rigorous framework showing that the pre-well-ordering of natural theories is a mathematical reality derived from the canonicity of reflection principles, provided one abstracts away from the specific, often pathological, representations of ordinals.