Reverse Mathematics and Π_{2}^{1} Comprehension

Stephen G. Simpson

Pennsylvania State University

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

Logic Colloquium Department of Mathematics

University of Florida November 17, 2006 Two books on reverse mathematics, a status report:

1. RM2001

S. G. Simpson, editor Reverse Mathematics 2001 (a volume of papers by various authors) Volume 21, Lecture Notes in Logic Association for Symbolic Logic VIII + 401 pages, 2005

2. SOSOA

Stephen G. Simpson Subsystems of Second Order Arithmetic Second Edition Volume 1, Perspectives in Logic Association for Symbolic Logic approximately 460 pages, in press Remark:

This talk represents joint work with Carl Mummert, my recent Ph.D. student at the Pennsylvania State University.

Background:

In my book SOSOA, a complete separable metric space is defined as the completion X = (Â, d̂) of a countable pseudometric space (A, d). Here A ⊆ ℕ and d : A × A → ℝ.

Thus complete separable metric spaces are “coded” by countable objects. Using this coding, a great deal of analysis and geometry is developed in RCA_{0}, with many reverse mathematics results.

A conceptual difficulty:

Before Mummert/Simpson, there was no reverse mathematics study of general topology.

The obstacle was, there was no way to discuss abstract topological spaces in L_{2}, the language of second order arithmetic. This was the case even for topological spaces which are separable or second countable.

The solution:

We overcome this obstacle by introducing a restricted class of topological spaces, called countably based MF spaces.

This class includes all complete separable metric spaces, as well as many nonmetrizable spaces.

Furthermore, this class of spaces can be discussed in L_{2}.

Let P be a poset, i.e., a partially ordered set.

Definition. A filter is a set F ⊆ P such that

1. F is upward closed, i.e., (p ∈ F ∧ q ≥ p) ⇒ q ∈ F.

2. for all p, q ∈ F there exists r ∈ F such that p ≥ r ∧ q ≥ r.

Compare the treatment of forcing in Kunen’s textbook of axiomatic set theory.

Definition. A maximal filter is a filter which is not properly included in any other filter.

By Zorn’s Lemma, every filter is included in a maximal filter.

Definition.

MF(P) = {F | F is a maximal filter on P }.

Definition.

MF(P) = {F | F is a maximal filter on P }.

MF(P) is a topological space with basic open sets

N_{p} = {F | p ∈ F }

for all p ∈ P.

Definition. An MF space is a space of the form MF(P) where P is a poset.

Definition. A countably based MF space is a space of the form MF(P) where P is a countable poset.

Thus, the second countable topological space MF(P) is “coded” by the countable poset P.

Therefore, countably based MF spaces can be defined and discussed in L_{2}. Thus we can do reverse mathematics in the usual setting, subsystems of second order arithmetic.

Characterization problems:

1. To characterize those topological spaces which are homeomorphic to MF spaces.

2. To characterize those topological spaces which are homeomorphic to countably based MF spaces.

The first problem remains unsolved. The second problem has recently been solved by Carl Mummert and Frank Stephan. They are the regular second countable spaces which have the strong Choquet property.

Examples of MF spaces. Many topological spaces are homeomorphic to MF spaces:

• all complete metric spaces.

• all locally compact Hausdorff spaces.

• the weak-star dual of any Banach space.

• any G_{δ} subset of any MF space.

• the Baire space ω^{ω} with the topology generated by the Σ_{1}^{1} sets, i.e., the Gandy/Harrington topology.

The latter is a neat example of a countably based MF space which is Hausdorff but not metrizable. However, the dense open subset {f ∈ ω^{ω} | ω_{1}^{f} = ω_{1}^{CK}} is completely metrizable.

Theorem. Every complete (separable) metric space is homeomorphic to a (countably based) MF space.

