Potential versus actual infinity:

insights from reverse mathematics

Stephen G. Simpson Pennsylvania State University

http://www.math.psu.edu/simpson/ simpson@math.psu.edu

Annual Logic Lecture

Group in Philosophical and Mathematical Logic

University of Connecticut April 1–3, 2015 Potential infinity versus actual infinity.

An important philosophical distinction:

Definition. A potential infinity is a quantity which is finite but indefinitely large. For instance, when we enumerate the natural numbers as 0, 1, 2, …, n, n + 1, …, the enumeration is finite at any point in time, but it grows indefinitely and without bound. Another example is the enumeration of all finite sequences of 0’s and 1’s.

Definition. An actual infinity is a completed infinite totality. Examples: ℕ, ℝ, C[0, 1], L_{2}[0, 1], etc. Other examples: gods, devils, etc.

Reference: Aristotle, Metaphysics, Books M and N.

Four philosophical positions.

Ultrafinitism: Infinities, both potential and actual, do not exist and are not acceptable in mathematics.

Finitism: Potential infinities exist and are acceptable in mathematics. Actual infinities do not exist and we must limit or eliminate their role in mathematics.

Predicativism: We may accept the natural numbers, but not the real numbers, as a completed infinite totality. Quantification over ℕ is acceptable, but quantification over ℝ, or over the set of all subsets of ℕ, is unacceptable.

Infinitism: Actual infinities of all kinds are welcome in mathematics, so long as they are consistent and intuitively natural.

Of these four positions, the finitist one seems to be the most objective.

Definition. By the real world we mean the real world around us and out there, as grasped by our minds. Objectivity is a relationship between our minds and the real world, wherein we grasp reality.

The real world contains many potential infinities. Examples are: counting, the rotation of the earth about the sun, the human reproduction cycle, division of a piece of metal into smaller pieces, the accumulation of wealth, etc.

However, the real world does not appear to contain any actual infinities. For this reason, actual infinities are suspect.

In order to maintain objectivity in mathematics, it seems necessary to limit the use of actual infinities. We introduce them only as “convenient fictions ,” and use them only in a way which leads to conclusions that are objectively justifiable.

Formal theories corresponding to these positions:

Ultrafinitism: According to Troelstra 1988, “no satisfactory development exists at present,” despite the work of Yesenin-Volpin, Nelson, ….

Finitism: PRA = Primitive Recursive Arithmetic. It includes the scheme of primitive recursion: f(−, 0) = g(−), f(−, n + 1) = h(−, n, f(−, n)). For instance, each of the functions A_{k}(n) for k = 0, 1, 2, … defined by A_{0}(n) = 2n, A_{k+1} (n) = \underbrace{A_{k}A_{k} ⋯ A_{k}}_{n times}(1), is primitive recursive.

For instance, A_{1}(n) = 2^{n}, and A_{2}(n) = 2_{n} = a stack of 2’s of height n. But the Ackermann function A(n) = A_{n}(n) is not primitive recursive.

Predicativism: Weyl’s system, ACA_{0}, Feferman’s system IR.

Infinitism: ZFC, or ZFC + large cardinals.

Solomon Feferman, Systems of predicative analysis I, II, Journal of Symbolic Logic, 29, 1964, 1–30, and 33, 1968, 193–220.

Reverse mathematics.

Reverse mathematics is a very rich and active program of research in the foundations of mathematics.

In reverse mathematics, we study the question of which theorems of core mathematics are provable in which formal systems.

By “core mathematics” we mean various branches of mathematics, including analysis, geometry, algebra, combinatorics, differential equations, etc.

Very often, it turns out that the formal system needed to prove a particular core-mathematical theorem is logically equivalent to the theorem. Moreover, five basic systems arise repeatedly in this way: RCA_{0}, WKL_{0}, ACA_{0}, ATR_{0}, Π_{1}^{1}-CA_{0}. These are known as “the Big Five.”

Reference.

Stephen G. Simpson, Subsystems of Second Order Arithmetic, Springer-Verlag, 1999, XIV + 445 pages. Second edition, Association for Symbolic Logic, 2009, XVI + 444 pages. See especially Chapters II–VI.

