Predicativity: The Outer Limits

Stephen G. Simpson Department of Mathematics Pennsylvania State University

www.math.psu.edu/simpson

Feferman Symposium Stanford University

December 11–13, 1998 S. Feferman, Systems of Predicative Analysis, J. of Symbolic Logic, 29, 1964, pp. 1–30.

S. Feferman, Systems of Predicative Analysis, II: Representations of Ordinals, J. of Symbolic Logic, 33, 1968, pp. 193–220.

“Although we strongly believe that the explications proposed in this paper for the notion of predicative provability in analysis are correct, we are not convinced that the matter has been settled conclusively by the results obtained so far. It is premature to say just what would constitute final evidence concerning this question. We expect that this will be revealed, at least in part, by further study of the theories considered here.” (page 29)

Subsequent papers do not indicate that Feferman has changed his mind about predicative provability.

S. Feferman, Predicatively reducible systems of set theory, in Axiomatic Set Theory, Proc. Symp. Pure Math. vol. XIII, Part 2, Amer. Math. Soc., Providence, 1974, pp. 11-32.

S. Feferman, A more perspicuous formal system for predicativity, in Konstruktionen versus Positionen, I, Walter de Gruyter, Berlin, 1979, pp. 68–93.

S. Feferman, Reflecting on incompleteness, J. of Symbolic Logic, 56, 1991, pp. 1–49.

Rules versus axioms. Δ_{1}^{1} comprehension rule:

\begin{matrix}∀n ((∃X α(n, X)) ↔ (∀Y β(n, Y))) \\ ∃Z ∀n (n ∈ Z ↔ ∃X α(n, X)) \end{matrix}

Δ_{1}^{1} comprehension axiom:

\begin{matrix}(∀n ((∃X α(n, X)) ↔ (∀Y β(n, Y)))) \\ → ∃Z ∀n (n ∈ Z ↔ ∃X α(n, X)) \end{matrix}

Here α and β are arithmetical formulas.

Rules versus axioms. hierarchy rule:

\begin{matrix}W O(<_{e}) \\ ∀X ∃Y H(<_{e}, X, Y) \end{matrix}

hierarchy axiom:

∀Z (W O(Z) → ∀X ∃Y H(Z, X, Y)) W O(Z): Z is a well ordering. H(Z, X, Y): Y is a Turing jump hierararchy along Z starting at X.

Rules versus axioms.

transfinite induction rule:

W O(<_{e})

T I(<_{e}, γ), γ arbitrary

transfinite induction axiom:

∀Z (W O(Z) → T I(Z, γ)) for arbitrary γ

T I(Z, γ): transfinite induction along Z with respect to the formula γ.

IR consists of the Δ_{1}^{1} comprehension rule + the hierarchy rule + the transfinite induction rule. ATR_{0} consists of the hierarchy axiom. It includes the Δ_{1}^{1} comprehension axiom. It is a system with restricted induction and so does not include the transfinite induction rule. |IR| = |ATR_{0}| = Γ_{0}. IR and ATR_{0} prove the same Π_{1}^{1} sentences. IR and ATR_{0} have the same proof-theoretic strength. THEMES OF THIS TALK:

1. IR explicates predicative provability, while ATR_{0} explicates predicative reducibility.

2. ATR_{0} is much stronger than IR, modeltheoretically and, above all, mathematically.

The minimum ω-model of IR is HYP (Γ_{0}). The minimum ω-model of the Δ_{1}^{1} comprehension axiom is HYP , i.e., L_{ω_{1}^{CK}} ∩ P (ω). HYP is the intersection of all ω-models of ATR_{0}. ATR_{0} has no minimal ω-model. ATR_{0} holds in any β-model. HYP is the intersection of all β-models. There is no minimal β-model.

A set-theoretic version of ATR_{0}.

ATR_{0}^{set} = extensionality

+ foundation axiom:

∀x (x ≠ ∅ → ∃u ∈ x (u ∩ x = ∅)) + closure under F_{0}−F_{8} (rudimentary functions)

+ axiom of infinity

+ ∀x (x is hereditarily countable )

+ axiom beta:

∀r (W F (r) → ∃f (field (r) ⊆ dom (f) ∧ ∀u ∈ dom (f) (f(u) = {f(v) : ⟨v, u⟩ ∈ r}))) .

Theorem (Simpson). ATR_{0}^{set} is conservative over ATR_{0}. Actually, it is a definitional extension of ATR_{0}, where well founded trees encode hereditarily countable sets in the usual way.

