In this paper we study the logical strength of the determinacy of infinite binary games in terms of second order arithmetic. We define new determinacy schemata inspired by the Wadge classes of Polish spaces and show the following equivalences over the system RCA0*, which consists of the axioms of discrete ordered semi‐rings with exponentiation, Δ10 comprehension and Π00 induction, and which is known as a weaker system than the popularbase theory RCA0: 1. Bisep(Δ10, Σ10)‐Det* ↔ WKL0, (...) 2. Bisep(Δ10, Σ20)‐Det* ↔ ATR0 + Σ11 induction, 3. Bisep(Σ10, Σ20)‐Det* ↔ Sep(Σ10, Σ20)‐Det* ↔ Π11‐CA0, 4. Bisep(Δ20, Σ20)‐Det* ↔ Π11‐TR0, where Det* stands for the determinacy of infinite games in the Cantor space (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

We study the Lindenbaum algebra ${\fancyscript{A}}$ (WKL o, RCA o) of sentences in the language of second-order arithmetic that imply RCA o and are provable from WKL o. We explore the relationship between ${\Sigma^1_1}$ sentences in ${\fancyscript{A}}$ (WKL o, RCA o) and ${\Pi^0_1}$ classes of subsets of ω. By applying a result of Binns and Simpson (Arch. Math. Logic 43(3), 399–414, 2004) about ${\Pi^0_1}$ classes, we give a specific embedding of the free distributive lattice with (...) countably many generators into ${\fancyscript{A}}$ (WKL o, RCA o). (shrink)

This is an introductory paper to a series of results linking generic absoluteness results for second and third order number theory to the model theoretic notion of model companionship. Specifically we develop here a general framework linking Woodin’s generic absoluteness results for second order number theory and the theory of universally Baire sets to model companionship and show that (with the required care in details) a $$\Pi _2$$ -property formalized in an appropriate language for second (...) order number theory is forcible from some $$T\supseteq \mathsf {ZFC}+$$ large cardinals if and only if it is consistent with the universal fragment of T if and only if it is realized in the model companion of T. In particular we show that the first order theory of $$H_{\omega _1}$$ is the model companion of the first order theory of the universe of sets assuming the existence of class many Woodin cardinals, and working in a signature with predicates for $$\Delta _0$$ -properties and for all universally Baire sets of reals. We will extend these results also to the theory of $$H_{\aleph _2}$$ in a follow up of this paper. (shrink)

This paper examines the ontological commitments of the second-order language of arithmetic and argues that they do not extend beyond the first-order language. Then, building on an argument by George Boolos, we develop a Tarski-style definition of a truth predicate for the second-order language of arithmetic that does not involve the assignment of sets to second-order variables but rather uses the same class of assignments standardly used in a definition for the (...) first-order language. (shrink)

Based on the paper [4] we show that true second‐order arithmetic is interpretable over the real‐algebraic structure of models of intuitionistic analysis built upon a certain class of complete Heyting algebras.

A theory T is tight if different deductively closed extensions of T (in the same language) cannot be bi-interpretable. Many well-studied foundational theories are tight, including $\mathsf {PA}$ [39], $\mathsf {ZF}$, $\mathsf {Z}_2$, and $\mathsf {KM}$ [6]. In this article we extend Enayat’s investigations to subsystems of these latter two theories. We prove that restricting the Comprehension schema of $\mathsf {Z}_2$ and $\mathsf {KM}$ gives non-tight theories. Specifically, we show that $\mathsf {GB}$ and $\mathsf {ACA}_0$ each admit different bi-interpretable extensions, (...) and the same holds for their extensions by adding $\Sigma ^1_k$ -Comprehension, for $k \ge 1$. These results provide evidence that tightness characterizes $\mathsf {Z}_2$ and $\mathsf {KM}$ in a minimal way. (shrink)

Second-order arithmetic and class theory are second-order theories of mathematical subjects of foundational importance, namely, arithmetic and set theory. Despite the similarity in appearance, there turned out to be significant mathematical dissimilarities between them. The present paper studies various principles in class theory, from such a comparative perspective between second-order arithmetic and class theory, and presents a few new dissimilarities between them.

We investigate the theory Peano Arithmetic with Indiscernibles ( \(\textrm{PAI}\) ). Models of \(\textrm{PAI}\) are of the form \(({\mathcal {M}},I)\), where \({\mathcal {M}}\) is a model of \(\textrm{PA}\), _I_ is an unbounded set of order indiscernibles over \({\mathcal {M}}\), and \(({\mathcal {M}},I)\) satisfies the extended induction scheme for formulae mentioning _I_. Our main results are Theorems A and B following. _Theorem A._ _Let_ \({\mathcal {M}}\) _be a nonstandard model of_ \(\textrm{PA}\) _ of any cardinality_. \(\mathcal {M }\) _has (...) an expansion to a model of _ \(\textrm{PAI}\) _iff_ \( {\mathcal {M}}\) _has an inductive partial satisfaction class._ Theorem A yields the following corollary, which provides a new characterization of countable recursively saturated models of \(\textrm{PA}\) : _Corollary._ _A countable model_ \({\mathcal {M}}\) of \(\textrm{PA}\) _is recursively saturated iff _ \({\mathcal {M}}\) _has an expansion to a model of _ \(\textrm{PAI}\). _Theorem B._ _There is a sentence _ \(\alpha \) _ in the language obtained by adding a unary predicate_ _I_(_x_) _to the language of arithmetic such that given any nonstandard model _ \({\mathcal {M}}\) _of_ \(\textrm{PA}\) _ of any cardinality_, \({\mathcal {M}}\) _has an expansion to a model of _ \(\text {PAI}+\alpha \) _iff_ \({\mathcal {M}}\) _has a inductive full satisfaction class._. (shrink)

We give a new elementary proof of the comparison theorem relating $\sum^1_{n + 1}-\mathrm{AC}\uparrow$ and $\Pi^1_n -\mathrm{CA}\uparrow$ ; the proof does not use Skolem theories. By the same method we prove: a) $\sum^1_{n + 1}-\mathrm{DC} \uparrow \equiv (\Pi^1_n -CA)_{ , for suitable classes of sentences; b) $\sum^1_{n+1}-DC \uparrow$ proves the consistency of (Π 1 n -CA) ω k, for finite k, and hence is stronger than $\sum^1_{n+1}-AC \uparrow$ . a) and b) answer a question of Feferman and Sieg.

