Baire categoricity and Σ_{1}^{0} induction

Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.math.psu.edu/simpson simpson@math.psu.edu

First draft: February 24, 2012 This draft: October 23, 2013

Abstract

We investigate the reverse-mathematical status of a version of the Baire Category Theorem known as BCT. In a 1993 paper Brown and Simpson showed that BCT is provable in RCA_{0}. We now show that BCT is equivalent to RCA_{0} over RCA∗_{0}.

Keywords: Reverse mathematics, second-order arithmetic, Baire Category Theorem, RCA_{0}, RCA∗_{0}, Σ_{1}^{0} induction.

2010 Mathematics Subject Classification: Primary 03B30; Secondary 03F25, 54E52.

Notre Dame Journal of Formal Logic, 55, 2014, pp. 75–78.

Consider the following version of the Baire Category Theorem.

Definition 1. Let BCT be the statement that, in any complete separable metric space, the intersection of any countable sequence of dense open sets is dense. Thus BCT is essentially the usual statement of the Baire Category Theorem for complete separable metric spaces.

The purpose of this paper is to prove a new result concerning the reversemathematical status of BCT. From Brown/Simpson [1, Theorem 2.1] we already know that BCT is provable in RCA_{0}. Here of course RCA_{0} is the usual base theory for reverse mathematics [6], consisting of Δ_{1}^{0} comprehension plus Σ_{1}^{0} induction. We now prove that BCT is logically equivalent to RCA_{0} over the weaker base theory RCA∗_{0}. The system RCA∗_{0} was first introduced in [7]. Two recent papers making use of RCA∗_{0} are [9] and [11].

In addition to BCT itself, we consider the following special case of BCT.

Definition 2. The Cantor space is the space {0, 1}^{ℕ} of infinite sequences of 0’s and 1’s. We endow {0, 1} with the discrete topology and {0, 1}^{ℕ} with the product topology. Let BCT({0, 1}^{ℕ}) be the statement that BCT holds for the Cantor space.

More precisely, let {0, 1}^{∗} be the set of finite sequences of 0’s and 1’s. For σ ∈ {0, 1}^{∗} and X ∈ {0, 1}^{ℕ} we write σ ⊂ X to mean that σ is an initial segment of X. We also write ⟦σ⟧ = {X ∈ {0, 1}^{ℕ} | σ ⊂ X}. Note that the sets ⟦σ⟧ where σ ∈ {0, 1}^{∗} form a basis for the topology of {0, 1}^{ℕ}. For σ, τ ∈ {0, 1}^{∗} we write σ ⊂ τ to mean that σ is a proper initial segment of τ. We say that D ⊆ {0, 1}^{∗} is dense in {0, 1}^{∗} if for all σ ∈ {0, 1}^{∗} there exists τ ∈ D such that σ ⊂ τ. Thus the dense open sets in {0, 1}^{ℕ} are just the sets of the form ⟦D⟧ = ⋃_{τ∈D}⟦τ⟧ where D is dense in {0, 1}^{∗}. We say that X ∈ {0, 1}^{ℕ} meets D if there exists τ ∈ D such that τ ⊂ X. Within RCA∗_{0} let BCT({0, 1}^{ℕ}) be the statement that for all sequences of dense sets D_{i} ⊆ {0, 1}^{∗}, i ∈ ℕ, and all σ ∈ {0, 1}^{∗} there exists X ∈ {0, 1}^{ℕ} such that σ ⊂ X and X meets D_{i} for each i ∈ ℕ.

Theorem 1. The following are pairwise equivalent over RCA∗_{0}.

1. RCA_{0}.

2. BCT.

3. BCT({0, 1}^{ℕ}).

4. For all finite sequences of dense sets D_{i} ⊆ {0, 1}^{∗}, 1 ≤ i ≤ n, there exists X ∈ {0, 1}^{ℕ} such that X meets D_{i} for each i = 1, …, n.

Proof. We reason in RCA∗_{0}. The implication 1 ⇒ 2 is already known [1, Theorem 2.1]. The implications 2 ⇒ 3 and 3 ⇒ 4 are obvious.

It remains to prove 4 ⇒ 1. For this purpose we use the following lemma from [9]. Within RCA∗_{0} a set C ⊆ ℕ is defined to be infinite if it is not finite, or equivalently, it is unbounded, i.e., ∀n ∃c (n < c ∈ C).

Lemma 1. Over RCA∗_{0} the following are equivalent.

1. RCA_{0}.

2. Each infinite subset of ℕ includes arbitrarily large finite subsets.

Proof. This is [9, Lemma 3.2].

We now prove 4 ⇒ 1. Assume 4. By Lemma 1 it suffices to prove that each infinite subset of ℕ includes arbitrarily large finite subsets. Given an infinite set C ⊆ ℕ, for each i ∈ ℕ let D_{i} be the set of strings in {0, 1}^{∗} of the form

σ^{⌢}⟨1⟩^{⌢}⟨\underbrace{0, …, 0}_{c}⟩^{⌢}⟨1⟩^{⌢}⟨\underbrace{0, …, 0}_{i}⟩^{⌢}⟨1⟩  (1)