Π_{∞}^{1}-TI_{0} consists of the transfinite induction axiom. It includes ATR_{0}. Precisely, Σ_{1}^{1}-TI_{0} = ATR_{0} + Σ_{1}^{1}-IND. Π_{∞}^{1}-TI_{0} is proof-theoretically stronger than IR and ATR_{0}. |Π_{∞}^{1}-TI_{0}| = φ_{ε_{Ω+1}} (0) = the Howard ordinal. Π_{∞}^{1}-TI_{0} has no minimal ω-model. Π_{∞}^{1}-TI_{0} holds in any β-model. HYP is the intersection of all β-models. There is no minimal β-model.

Reverse mathematics of ATR_{0}: The following are equivalent over RCA_{0}.

1. ATR_{0}.

2. Every disjoint pair of analytic sets can be separated by a Borel set.

3. The domain of a single-valued Borel set in the plane is Borel.

4. Every uncountable closed (or analytic) set has a perfect subset.

5. Clopen (or open) determinacy.

6. Clopen (or open) Ramsey theorem.

7. For every countable bipartite graph, there exists a König covering, i.e., a pair (C, M) where C is a vertex covering, M is a matching, and C consists of one vertex of each edge in M.

This is a combined result of Aharoni/Magidor/Shore 1992 and Simpson 1994.

8. Comparability of countable well orderings.

9. Ulm theory for countable reduced Abelian p-groups.

Open questions:

1. Is Fraïssé’s conjecture for countable linear orderings provable in ATR_{0}?

See papers by Marcone 1994 and Shore 1994.

2. A consequence of the Ulm theory:

If each of two countable reduced Abelian p-groups is a direct summand of the other, then they are isomorphic.

Is this statement equivalent to ATR_{0}?

Note: Mathematically, IR seems no stronger than arithmetical comprehension, and Π_{∞}^{1}-TI_{0} no stronger than ATR_{0}.

Aharoni/Magidor/Shore, On the strength of König’s duality theorem for countable bipartite graphs, J. of Combinatorial Theory, series B, 54, 1992, pp. 257–290.

Simpson, same title, J. of Symbolic Logic, 59, 1994, pp. 113–123.

R. Shore, On the strength of Fraïssé’s conjecture, in Logical Methods, Birkhäuser, 1993, pp. 782–813.

A. Marcone, Foundations of BQO theory, Transactions of the AMS, 345, 1994, pp. 641–660.

My book on reverse mathematics is finally out!

Stephen G. Simpson Subsystems of Second Order Arithmetic Perspectives in Mathematical Logic Springer-Verlag, 1998 XIV + 445 pages.

Order: 1-800-SPRINGER.

List price: $60.

Discount: 30 percent for ASL members; mention promotion code S206.

Impredicative Π_{2}^{0} combinatorial theorems.

1. A finite miniaturization (a la Kirby/Paris) of the clopen Ramsey theorem:

Friedman/McAloon/Simpson, A finite combinatorial principle which is equivalent to the 1consistency of predicative analysis, in: Logic Symposion I (Patras), edited by G. Metakides, North-Holland, Amsterdam, 1982, pp. 197– 220.

2. Friedman’s work on Kruskal’s theorem:

Stephen G. Simpson, Nonprovability of certain combinatorial properties of finite trees, in: Harvey Friedman’s Research in the Foundations of Mathematics, North-Holland, Amsterdam, 1985, pp. 87–117.

Definitions.

1. Let X be a finite set of positive integers. A coloring of X is P (X) = C_{1} ∪ C_{2} where C_{1} and C_{2} are closed under initial segment. Y ⊆ X is homogeneous if P (Y) ⊆ C_{1} or P (Y) ⊆ C_{2}.

2. X is 0-dense if |X| ≥ 2 and |X| ≥ min X.

3. X is n + 1-dense if for every coloring of X there exists an n-dense homogeneous set. Theorem (Friedman/McAloon/Simpson).

∀ n ∃ n-dense set ≡ uniform Π_{2}^{0} reflection for IR ≡ uniform Π_{2}^{0} reflection for ATR_{0} 3. A recent result of Friedman:

Definitions. A tree T is a finite poset with a minimum element such that the predecessors of each element are linearly ordered. The height of x ∈ T is the number of predecessors of x in T. The height of T is the maximum height of an element of T. We say that T is of degree ≤ k if each element of T has at most k immediate successors.

T (≤ i) = {x ∈ T : height (x) ≤ i}.

T (i) = {x ∈ T : height (x) = i}.

T (> i) = {x ∈ T : height (x) > i}.

Note that T (≤ i) is a subtree of T.

Consider the following statement.

For each k there exists n so large that the following holds. If T is a tree of height n and degree ≤ k, then there exists 1 ≤ i ≤ n and an inf-preserving embedding of T (≤ i) into T which carries T (i) into T (> i).

Friedman 1998 showed that this statement is equivalent to uniform Π_{2}^{0} reflection for Π_{2}^{1}-TI_{0}.