Some axiomatic theories of truth and related subsystems of second-order arithmetic are surveyed and shown to be conservative over their respective base theory. In particular, it is shown by purely finitistically means that the theory PA ÷ "there is a satisfaction class" and the theory FS of [2] are conservative over PA.

Second-order logic has a number of attractive features, in particular the strong expressive resources it offers, and the possibility of articulating categorical mathematical theories (such as arithmetic and analysis). But it also has its costs. Five major charges have been launched against second-order logic: (1) It is not axiomatizable; as opposed to first-order logic, it is inherently incomplete. (2) It also has several semantics, and there is no criterion to choose between them (Putnam, J (...) Symbol Logic 45:464–482, 1980 ). Therefore, it is not clear how this logic should be interpreted. (3) Second-order logic also has strong ontological commitments: (a) it is ontologically committed to classes (Resnik, J Phil 85:75–87, 1988 ), and (b) according to Quine (Philosophy of logic, Prentice-Hall: Englewood Cliffs, 1970 ), it is nothing more than “set theory in sheep’s clothing”. (4) It is also not better than its first-order counterpart, in the following sense: if first-order logic does not characterize adequately mathematical systems, given the existence of non - isomorphic first-order interpretations, second-order logic does not characterize them either, given the existence of different interpretations of second-order theories (Melia, Analysis 55:127–134, 1995 ). (5) Finally, as opposed to what is claimed by defenders of second-order logic [such as Shapiro (J Symbol Logic 50:714–742, 1985 )], this logic does not solve the problem of referential access to mathematical objects (Azzouni, Metaphysical myths, mathematical practice: the logic and epistemology of the exact sciences, Cambridge University Press, Cambridge, 1994 ). In this paper, I argue that the second-order theorist can solve each of these difficulties. As a result, second-order logic provides the benefits of a rich framework without the associated costs. (shrink)