Some benchmarks in the Gödel hierarchy:

strong { ⋮ supercompact cardinal ⋮ measurable cardinal ⋮ 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 ⋮

Hilbert’s program: finitistic reductionism. Let S be a formal system for mathematics, e.g., ZFC or Z_{2}. Definition. S is finitistically reducible if all Π_{2}^{0} sentences which are provable in S are provable in PRA. Finitistic reducibility means: if we use S to prove a finitistically meaningful sentence, then that same sentence is provable finitistically. Thus, the non-finitistic part of S can be “eliminated” from the proof. In other words, S is a “convenient fictions.” Also, if S proves a Π_{2}^{0} sentence ∀m ∃n Φ(m, n), then PRA proves ∀m Φ(m, f(m)) for some primitive recursive function f. References.

David Hilbert, Über das Unendliche, Mathematische Annalen, 95, 1926, 161–190. See also the translation in: J. van Heijenoort, editor, From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, Harvard University Press, 1967, 680 pages. Richard Zach, Hilbert’s Program, Stanford Encyclopedia of Philosophy, 2003, http://plato.stanford.edu/entries/hilbert-program/.

Theorem. The following formal systems are finitistically reducible.

1. RCA_{0}.

2. WKL_{0}.

3. WKL_{0} + Σ_{2}^{0}-bounding.

4. WKL_{0}^{+} , which includes a useful version of the Baire category theorem.

References.

William W. Tait, Finitism, Journal of Philosophy, 78, 1981, 524–546. Stephen G. Simpson, Partial realizations of Hilbert’s program, Journal of Symbolic Logic, 53, 1988, 349–363. Douglas K. Brown and Stephen G. Simpson, The Baire category theorem in weak subsystems of second order arithmetic, Journal of Symbolic Logic, 58, 1993, 557–578. Stephen G. Simpson, Subsystems of Second Order Arithmetic, Springer-Verlag, 1999, XIV + 445 pages; 2nd edition, ASL, 2009, XVI + 444 pages, especially Chapter IX. Stephen G. Simpson, Toward objectivity in mathematics, in: Infinity and Truth, edited by C.-T. Chong, Q. Feng, T. A. Slaman, and W. H. Woodin, World Scientific, 2014, 157–169. Stephen G. Simpson, An objective justification for actual infinity?, same volume, 2014, 225–228.

Some formal systems which are not finitistically reducible:

1. IΣ_{2}.

2. RCA_{0} + Σ_{2}^{0}-induction.

3. RCA_{0} + WO (ω^{ω}).

4. ACA_{0} and stronger systems.

Each of these systems proves that the Ackermann function is total, i.e., ∀n ∃j (A(n) = j). They also prove the consistency of PRA, which by Gödel is not provable in PRA. Such statements are finitistically meaningful but not finitistically provable . Therefore, the systems in question are not finitistically reducible.

Remark. Let RT(2, 2) = Ramsey’s Theorem for pairs. It is unknown whether RCA_{0} + RT(2, 2) is finitistically reducible!!!

Reference.

Chi-Tat Chong, Theodore A. Slaman, and Yue Yang, The metamathematics of stable Ramsey’s Theorem for pairs, Journal of the American Mathematical Society, 27, 2014, 863–892.

Predicative reductionism.

Definition. S is predicatively reducible if all Π_{1}^{1} sentences which are provable in S are provable in IR.

Predicative reducibility means: if we use S to prove a predicatively meaningful sentence, then that same sentence is provable predicatively. Thus, the non-predicative part of S can be “eliminated” from the proof. In other words, S is a “convenient fiction.”

Theorem. ACA_{0} and ATR_{0} are predicatively reducible.

This is interesting, because (1) ACA_{0} is strong enough to formalize a great deal of core mathematics, (2) ATR_{0} is even stronger and can formalize a great deal of set theory, including for instance the fact that the Continuum Hypothesis holds for Borel sets.

On the other hand, stronger systems such as Π_{1}^{1}-CA_{0} and beyond are not predicatively reducible. For instance, they prove the consistency of IR, which is certainly not provable in IR.

References:

Hermann Weyl, Das Kontinuum: Kritische Untersuchungen über die Grundlagen der Analysis”, Veit, Leipzig, 1918, IV + 84 pages.

René Baire, Émile Borel, Jacques Hadamard, and Henri Lebesgue, Cinq lettres sur la théorie des ensembles, Bulletin de la Société Mathématique de France, 1905, 33, 261–273.

Solomon Feferman, Systems of predicative analysis, Part I, Journal of Symbolic Logic, 29, 1964, 1–30.

Solomon Feferman, Systems of predicative analysis, Part II, Journal of Symbolic Logic, 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, edited by G. Metakides, North-Holland, Amsterdam, 1982, 197–220.

Stephen G. Simpson, Predicativity: the outer limits, in: Reflections on the Foundations of Mathematics: Essays in Honor of Solomon Feferman, edited by W. Sieg, R. Sommer, and C. Talcott, Lecture Notes in Logic, Volume 15, Association for Symbolic Logic, 2001, 134–140.

Proof-theoretic ordinals. Definition. The proof-theoretic ordinal of S is |S| = the supremum of all ordinals α such that S proves WO (α). Here WO (α) means that α is well ordered. The proof-theoretic ordinals of the Big Five:

|RCA_{0}| = |WKL_{0}| = ω^{ω}.

|ACA_{0}| = ε_{0}.

|ATR_{0}| = Γ_{0}.

|Π_{1}^{1}-CA_{0}| = Ψ_{0}(Ω_{ω}). In every case we have S ⊢ WO (α) for all α < |S|, and S ⊬ WO (|S|). For instance, ACA_{0} ⊬ WO (ε_{0}) and RCA_{0} ⊬ WO (ω^{ω}). Reference.

Subsystems of Second Order Arithmetic, Chapter IX, Section 5.

The objectivity of finitism. Why do I say that finitism is objective? Or at least, more objective than ultrafinitism, predicativism, and infinitism? My viewpoint is informed by a particular philosophical system, Objectivism . It is an integrated philosophical system, covering the major branches of philosophy: metaphysics, epistemology, ethics, aesthetics. We describe only the Objectivist epistemology. The main point is a close relationship between existence (“out there”) and consciousness (“in here”).

The Objectivist epistemology:

1. knowledge: “grasp of an object by means of an active, reality-based process which is chosen by the subject.”

2. objectivity: a specific relationship between exsitence and consciousness.

3. context. All knowledge is contextual and must therefore be integrated into a coherent whole.

4. compartmentalization: a failure of integration (more about this later).

5. logic: “the art of non-contradictory identification.”

6. hierarchy: Concepts are validated by reference to earlier concepts, etc., down to the perceptual roots.

To understand Objectivism, contrast it with two other kinds of philosophies:

intrinsicism and subjectivism .

1. intrinsicism: acknowledges reality but denies the active, volitional role of consciousness. Knowledge is acquired by revelation or intuition.

2. subjectivism: acknowledges consciousness but denies the role of reality. Knowledge is created by an individual or a group.

Objectivism strikes a balance:

“Existence is identity; consciousness is identification.”

Mathematics as part of human knowledge. Compartmentalization in the university environment. Compartmentalization within individuals. The Pennsylvania State University. Lack of integration of mathematics with application areas: physical sciences, earth sciences, social sciences, engineering, etc. Mathematics in public affairs. Philosophy is responsible for integrating human knowledge into a coherent whole. Mathematical modeling. Some philosophical questions.

The unity of mathematics. Specialties within mathematics: geometry, number theory, differential equations, mathematical logic, etc. An antidote: the unity of mathematics. Combinations of specialties: algebraic geometry, geometric analysis, etc. Set theory contributes to the unity of mathematics, by providing a common framework and a common standard of rigor. Namely, ZFC = Zermelo/Fraenkel set theory, including the Axiom of Choice.

Set theory and the unity of mathematics.

1. ZFC as a common framework.

2. ZFC as a standard of rigor.

3. ZFC as a comfortable answer to foundational questions. On the other hand, there are justified qualms:

1. The set-theoretic “multiverse”.

2. Avoidance of higher set theory.

3. There is no clear way to integrate ZFC-based mathematics with the rest of human knowledge.

The unity of mathematics is good, but the unity of human knowledge would be even better.

Critique of set-theoretic realism. Gödel, Martin, Steel, Woodin, Maddy. According to set-theoretic realism, set theory refers to certain aspects of reality. Examples: ℵ_{ω}, the Continuum Hypothesis. A key epistemological question:

How can we acquire knowledge of the set-theoretic reality? We consider three contemporary answers.

A. The intrinsicist answer.

B. The “testable consequences” answer.

C. The Thin Realist answer.

Acquiring knowledge of set-theoretic reality. A. The intrinsicist answer: pure intuition. This seems incompatible with the requirement of objectivity. B. Testable consequences. Example: Diophantine equations. Analogy with the atomic theory of matter. The “testable consequences” answer is different from the intrinsicist answer, because it gives an active role to cognitive processes. The difficulty is in the implementation. E.g., the Diophantine equations are too complicated. Projective determinacy (Woodin, Martin, Steel), Boolean relation theory (Friedman). They are remote from core mathematics and application areas.

C. Thin Realism. This is Maddy’s current view, in contrast to her earlier Robust Realism. She argues that set-theoretic realism is embedded in “the fabric of mathematical fruitfulness.” I have my doubts, as above. Maddy’s analogy:

\frac{large cardinals}{set theory skepticism} = \frac{tables and chairs}{evil daemon theories} .

I propose a competing analogy:

\frac{large cardinals}{set theory skepticism} = \frac{gods and devils}{religious skepticism} .

Thin Realism, continued. The point of my analogy is that both set theory and religious faith can claim to be in a “strong” position vis a vis skeptics, by avoiding reliance on facts which can be questioned. I reject such claims on grounds of lack of objectivity. However, I applaud Maddy for attempting to apply standard scientific criteria. Can this be developed into a full-scale integration of mathematics with the rest of human knowledge?

Insights from reverse mathematics. Reverse mathematics classifies core mathematical theorems according to the set existence axioms needed to prove them. Often the theorem is equivalent to the axiom. Hence the name “reverse mathematics.” A large number of theorems fall into a small number of equivalence classes. The equivalence classes correspond to benchmarks in Gödel’s hierarchy of consistency strength.

Some benchmarks in the Gödel hierarchy:

strong { ⋮ supercompact cardinal ⋮ measurable cardinal ⋮ 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 ⋮

Toward objectivity in mathematics, I see two insights to be drawn from reverse mathematics.

1. The bulk of core mathematical theorems fall at the lowest levels.

This suggests that higher set theory may be largely irrelevant.

2. The lowest levels are conservative over PRA (primitive recursive arithmetic).

This leads to strong partial realizations of Hilbert’s program. A large portion of core mathematics, sufficient for applications, is validated in a finitistically provable way.

These considerations seem to open a path toward objectivity in mathematics.

Wider cultural significance? Historically, are trends in philosophy of mathematics parallel to trends in world culture? Plato and Aristotle. The Renaissance. The Enlightenment. The 19th century. Early 20th century: intuitionism in philosophy of mathematics; subjectivism and collectivism in the wider culture. Late 20th century: set-theoretic realism in philosophy of mathematics; religious fundamentalism in the wider culture.

More References.

Kurt Gödel: Essays for his Centennial, edited by S. Feferman, C. Parsons, and S. G. Simpson, Association for Symbolic Logic, Cambridge University Press, 2010, VIII + 373 pages.

Matthew D. Foreman, Review of papers by Donald A. Martin, John R. Steel, and W. Hugh Woodin, Journal of Symbolic Logic, 57, 1132–1136, 1992.

Penelope Maddy, Second Philosophy: A Naturalistic Method, Oxford University Press, 2007, XII + 448 pages.

Leonard Peikoff, Objectivism: The Philosophy of Ayn Rand, Dutton, New York, 1991, XV + 493 pages.

Stephen G. Simpson, The Gödel hierarchy and reverse mathematics, in the Gödel volume, 2010, 109–127.

Thank you for your attention!