Proof (sketch). Let Â be a complete metric space with dense subset A. Let P = A × ℚ^{+} ordered by (a, r) < (b, s) if and only if d(a, b) + r < s. We argue that MF(P) is homeomorphic to X. Given a maximal filter F on P, we claim that inf {r | (a, r) ∈ F } = 0. Suppose the inf is h > 0. Let (a, r) ∈ F be such that h ≤ r < 4h/3. We show that (a, r/3) < (b, s) for all (b, s) ∈ F, contradicting maximality. Given (b, s) ∈ F, let (c, t) ∈ F be such that (c, t) < (a, r) and (c, t) < (b, s). We have h ≤ t < r < 4h/3 and d(a, c) + h ≤ d(a, c) + t < r < 4h/3, hence d(a, c) < h/3, hence d(a, c) + r/3 < d(a, c) + 4h/9 ≤ h/3 + 4h/9 = 7h/9 < t so (a, r/3) < (c, t) < (b, s), proving the claim. Hence F is generated by (a_{0}, r_{0}) > (a_{1}, r_{1}) > ⋯ > (a_{n}, r_{n}) > ⋯ with lim_{n} r_{n} = 0, giving a point of Â.

Metrization theorems:

Urysohn Metrization Theorem. A second countable topological space is metrizable if and only if it is regular. (A topological space is said to be regular if, for every open set U and point x ∈ U, there exists an open set V such that x ∈ V and the closure of V is included in U. See Kelley, General Topology.)

Choquet Metrization Theorem. A topological space is completely metrizable if and only if it is metrizable and has the strong Choquet property. (This is a game-theoretic property which is similar to, but stronger than, the property of Baire. See Kechris, Classical Descriptive Set Theory.)

Theorem. All MF spaces have the strong Choquet property. (See Mummert’s Ph.D. thesis, 2005.)

Metrization theorems, continued.

Combining the above results, we have the following metrization theorem for countably based MF spaces.

MFMT: A countably based MF space is completely metrizable if and only if it is regular.

Note that the statement MFMT can be formalized as a sentence in the language of second order arithmetic.

We study the reverse mathematics of MFMT.

We consider the following subsystems of second order arithmetic.

ACA_{0} = arithmetical comprehension.

Π_{1}^{1}-CA_{0} = Π_{1}^{1} comprehension.

Π_{2}^{1}-CA_{0} = Π_{2}^{1} comprehension.

Remark. The fundamental concepts of the theory of MF spaces can be formalized in ACA_{0}. In particular, it is provable in ACA_{0} that every complete separable metric space is homeomorphic to a countably based MF space.

Theorem. MFMT is equivalent to Π_{2}^{1}-CA_{0}. The equivalence is provable in Π_{1}^{1}-CA_{0}.

We outline the proof of this theorem.

Lemma 1. MFMT is provable in Π_{2}^{1}-CA_{0}.

Proof. Part 1. Assume MF(P) is regular. Use Π_{2}^{1} comprehension to form the set {(p, q) ∈ P × P | N_{p} ⊇ closure of N_{q}}. Use this set as a parameter. Follow Matthias Schröder’s effective adaptation of the original Urysohn argument, to find a metric d_{1} for MF(P). Thus MF(P) is metrizable.

Part 2. Fix a countable dense set A ⊆ MF(P). Use Π_{2}^{1} comprehension to form the sets {(a, r, p) ∈ A × ℚ^{+} × P | B(a, r) ⊆ N_{p}} and {(a, r, p) ∈ A × ℚ^{+} × P | N_{p} ⊆ B(a, r)}, where B(a, r) = {x ∈ MF(P) | d_{1}(a, x) < r}. Using these sets as parameters, construct a G_{δ} set in (Â, d̂_{1}) which has the same points as MF(P) and is homeomorphic to MF(P). It follows that MF(P) is homeomorphic to a complete separable metric space (Â, d̂_{2}).

Note: Choquet’s game-theoretic argument is not formalizable in second order arithmetic. Instead, we argue directly within Π_{2}^{1}-CA_{0}.