In the paper the problem of definability and undefinability of the concept of satisfaction and truth is considered. Connections between satisfaction and truth on the one hand and consistency of certain systems of omega-logic and transfinite induction on the other are indicated.

We introduce a second-order system V1-Horn of bounded arithmetic formalizing polynomial-time reasoning, based on Grädel's 35) second-order Horn characterization of P. Our system has comprehension over P predicates , and only finitely many function symbols. Other systems of polynomial-time reasoning either allow induction on NP predicates , and hence are more powerful than our system , or use Cobham's theorem to introduce function symbols for all polynomial-time functions . We prove that our system is equivalent (...) to QPV and Zambella's P-def. Using our techniques, we also show that V1-Horn is finitely axiomatizable, and, as a corollary, that the class of Σ1b consequences of S21 is finitely axiomatizable as well, thus answering an open question. (shrink)

The aim of this paper is to point out the equivalence between three notions respectively issued from recursion theory, computational complexity and finite model theory. One the one hand, the rudimentary languages are known to be characterized by the linear hierarchy. On the other hand, this complexity class can be proved to correspond to monadic second‐order logic with addition. Our viewpoint sheds some new light on the close connection between these domains: We bring together the two extremal notions (...) by providing a direct logical characterization of rudimentary languages and a representation result of second‐order logic into these languages. We use natural arithmetical tools, and our proofs contain no ingredient from computational complexity. (shrink)

We will introduce a partial ordering $\preceq_1$ on the class of ordinals which will serve as a foundation for an approach to ordinal notations for formal systems of set theory and second-order arithmetic. In this paper we use $\preceq_1$ to provide a new characterization of the ubiquitous ordinal $\epsilon _{0}$.

Journal of Mathematical Logic, Volume 23, Issue 02, August 2023. In mathematical logic there are two seemingly distinct kinds of principles called “reflection principles.” Semantic reflection principles assert that if a formula holds in the whole universe, then it holds in a set-sized model. Syntactic reflection principles assert that every provable sentence from some complexity class is true. In this paper, we study connections between these two kinds of reflection principles in the setting of second-order arithmetic. We (...) prove that, for a large swathe of theories, [math]-model reflection is equivalent to the claim that arbitrary iterations of uniform [math] reflection along countable well-orderings are [math]-sound. This result yields uniform ordinal analyzes of theories with strength between [math] and [math]. The main technical novelty of our analysis is the introduction of the notion of the proof-theoretic dilator of a theory [math], which is the operator on countable ordinals that maps the order-type of [math] to the proof-theoretic ordinal of [math]. We obtain precise results about the growth of proof-theoretic dilators as a function of provable [math]-model reflection. This approach enables us to simultaneously obtain not only [math], [math] and [math] ordinals but also reverse-mathematical theorems for well-ordering principles. (shrink)

We define theories of bounded arithmetic, whose definable functions and relations are exactly those in certain complexity classes. Based on a recursion-theoretic characterization of NC in Clote , the first-order theory TNC, whose principal axiom scheme is a form of short induction on notation for nondeterministic polynomial-time computable relations, has the property that those functions having nondeterministic polynomial-time graph Θ such that TNC x y Θ are exactly the functions in NC, computable on a parallel random-access machine (...) in polylogarithmic parallel time with a polynomial number of processors.0 We then define three theories of weak second-order arithmetic which respectively characterize relations in the classes of alternating logarithmic time, logspace and nondeterministic logspace. (shrink)

