Predicativism:

a reverse-mathematical perspective

Stephen G. Simpson Department of Mathematics

Vanderbilt University http://www.math.psu.edu/simpson

sgslogic@gmail.com

Das Kontinuum – 100 Years Later

Leeds, UK September 11–14, 2018 Foundations of mathematics is the study of the basic concepts and logical structure of mathematics as a whole.

Many central problems in foundations of mathematics arise from questions about the notion of “infinity.” Let us focus on three foundational doctrines: finitism, predicativism, and impredicativism.

• Finitism says that the natural number system ℕ exists only as a potential infinity ;

• Predicativism says that ℕ exists as an actual infinity ;

• Impredicativism says that not only ℕ but also many other actual infinities exist.

These doctrines can be formalized in terms of various axiom systems.

Reverse mathematics is a program of foundationally-inspired research which focuses on questions of the following type.

Which axioms are needed in order to prove specific theorems in core mathematical subjects ?

(Some examples of core mathematical subjects are: analysis, algebra, geometry, topology, differential equations, combinatorics.)

Reverse mathematicians have uncovered definitive answers to many questions of this type. These results have specific implications for doctrines such as finitism, predicativism, and impredicativism.

Reverse mathematics takes place in the Gödel hierarchy. Almost all reverse-mathematical research involves a particular family of formal systems, namely, subsystems of second-order arithmetic . Five particular subsystems of Z_{2} have played a large role: RCA_{0}, WKL_{0}, ACA_{0}, ATR_{0}, Π_{1}^{1}-CA_{0}. These are known as “The Big Five.”

The Gödel hierarchy for reverse mathematics