Lemma 2. Over Π_{1}^{1}-CA_{0}, MFMT implies Π_{2}^{1} comprehension.

Proof. Let ψ(n, X) be a Π_{1}^{1} formula. Assuming MFMT, we prove the existence of the Σ_{2}^{1} set S = {n | ∃X ψ(n, X)}.

We write ψ(n, X) ≡ ¬ ∃f ∀m R(n, X[m], f[m]) where X[m] = ⟨X(0), …, X(m − 1)⟩ and f[m] = ⟨f(0), …, f(m − 1)⟩. Let P be the countable poset consisting of all (n, X[k], f[k]) such that (∀m ≤ k) R(n, X[m], f[m]), plus all (n, X[k]), partially ordered by:

1. (n, X[k], f[k]) < (n′, X′[k′], f′[k′]) iff n = n′ and X[k] ⊃ X′[k′] and f[k] ⊃ f′[k′].

2. (n, X[k]) < (n′, X′[k′]) iff n = n′ and X[k] ⊃ X′[k′].

3. (n, X[k], f[k]) < (n′, X′[k′]) iff n = n′ and X[k] ⊃ X′[k′].

4. (n, X[k]) < (n′, X′[k′], f′[k′]) never.

The maximal filters on P are of three types:

1. F = {p ∈ P | q ≤ p}, where q is a minimal element of P.

2. F = {(n, X[k], f[k]), (n, X[k]) | k ∈ ℕ}, where n, X, f are such that ∀m R(n, X[m], f[m]) holds.

3. F = {(n, X[k]) | k ∈ ℕ}, where n, X are such that ψ(n, X) holds.

Let C be the closed set in MF(P) consisting of all F of type 3. The complement of C is the open set ⋃_{n∈ℕ} N_{(n,⟨⟩,⟨⟩)}.

By Kondo’s Π_{1}^{1} Uniformization Theorem (provable in Π_{1}^{1}-CA_{0}, SOSOA §VI.2), we may assume that ∀n (∃ at most one X) ψ(n, X). Thus, for each n, C ∩ N_{(n,⟨⟩)} contains at most one point.

Under this assumption, it is straightforward to show that MF(P) is regular.

By MFMT, there is a homeomorphism Φ : MF(P) ≅ Â, where Â is a complete separable metric space. In particular, Φ(C) ⊆ Â is closed, and the open sets Φ(N_{(n,⟨⟩)}) ⊆ Â are arithmetical uniformly in n, using a code of Φ^{−1} as a parameter. Hence by Π_{1}^{1} comprehension we may form the set

S = {n | Φ(C) ∩ Φ(N_{(n,⟨⟩)}) ≠ ∅}
= {n | C ∩ N_{(n,⟨⟩)} ≠ ∅}
= {n | ∃X ψ(n, X)} .

This completes the proof.

Remark. This is the first instance of a core mathematical theorem equivalent to Π_{2}^{1} comprehension. Previous reverse mathematics results within second order arithmetic have involved only weaker set existence axioms.

(However, Heinatsch and Möllerfeld have shown that Π_{2}^{1}-CA_{0} proves the same Π_{1}^{1} sentences as ACA_{0} + <ω-Σ_{2}^{0} determinacy.)

Another result: Theorem. The following are equivalent over ACA_{0}.

1. In any countably based MF space, any uncountable closed set contains a perfect set.

2. ∀X (ℵ_{1}^{L(X)} is countable).

References:

Carl Mummert and Stephen G. Simpson, Reverse mathematics and Π_{2}^{1} comprehension, Bulletin of Symbolic Logic, 11, 2005, 526–533.

Carl Mummert, Ph.D. thesis, On the Reverse Mathematics of General Topology, Pennsylvania State University, 2005, VI + 102 pages.

Carl Mummert, Reverse mathematics of MF spaces, 36 pages, submitted for publication.

Carl Mummert and Frank Stephan, Topological aspects of poset spaces, 25 pages, submitted for publication.

THE END