In this paper, we introduce systems of nonstandard second-order arithmetic which are conservative extensions of systems of second-order arithmetic. Within these systems, we do reverse mathematics for nonstandard analysis, and we can import techniques of nonstandard analysis into analysis in weak systems of second-order arithmetic. Then, we apply nonstandard techniques to a version of Riemannʼs mapping theorem, and show several different versions of Riemannʼs mapping theorem.

In this article we provide an intrinsic characterization of the famous Howard–Bachmann ordinal in terms of a natural well-partial-ordering by showing that this ordinal can be realized as a maximal order type of a class of generalized trees with respect to a homeomorphic embeddability relation. We use our calculations to draw some conclusions about some corresponding subsystems of second order arithmetic. All these subsystems deal with versions of light-face Π11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} (...) \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varPi ^1_1$$\end{document}-comprehension. (shrink)

We examine the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ of equivalence relations on $\omega $ under computable reducibility. We examine when pairs of degrees have a least upper bound. In particular, we show that sufficiently incomparable pairs of degrees do not have a least upper bound but that some incomparable degrees do, and we characterize the degrees which have a least upper bound with every finite equivalence relation. We show that the natural classes of finite, light, and dark degrees (...) are definable in $\operatorname {\mathrm {\mathbf {ER}}}$. We show that every equivalence relation has continuum many self-full strong minimal covers, and that $\mathbf {d}\oplus \mathbf {\operatorname {\mathrm {\mathbf {Id}}}_1}$ needn’t be a strong minimal cover of a self-full degree $\mathbf {d}$. Finally, we show that the theory of the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ as well as the theories of the substructures of light degrees and of dark degrees are each computably isomorphic with second-order arithmetic. (shrink)

Among the main theorems obtained in mathematical logic in this century are the so called limitation theorems, i.e., the Löwenheim-Skolem theorem on the cardinality of models of first-order theories, Gödel’s incompleteness theorems and Tarski’s theorem on the undefinability of truth. Problems connected with the latter are the subject of this paper. In Section 1 we shall consider Tarski’s theorem. In particular the original formulation of it as well as some specifications will be provided. Next various meanings of the notion (...) of a satisfaction predicate will be studied. In Section 2 the problem of definability of the notion of truth, in particular of the notion of truth for the language of Peano arithmetic PA, will be discussed. It will be explicitly shown that the notion of satisfaction for the language of PA can be defined in a certain weak fragment of the second order arithmetic. Finally the axiomatic characterization of satisfaction and truth as well and its mathematical and philosophical meaning will be discussed. (shrink)

We define a class of first-order formulas $\mathsf{P}^{\ast }$ which exactly contains formulas $\varphi$ such that satisfaction of $\varphi$ in any classical structure attached to a node of a Kripke model of intuitionistic predicate logic deciding atomic formulas implies its forcing in that node. We also define a class of $\mathsf{E}$-formulas with the property that their forcing coincides with their classical satisfiability in Kripke models which decide atomic formulas. We also prove that any formula with this property is (...) an $\mathsf{E}$-formula. Kripke models of intuitionistic arithmetical theories usually have this property. As a consequence, we prove a new conservativity result for Peano arithmetic over Heyting arithmetic. (shrink)

This paper presents a systematic study of the prehistory of the traditional subsystems of second-order arithmetic that feature prominently in the reverse mathematics program of Friedman and Simpson. We look in particular at: (i) the long arc from Poincar\'e to Feferman as concerns arithmetic definability and provability, (ii) the interplay between finitism and the formalization of analysis in the lecture notes and publications of Hilbert and Bernays, (iii) the uncertainty as to the constructive status of principles (...) equivalent to Weak K\"onig's Lemma, and (iv) the large-scale intellectual backdrop to arithmetical transfinite recursion in descriptive set theory and its effectivization by Borel, Lusin, Addison, and others. (shrink)