“strong” { ⋮ huge cardinal numbers ⋮ ineffable cardinal numbers ⋮ ZFC (Zermelo/Fraenkel set theory) ZC (Zermelo set theory) simple type theory

“medium” { Z_{2} (second-order arithmetic) ⋮ Π_{2}^{1}-CA_{0} (Π_{2}^{1} comprehension) Π_{1}^{1}-CA_{0} (Π_{1}^{1} comprehension) ATR_{0} (arithmetical transfinite recursion) ACA_{0} (arithmetical comprehension)

“weak” { WKL_{0} (weak König’s lemma) RCA_{0} (recursive comprehension) PRA (primitive recursive arithmetic) EFA (elementary function arithmetic) bounded arithmetic ⋮

The reverse-mathematical perspective:

• finitism is embodied by PRA, RCA_{0}, and WKL_{0};

• predicativism is embodied by ACA_{0} and IR and ATR_{0};

• impredicativism is embodied by Π_{1}^{1}-CA_{0} and stronger systems.

Details:

PRA embodies the outer limits of finitistic reasoning (Tait 1981).

RCA_{0} and WKL_{0} are not finitistic , but they are finitistically reducible in the following sense: RCA_{0} is Π_{2}^{0}-conservative over PRA (Parsons 1970), and WKL_{0} is Π_{1}^{1}-conservative over RCA_{0} (Harrington 1977).

ACA_{0} is necessary and sufficient for the development of predicative analysis, following Weyl’s monograph Das Kontinuum. Proof-theoretically, ACA_{0} is much stronger than WKL_{0}. The first-order part of ACA_{0} is PA = Z_{1} = first-order arithmetic.

Inspired by Poincaré and Weyl, Feferman 1964 developed a formal system IR which embodies the outer limits of predicative reasoning. Proof-theoretically, IR is much stronger than ACA_{0}.

ATR_{0} is not predicative , but it is predicatively reducible in the following sense: ATR_{0} is Π_{1}^{1}-conservative over IR (FMS 1982).

Reverse mathematics for WKL_{0}.

WKL_{0} is equivalent over RCA_{0} to each of the following statements:

1. The Heine/Borel Covering Lemma: Every covering of [0, 1] by a sequence of open intervals has a finite subcovering.

2. Every covering of a compact metric space by a sequence of open sets has a finite subcovering.

3. Every continuous real-valued function on [0, 1] (or on any compact metric space) is bounded (unif. continuous, Riemann integrable).

6. The Maximum Principle: Every continuous r.-v. function on [0, 1] (or on any compact metric space) has (or attains) a supremum.

7. The local existence theorem for solutions of (finite systems of) ordinary differential equations.

8. Gödel Completeness Theorem: Every finite (or countable) consistent set of sentences in the predicate calculus has a countable model.

9. Gödel Compactness Theorem for countable sets of sentences in propositional calculus.

Reverse mathematics for WKL_{0}, continued.

10. Every countable commutative ring has a prime ideal.

11. Every countable field (of characteristic 0) has a unique algebraic closure.

12. Every countable formally real field is orderable.

13. Every countable formally real field has a (unique) real closure.

14. The Brouwer Fixed Point Theorem.

15. The Schauder Fixed Point Theorem for separable Banach spaces.

16. The Hahn-Banach Theorem for separable Banach spaces.

A remark on Hilbert’s Program of finitistic reductionism. There are many true mathematical statements which fail recursively, in the sense that we can construct “recursive counterexamples.” These statements are not provable in RCA_{0}, because RCA_{0} is recursively true. However, many of these statements are provable in WKL_{0}, and WKL_{0} is Π_{1}^{1}-conservative over RCA_{0}, hence Π_{2}^{0}-conservative over PRA. Thus we have a partial realization of Hilbert’s Program of finitistic reductionism .

Another remark on Hilbert’s Program of finitistic reductionism.

Recently Ludovic Patey and Keita Yokoyama solved a fascinating and long-standing open problem.

Namely, they calibrated the proof-theoretical strength of RT(2, 2) = Ramsey’s Theorem for 2-colorings of pairs .

For any set X, let [X]^{2} be the set of all 2-element subsets of X. RT(2, 2) says that for any 2-coloring [ℕ]^{2} = C_{1} ∪ C_{2}, there exists an infinite set X ⊆ ℕ such that [X]^{2} ⊆ C_{1} or [X]^{2} ⊆ C_{2}.

Patey and Yokoyama showed that WKL_{0} + RT(2, 2) is Π_{3}^{0}-conservative over RCA_{0}, hence Π_{2}^{0}-conservative over PRA. Thus we can say that RT(2, 2), like WKL_{0}, is finitistically reducible à la Hilbert’s Program.

It remains open whether WKL_{0} + RT(2, 2) is Π_{1}^{1}-conservative over RCA_{0}.

Now, after this finitistic digression, we return to predicativism.

Reverse mathematics for ACA_{0}. ACA_{0} is equivalent over RCA_{0} to each of the following statements:

1. Every bounded, or bounded increasing, sequence of real numbers has a least upper bound.

2. The Bolzano/Weierstraß Theorem: Every bounded sequence of real numbers, or of points in ℝ^{d}, has a convergent subsequence.

3. Every sequence of points in a compact metric space has a convergent subsequence.

4. The Ascoli Lemma: Every bounded equicontinuous sequence of real-valued continuous functions on a bounded interval has a uniformly convergent subsequence.

5. Every countable commutative ring has a maximal ideal.

6. Every countable vector space over ℚ, or over any countable field, has a basis.

7. Every countable field (of characteristic 0) has a transcendence basis.

8. Every countable Abelian group has a unique divisible closure.

9. König’s Lemma for finitely branching trees.

10. Ramsey’s Theorem for colorings of [ℕ]^{3}, or of [ℕ]^{4}, [ℕ]^{5}, ….

An open problem concerning ACA_{0}.

For any set X ⊆ ℕ, let FS(X) = the set of all sums of nonempty finite subsets of X. Hindman’s Theorem says the following. Given a k-coloring ℕ = C_{1} ∪ ⋯ ∪ C_{k}, there exists an infinite set X ⊆ ℕ such that FS(X) ⊆ C_{i} for some i.

Reverse-mathematically, it is known that Hindman’s Theorem lies somewhere between ACA_{0} and a slightly stronger system ACA0^{+} (BHS 1987). A fascinating and long-standing open problem is to learn whether Hindman’s Theorem is provable in ACA_{0}.

There are at least four known proofs of Hindman’s Theorem. So far as we know, the only proof that is formalizable in ACA0^{+} is the least elegant one. The most elegant one uses idempotent ultrafilters. Recently Montalbán and Shore did a reverse-mathematical study of the ultrafilter proof, but they did not answer the ACA_{0} problem.

Reverse Mathematics for ATR_{0}. ATR_{0} is equivalent over RCA_{0} to each of the following statements:

1. Any two countable well orderings are comparable.

2. Ulm’s Theorem: Every countable reduced Abelian p-group is characterized up to isomorphism by its Ulm invariants.

3. The Perfect Set Theorem: Every uncountable closed, or analytic, set has a perfect subset.

4. Lusin’s Separation Theorem: Any two disjoint analytic sets can be separated by a Borel set.

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

6. Every clopen (or open) game in ℕ^{ℕ} is determined.

7. Ramsey’s Theorem for clopen (or closed) 2-colorings of [ℕ]^{∞}.

8. Podewski-Steffens Theorem: Given a countable bipartite graph, there exist a matching M and a vertex covering C such that C consists of exactly one vertex from each edge of M.

A remark on predicative reductionism.

All of the above statements are impredicative , because they are not provable in IR. (E.g., they are false in the ω-model of IR consisting of the hyperarithmetical hierarchy up to Γ_{0}.) However, all of these statements are provable in ATR_{0}, and ATR_{0} is Π_{1}^{1}-conservative over IR. Thus we have a partial realization of a program of predicative reductionism .

An open problem concerning ATR_{0}.

According to a 1948 conjecture of Fraïssé, the set of all countable linear orderings under embeddability form a well-quasi-ordering, i.e., there is no infinite descending chain and no infinite antichain. Fraïssé’s Conjecture is now a theorem, proved by Richard Laver in 1971. The reverse-mathematical status of Fraïssé’s Conjecture is a fascinating and long-standing open problem. It is known that Fraïssé’s Conjecture implies ATR_{0}. It is open whether Fraïssé’s Conjecture is provable in ATR_{0}. Recently Montalbán made dramatic progress by showing that Fraïssé’s Conjecture is strictly weaker than Π_{1}^{1}-CA_{0}.

Reverse Mathematics for Π_{1}^{1}-CA_{0}. Π_{1}^{1}-CA_{0} is equivalent over RCA_{0} to each of the following statements:

1. Every tree has a largest perfect subtree.

2. The Cantor/Bendixson Theorem: Every closed subset of ℝ, or of any complete separable metric space, is the union of a countable set and a perfect set.

3. Every countable Abelian group is the direct sum of a divisible group and a reduced group.

4. Every difference of two open sets in the Baire space ℕ^{ℕ} is determined.

5. Ramsey’s Theorem for G_{δ} subsets of [ℕ]^{∞}.

References.

Andreas Blass, Jeffry L. Hirst, and Stephen G. Simpson, Logical analysis of some theorems of combinatorics and topological dynamics, in: Logic and Combinatorics (S. G. Simpson, editor), American Mathematical Society, Contemporary Mathematics, 65, 1987, 125–156. Solomon Feferman, Systems of predicative analysis, Journal of Symbolic Logic, I, 29, 1964, 1–30, and II, 33, 1968, 193–220. Harvey Friedman, Kenneth McAloon, and Stephen G. Simpson, A finite combinatorial principle which is equivalent to the 1-consistency of predicative analysis, in: Patras Logic Symposion (G. Metakides, editor), North-Holland, 1982, 197–230. Richard Laver, On Fraïssé’s order type conjecture, Annals of Mathematics, 93, 1971, 89–111. Antonio Montalbán, Fraïssé’s conjecture in Π_{1}^{1}-comprehension, 2016, 9 pages, to appear in Journal of Mathematical Logic. Antonio Montalbán and Richard A. Shore, Conservativity of ultrafilters over subsystems of second order arithmetic, Journal of Symbolic Logic, 83, 2018, 740–765. Ludovic Patey and Keita Yokoyama, The proof-theoretic strength of Ramsey’s theorem for pairs and two colors, Advances in Mathematics, 330, 2018, 1034–1070. Stephen G. Simpson, Partial realizations of Hilbert’s Program, Journal of Symbolic Logic, 53, 1988, 349–363. Stephen G. Simpson, Predicativity: the outer limits, in: Reflections on the Foundations of Mathematics: Essays in Honor of Solomon Feferman (W. Sieg, R. Sommer, and C. Talcott, editors), Association for Symbolic Logic, 2002, 134–140. Stephen G. Simpson, Subsystems of Second Order Arithmetic, 2nd edition, Association for Symbolic Logic, Cambridge University Press, 2009, XVI + 444 pages. Stephen G. Simpson, The Gödel hierarchy and reverse mathematics, in: Kurt Gödel: Essays for his Centennial (S. Feferman, C. Parsons, and S. G. Simpson, editors), Association for Symbolic Logic, Cambridge University Press, 2010, 109–127. Stephen G. Simpson, Foundations of mathematics: an optimistic message, 2016, 11 pages, to appear. Hermann Weyl, Das Kontinuum: Kritische Untersuchungen über die Grundlagen der Analysis, Veit, Leipzig, 1918, IV + 84 pages.