where c ∈ C and c > the length of σ. The sequence of sets ⟨D_{i} | i ∈ ℕ⟩ exists by Δ_{1}^{0} comprehension. Since C is infinite, each D_{i} is dense in {0, 1}^{∗}. Given n ∈ ℕ, apply 4 to obtain X ∈ {0, 1}^{ℕ} such that X meets D_{i} for each i = 1, …, n. By Σ_{1}^{0} bounding [7] plus Δ_{1}^{0} comprehension, there exists a finite sequence of strings τ_{i}, 1 ≤ i ≤ n, such that τ_{i} ∈ D_{i} and τ_{i} ⊂ X for each i = 1, …, n. Consider the finite sequence c_{1}, …, c_{n} where τ_{i} is as in (1) with c = c_{i}. For i ≠ j we have τ_{i} ≠ τ_{j}, hence τ_{i} ⊂ τ_{j} or τ_{j} ⊂ τ_{i}, hence c_{i} < c_{j} or c_{j} > c_{i}, hence c_{i} ≠ c_{j}. Thus {c_{1}, …, c_{n}} is a finite subset of C of cardinality n, Q.E.D.

Theorem 2. BCT is not Π_{1}^{0}-conservative over RCA∗_{0}.

Proof. Recall from [6, §X.4] and [7] that RCA∗_{0} is RCA_{0} with Σ_{1}^{0} induction weakened to Σ_{0}^{0} induction plus natural number exponentiation, i.e., the assertion that m^{n} exists for all m, n ∈ ℕ. It is known that RCA∗_{0} is Π_{2}^{0}-equivalent to Elementary Function Arithmetic [7], hence much weaker than RCA_{0} which is Π_{2}^{0}-equivalent to Primitive Recursive Arithmetic [6, §IX.3]. Since Primitive Recursive Arithmetic proves the consistency of Elementary Function Arithmetic (see for instance [4] or [6, Theorems II.8.11 and IX.3.16]), it follows that RCA_{0} is not Π_{1}^{0}-conservative over RCA∗_{0}. This fact together with Theorem 1 gives Theorem 2.

Remarks.

1. Beyond RCA∗_{0} one may consider even weaker base theories for reverse mathematics. In this direction there is the following result of Fernandes [2]: BCT is Π_{1}^{1}-conservative over Σ_{1}^{b}-NIA+∇_{1}^{b}-CA. Note that Σ_{1}^{b}-NIA+∇_{1}^{b}- CA is “feasible,” i.e., it does not include natural number exponentiation.

2. Actually Fernandes [2] showed that BCT is conservative over Σ_{1}^{b}-NIA+∇_{1}^{b}- CA not only for Π_{1}^{1} sentences but also for sentences of the form (∀X) (∃ unique Y) Φ where Φ is arithmetical. And Yamazaki [10] showed that Π_{∞}^{0}- BCT is conservative over RCA_{0} for this same class of sentences, which arose previously in connection with Tanaka’s Conjecture [8, Theorem 4.18].

3. Our Theorems 1 and 2 were inspired by Fernandes [2, Proposition 1] and Hirschfeldt/Shore/Slaman [3, Theorem 4.3].

References

[1] Douglas K. Brown and Stephen G. Simpson. The Baire category theorem in weak subsystems of second order arithmetic. Journal of Symbolic Logic, 58:557–578, 1993. 1, 2

[2] António M. Fernandes. The Baire category theorem over a feasible base theory. In [5], pages 164–174, 2005. 3

[3] Denis R. Hirschfeldt, Richard A. Shore, and Theodore A. Slaman. The atomic model theorem and type omitting. Transactions of the American Mathematical Society, 361:5805–5837, 2009. 3 [4] Wilfried Sieg. Fragments of arithmetic. Annals of Pure and Applied Logic,

28:33–71, 1985. 3

[5] S. G. Simpson, editor. Reverse Mathematics 2001. Number 21 in Lecture Notes in Logic. Association for Symbolic Logic, 2005. X + 401 pages. 3

[6] Stephen G. Simpson. Subsystems of Second Order Arithmetic. Perspectives in Mathematical Logic. Springer-Verlag, 1999. XIV + 445 pages; Second Edition, Perspectives in Logic, Association for Symbolic Logic, Cambridge University Press, 2009, XVI+ 444 pages. 1, 3

[7] Stephen G. Simpson and Rick L. Smith. Factorization of polynomials and Σ_{1}^{0} induction. Annals of Pure and Applied Logic, 31:289–306, 1986. 1, 3

[8] Stephen G. Simpson, Kazuyuki Tanaka, and Takeshi Yamazaki. Some conservation results on weak König’s lemma. Annals of Pure and Applied Logic, 118:87–114, 2002. 3

[9] Stephen G. Simpson and Keita Yokoyama. Reverse mathematics and Peano categoricity. Annals of Pure and Applied Logic, 164:284–293, 2013. 1, 2

[10] Takeshi Yamazaki. Some more conservation results on the Baire Category Theorem. Mathematical Logic Quarterly, 46(1):105–110, 2000. 3

[11] Keita Yokoyama. On the strength of Ramsey’s Theorem without Σ_{1}- induction. Mathematical Logic Quarterly, 59:108–111, 2013. 1