We show that there is a [Formula: see text]-model of second-order arithmetic in which the choice scheme holds, but the dependent choice scheme fails for a [Formula: see text]-assertion, confirming a conjecture of Stephen Simpson. We obtain as a corollary that the Reflection Principle, stating that every formula reflects to a transitive set, can fail in models of [Formula: see text]. This work is a rediscovery by the first two authors of a result obtained by the third (...) author in [V. G. Kanovei, On descriptive forms of the countable axiom of choice, Investigations on nonclassical logics and set theory, Work Collect., Moscow, 3-136 ]. (shrink)

Lyubetsky and Kanovei showed in [8] that there is a second-order arithmetic model of $\mathrm {Z}_2^{-p}$, (comprehension for all second-order formulas without parameters), in which $\Sigma ^1_2$ - $\mathrm {CA}$ (comprehension for all $\Sigma ^1_2$ -formulas with parameters) holds, but $\Sigma ^1_4$ - $\mathrm {CA}$ fails. They asked whether there is a model of $\mathrm {Z}_2^{-p}+\Sigma ^1_2$ - $\mathrm {CA}$ with the optimal failure of $\Sigma ^1_3$ - $\mathrm {CA}$. We answer the question positively by (...) constructing such a model in a forcing extension by a tree iteration of Jensen’s forcing. Let $\mathrm {Coll}^{-p}$ be the parameter-free collection scheme for second-order formulas and let $\mathrm {AC}^{-p}$ be the parameter-free choice scheme. We show that there is a model of $\mathrm {Z}_2^{-p}+\mathrm { AC}^{-p}+\Sigma ^1_2$ - $\mathrm {CA}$ with a failure of $\Sigma ^1_4$ - $\mathrm {CA}$. We also show that there is a model of $\mathrm {Z}_2^{-p}+\mathrm {Coll}^{-p}+\Sigma ^1_2$ - $\mathrm {CA}$ with a failure of $\Sigma ^1_4$ - $\mathrm {CA}$ and a failure of $\mathrm {AC}^{-p}$, so that, in particular, the schemes $\mathrm {Coll}^{-p}$ and $\mathrm {AC}^{-p}$ are not equivalent over $\mathrm {Z}_2^{-p}$. (shrink)

In this paper, we discuss uniform versions of some axioms of second order arithmetic in the context of higher order arithmetic. We prove that uniform versions of weak weak König's lemma WWKL and Σ01 separation are equivalent to over a suitable base theory of higher order arithmetic, where is the assertion that there exists Φ2 such that Φf1 = 0 if and only if ∃x0 for all f. We also prove that uniform versions (...) of some well-known theorems are equivalent to or the axiom of the existence of the Suslin operator. (shrink)

This paper describes axiomatic theories SA and SAR, which are versions of second order arithmetic with countably many sorts for sets of natural numbers. The theories are intended to be applied in reverse mathematics because their multi-sorted language allows to express some mathematical statements in more natural form than in the standard second order arithmetic. We study metamathematical properties of the theories SA, SAR and their fragments. We show that SA is mutually interpretable with (...) the theory of arithmetical truth PATr obtained from the Peano arithmetic by adding infinitely many truth predicates. Corresponding fragments of SA and PATr are also mutually interpretable. We compare the proof-theoretical strengths of the fragments; in particular, we show that each fragment SAs with sorts <=s is weaker than next fragment SAs+1. (shrink)

We consider fragments of uniform reflection for formulas in the analytic hierarchy over theories of second order arithmetic. The main result is that for any second order arithmetic theory $T_0$ extending $\mathsf {RCA}_0$ and axiomatizable by a $\Pi ^1_{k+2}$ sentence, and for any $n\geq k+1$, $$\begin{align*}T_0+ \mathrm{RFN}_{\varPi^1_{n+2}} \ = \ T_0 + \mathrm{TI}_{\varPi^1_n}, \end{align*}$$ $$\begin{align*}T_0+ \mathrm{RFN}_{\varSigma^1_{n+1}} \ = \ T_0+ \mathrm{TI}_{\varPi^1_n}^{-}, \end{align*}$$ where T is $T_0$ augmented with full induction, and $\mathrm {TI}_{\varPi ^1_n}^{-}$ denotes (...) the schema of transfinite induction up to $\varepsilon _0$ for $\varPi ^1_n$ formulas without set parameters. (shrink)

Constructive ZF + full separation is shown to be equiconsistent with Second Order Arithmetic.

We introduce a notion of syntactical truth predicate (s.t.p.) for the second order arithmetic PA 2 . An s.t.p. is a set T of closed formulas such that: (i) T(t = u) if and only if the closed first order terms t and u are convertible, i.e., have the same value in the standard interpretation (ii) T(A → B) if and only if (T(A) $\Longrightarrow$ T(B)) (iii) T(∀ x A) if and only if (T(A[x ← t]) (...) for any closed first order term t) (iv) T(∀ X A) if and only if (T(A[X ←▵]) for any closed set definition $\triangle = \{x \mid D(x)\}$ ). S.t.p.'s can be seen as a counterpart to Tarski's notion of (model-theoretical) validity and have main model properties. In particular, their existence is equivalent to the existence of an ω-model of PA 2 , this fact being provable in PA 2 with arithmetical comprehension only. (shrink)

Ratajczyk, Z., Subsystems of true arithmetic and hierarchies of functions, Annals of Pure and Applied Logic 64 95–152. The combinatorial method coming from the study of combinatorial sentences independent of PA is developed. Basing on this method we present the detailed analysis of provably recursive functions associated with higher levels of transfinite induction, I, and analyze combinatorial sentences independent of I. Our treatment of combinatorial sentences differs from the one given by McAloon [18] and gives more natural sentences. The (...) same method give also a combinatorial technique with no use of the cut-elimination theorem which is appropriate to study proof-theoretic strength of subsystems of first order arithmetic and some of their expansions. It was used to analyze iterated reflection principle and system of transfinite induction with a satisfaction class. (shrink)

We define classes Φnof formulae of first-order arithmetic with the following properties:(i) Everyφϵ Φnis classically equivalent to a Πn-formula (n≠ 1, Φ1:= Σ1).(ii)(iii)IΠnandiΦn(i.e., Heyting arithmetic with induction schema restricted to Φn-formulae) prove the same Π2-formulae.We further generalize a result by Visser and Wehmeier. namely that prenex induction within intuitionistic arithmetic is rather weak: After closing Φnboth under existential and universal quantification (we call these classes Θn) the corresponding theoriesiΘnstill prove the same Π2-formulae. In a (...) second part we consideriΔ0plus collection-principles. We show that both the provably recursive functions and the provably total functions ofare polynomially bounded. Furthermore we show that the contrapositive of the collection-schema gives rise to instances of the law of excluded middle and hence. (shrink)

In this paper I will communicate some new consequences of the Proper Forcing Axiom. First, the Bounded Proper Forcing Axiom implies that there is a well ordering of R which is Σ 1 -definable in (H(ω 2 ), ∈). Second, the Proper Forcing Axiom implies that the class of uncountable linear orders has a five element basis. The elements are X, ω 1 , ω 1 * , C, C * where X is any suborder of the reals of (...) size ω 1 and C is any Countryman line. Third, the Proper Forcing Axiom implies the Singular Cardinals Hypothesis at κ unless stationary subsets of S κ + ω reflect. The techniques are expected to be applicable to other open problems concerning the theory of H(ω 2 ). (shrink)

We show that certain model-theoretic forcing arguments involving subsystems of second-order arithmetic can be formalized in the base theory, thereby converting them to effective proof-theoretic arguments. We use this method to sharpen the conservation theorems of Harrington and Brown-Simpson, giving an effective proof that WKL+0 is conservative over RCA0 with no significant increase in the lengths of proofs.

In this paper, we show within ${\mathsf{RCA}_0}$ that both the Jordan curve theorem and the Schönflies theorem are equivalent to weak König’s lemma. Within ${\mathsf {WKL}_0}$ , we prove the Jordan curve theorem using an argument of non-standard analysis based on the fact that every countable non-standard model of ${\mathsf {WKL}_0}$ has a proper initial part that is isomorphic to itself (Tanaka in Math Logic Q 43:396–400, 1997).

This research is motivated by the program of Reverse Mathematics. We investigate basic part of complex analysis within some weak subsystems of second order arithmetic, in order to determine what kind of set existence axioms are needed to prove theorems of basic analysis. We are especially concerned with Cauchy’s integral theorem. We show that a weak version of Cauchy’s integral theorem is proved in RCAo. Using this, we can prove that holomorphic functions are analytic in RCAo. (...) On the other hand, we show that a full version of Cauchy’s integral theorem cannot be proved in RCAo but is equivalent to weak König’s lemma over RCAo. (shrink)

Yu, X., Riesz representation theorem, Borel measures and subsystems of second-order arithmetic, Annals of Pure and Applied Logic 59 65-78. Formalized concept of finite Borel measures is developed in the language of second-order arithmetic. Formalization of the Riesz representation theorem is proved to be equivalent to arithmetical comprehension. Codes of Borel sets of complete separable metric spaces are defined and proved to be meaningful in the subsystem ATR0. Arithmetical transfinite recursion is enough to prove (...) the measurability of Borel sets for any finite Borel measure on a compact complete separable metric space. (shrink)

In this paper, we introduce the systems ns-ACA₀ and ns-WKL₀ of non-standard second-order arithmetic in which we can formalize non-standard arguments in ACA₀ and WKL₀, respectively. Then, we give direct transformations from non-standard proofs in ns-ACA₀ or ns-WKL₀ into proofs in ACA₀ or WKL₀.

By RCA 0 , we denote a subsystem of second order arithmetic based on Δ0 1 comprehension and Δ0 1 induction. We show within this system that the real number system R satisfies all the theorems (possibly with non-standard length) of the theory of real closed fields under an appropriate truth definition. This enables us to develop linear algebra and polynomial ring theory over real and complex numbers, so that we particularly obtain Hilbert’s Nullstellensatz in RCA 0.

We study the formalization within sybsystems of second-order arithmetic of theorems concerning periodic points in dynamical systems on the real line. We show that Sharkovsky's theorem is provable in WKL0. We show that, with an additional assumption, Sharkovsky's theorem is provable in RCA0. We show that the existence for all n of n-fold iterates of continuous mappings of the closed unit interval into itself is equivalent to the disjunction of Σ02 induction and weak König's lemma.

We study the provability in subsystems of second-order arithmetic of two theorems of Harrington and Shelah [6] about Borel quasi-orderings of the reals. These theorems turn out to be provable in ATR0, thus giving further evidence to the observation that ATR0 is the minimal subsystem of second-order arithmetic in which significant portion of descriptive set theory can be developed. As in [6] considering the lightface versions of the theorems will be instrumental in their proof (...) and the main techniques employed will be the reflection principles and Gandy forcing. (shrink)

Hindman's Theorem is a prototypical example of a combinatorial theorem with a proof that uses the topology of the ultrafilters. We show how the methods of this proof, including topological arguments about ultrafilters, can be translated into second order arithmetic.

Working within weak subsystems of second-order arithmetic Z2 we consider two versions of the Baire Category theorem which are not equivalent over the base system RCA0. We show that one version (B.C.T.I) is provable in RCA0 while the second version (B.C.T.II) requires a stronger system. We introduce two new subsystems of Z2, which we call RCA+ 0 and WKL+ 0, and show that RCA+ 0 suffices to prove B.C.T.II. Some model theory of WKL+ 0 and its (...) importance in view of Hilbert's program is discussed, as well as applications of our results to functional analysis. (shrink)

We develop fundamental aspects of the theory of metric, Hilbert, and Banach spaces in the context of subsystems of second-order arithmetic. In particular, we explore issues having to do with distances, closed subsets and subspaces, closures, bases, norms, and projections. We pay close attention to variations that arise when formalizing definitions and theorems, and study the relationships between them.