Switch to: References

Citations of:

Subsystems of Second Order Arithmetic

Springer Verlag (1998)

Add citations

You must login to add citations.
  1. How can a line segment with extension be composed of extensionless points?Brian Reese, Michael Vazquez & Scott Weinstein - 2022 - Synthese 200 (2):1-28.
    We provide a new interpretation of Zeno’s Paradox of Measure that begins by giving a substantive account, drawn from Aristotle’s text, of the fact that points lack magnitude. The main elements of this account are (1) the Axiom of Archimedes which states that there are no infinitesimal magnitudes, and (2) the principle that all assignments of magnitude, or lack thereof, must be grounded in the magnitude of line segments, the primary objects to which the notion of linear magnitude applies. Armed (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • The Potential in Frege’s Theorem.Will Stafford - 2023 - Review of Symbolic Logic 16 (2):553-577.
    Is a logicist bound to the claim that as a matter of analytic truth there is an actual infinity of objects? If Hume’s Principle is analytic then in the standard setting the answer appears to be yes. Hodes’s work pointed to a way out by offering a modal picture in which only a potential infinity was posited. However, this project was abandoned due to apparent failures of cross-world predication. We re-explore this idea and discover that in the setting of the (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Review of John Stillwell, Reverse Mathematics: Proofs from the Inside Out. [REVIEW]Benedict Eastaugh - 2020 - Philosophia Mathematica 28 (1):108-116.
    Review of John Stillwell, Reverse Mathematics: Proofs from the Inside Out. Princeton, NJ: Princeton University Press, 2018, pp. 200. ISBN 978-0-69-117717-5 (hbk), 978-0-69-119641-1 (pbk), 978-1-40-088903-7 (e-book).
    Download  
     
    Export citation  
     
    Bookmark  
  • Otávio Bueno* and Steven French.**Applying Mathematics: Immersion, Inference, Interpretation. [REVIEW]Anthony F. Peressini - 2020 - Philosophia Mathematica 28 (1):116-127.
    Otávio Bueno* * and Steven French.** ** Applying Mathematics: Immersion, Inference, Interpretation. Oxford University Press, 2018. ISBN: 978-0-19-881504-4 978-0-19-185286-2. doi:10.1093/oso/9780198815044. 001.0001. Pp. xvii + 257.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Suggestion for Teaching Science as a Pluralist Enterprise.Antonino Drago - 2018 - Transversal: International Journal for the Historiography of Science 5:66-83.
    The change in the organization of science education over the past fifty years is quickly recalled. Being its cultural bound the lack of a conception of the foundation of science, the multiple innovations have resulted as temporary improvements without a clear direction, apart from the technocratic goal of an automation of learning processes. The discovery of two dichotomies as the foundations of science suggests a pluralist conception of science, and hence the need to entirely renew science education, in particular by (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • (1 other version)Exploring Predicativity.Laura Crosilla - 1995 - In Klaus Mainzer, Peter Schuster & Helmut Schwichtenberg (eds.), Proof and Computation. World Scientific. pp. 83-108.
    Prominent constructive theories of sets as Martin-Löf type theory and Aczel and Myhill constructive set theory, feature a distinctive form of constructivity: predicativity. This may be phrased as a constructibility requirement for sets, which ought to be finitely specifiable in terms of some uncontroversial initial “objects” and simple operations over them. Predicativity emerged at the beginning of the 20th century as a fundamental component of an influential analysis of the paradoxes by Poincaré and Russell. According to this analysis the paradoxes (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Axiomatizing Changing Conceptions of the Geometric Continuum II: Archimedes-Descartes-Hilbert-Tarski†.John T. Baldwin - 2019 - Philosophia Mathematica 27 (1):33-60.
    In Part I of this paper we argued that the first-order systems HP5 and EG are modest complete descriptive axiomatization of most of Euclidean geometry. In this paper we discuss two further modest complete descriptive axiomatizations: Tarksi’s for Cartesian geometry and new systems for adding $$\pi$$. In contrast we find Hilbert’s full second-order system immodest for geometrical purposes but appropriate as a foundation for mathematical analysis.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Logical and Epistemic Modality.David Elohim - manuscript
    This paper examines the interaction between the philosophy and psychology of concepts and the modal characterization of the deductive concept of logical validity. The concept of logical consequence on which I focus is model-theoretic, where the concept records the property of necessary truth-preservation from the premise of an argument to its conclusion, as well as the condition that, in the class of all possible worlds in which a premise is true, a consequent formula or succedent class of formulas is true, (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • (1 other version)Forms of Luminosity: Epistemic Modality and Hyperintensionality in Mathematics.David Elohim - 2017 - Dissertation, Arché, University of St Andrews
    This book concerns the foundations of epistemic modality and hyperintensionality and their applications to the philosophy of mathematics. David Elohim examines the nature of epistemic modality, when the modal operator is interpreted as concerning both apriority and conceivability, as well as states of knowledge and belief. The book demonstrates how epistemic modality and hyperintensionality relate to the computational theory of mind; metaphysical modality and hyperintensionality; the types of mathematical modality and hyperintensionality; to the epistemic status of large cardinal axioms, undecidable (...)
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • (1 other version)Forms of Luminosity: Epistemic Modality and Hyperintensionality in Mathematics.David Elohim - 2017
    This book concerns the foundations of epistemic modality and hyperintensionality and their applications to the philosophy of mathematics. David Elohim examines the nature of epistemic modality, when the modal operator is interpreted as concerning both apriority and conceivability, as well as states of knowledge and belief. The book demonstrates how epistemic modality and hyperintensionality relate to the computational theory of mind; metaphysical modality and hyperintensionality; the types of mathematical modality and hyperintensionality; to the epistemic status of large cardinal axioms, undecidable (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Reverse formalism 16.Sam Sanders - 2020 - Synthese 197 (2):497-544.
    In his remarkable paper Formalism 64, Robinson defends his eponymous position concerning the foundations of mathematics, as follows:Any mention of infinite totalities is literally meaningless.We should act as if infinite totalities really existed. Being the originator of Nonstandard Analysis, it stands to reason that Robinson would have often been faced with the opposing position that ‘some infinite totalities are more meaningful than others’, the textbook example being that of infinitesimals. For instance, Bishop and Connes have made such claims regarding infinitesimals, (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • The foundations of mathematics from a historical viewpoint.Antonino Drago - 2015 - Epistemologia 38 (1):133-151.
    A new hypothesis on the basic features characterising the Foundations of Mathematics is suggested. By means of them the entire historical development of Mathematics before the 20th Century is summarised through a table. Also the several programs, launched around the year 1900, on the Foundations of Mathematics are characterised by a corresponding table. The major difficulty that these programs met was to recognize an alternative to the basic feature of the deductive organization of a theory - more precisely, to Hilbert’s (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Large Cardinals, Inner Models, and Determinacy: An Introductory Overview.P. D. Welch - 2015 - Notre Dame Journal of Formal Logic 56 (1):213-242.
    The interaction between large cardinals, determinacy of two-person perfect information games, and inner model theory has been a singularly powerful driving force in modern set theory during the last three decades. For the outsider the intellectual excitement is often tempered by the somewhat daunting technicalities, and the seeming length of study needed to understand the flow of ideas. The purpose of this article is to try and give a short, albeit rather rough, guide to the broad lines of development.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Axiomatizing semantic theories of truth?Martin Fischer, Volker Halbach, Jönne Kriener & Johannes Stern - 2015 - Review of Symbolic Logic 8 (2):257-278.
    We discuss the interplay between the axiomatic and the semantic approach to truth. Often, semantic constructions have guided the development of axiomatic theories and certain axiomatic theories have been claimed to capture a semantic construction. We ask under which conditions an axiomatic theory captures a semantic construction. After discussing some potential criteria, we focus on the criterion of ℕ-categoricity and discuss its usefulness and limits.
    Download  
     
    Export citation  
     
    Bookmark   27 citations  
  • On the Concept of Finitism.Luca Incurvati - 2015 - Synthese 192 (8):2413-2436.
    At the most general level, the concept of finitism is typically characterized by saying that finitistic mathematics is that part of mathematics which does not appeal to completed infinite totalities and is endowed with some epistemological property that makes it secure or privileged. This paper argues that this characterization can in fact be sharpened in various ways, giving rise to different conceptions of finitism. The paper investigates these conceptions and shows that they sanction different portions of mathematics as finitistic.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Logicism, Interpretability, and Knowledge of Arithmetic.Sean Walsh - 2014 - Review of Symbolic Logic 7 (1):84-119.
    A crucial part of the contemporary interest in logicism in the philosophy of mathematics resides in its idea that arithmetical knowledge may be based on logical knowledge. Here an implementation of this idea is considered that holds that knowledge of arithmetical principles may be based on two things: (i) knowledge of logical principles and (ii) knowledge that the arithmetical principles are representable in the logical principles. The notions of representation considered here are related to theory-based and structure-based notions of representation (...)
    Download  
     
    Export citation  
     
    Bookmark   8 citations  
  • Models and Computability.W. Dean - 2014 - Philosophia Mathematica 22 (2):143-166.
    Computationalism holds that our grasp of notions like ‘computable function’ can be used to account for our putative ability to refer to the standard model of arithmetic. Tennenbaum's Theorem has been repeatedly invoked in service of this claim. I will argue that not only do the relevant class of arguments fail, but that the result itself is most naturally understood as having the opposite of a reference-fixing effect — i.e., rather than securing the determinacy of number-theoretic reference, Tennenbaum's Theorem points (...)
    Download  
     
    Export citation  
     
    Bookmark   9 citations  
  • Cohesive sets and rainbows.Wei Wang - 2014 - Annals of Pure and Applied Logic 165 (2):389-408.
    We study the strength of RRT32, Rainbow Ramsey Theorem for colorings of triples, and prove that RCA0 + RRT32 implies neither WKL0 nor RRT42 source. To this end, we establish some recursion theoretic properties of cohesive sets and rainbows for colorings of pairs. We show that every sequence admits a cohesive set of non-PA Turing degree; and that every ∅′-recursive sequence admits a low3 cohesive set.
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • The polarized Ramsey’s theorem.Damir D. Dzhafarov & Jeffry L. Hirst - 2009 - Archive for Mathematical Logic 48 (2):141-157.
    We study the effective and proof-theoretic content of the polarized Ramsey’s theorem, a variant of Ramsey’s theorem obtained by relaxing the definition of homogeneous set. Our investigation yields a new characterization of Ramsey’s theorem in all exponents, and produces several combinatorial principles which, modulo bounding for ${\Sigma^0_2}$ formulas, lie (possibly not strictly) between Ramsey’s theorem for pairs and the stable Ramsey’s theorem for pairs.
    Download  
     
    Export citation  
     
    Bookmark   8 citations  
  • $${\Pi^1_2}$$ -comprehension and the property of Ramsey.Christoph Heinatsch - 2009 - Archive for Mathematical Logic 48 (3-4):323-386.
    We show that a theory of autonomous iterated Ramseyness based on second order arithmetic (SOA) is proof-theoretically equivalent to ${\Pi^1_2}$ -comprehension. The property of Ramsey is defined as follows. Let X be a set of real numbers, i.e. a set of infinite sets of natural numbers. We call a set H of natural numbers homogeneous for X if either all infinite subsets of H are in X or all infinite subsets of H are not in X. X has the property (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • On the connection between Nonstandard Analysis and Constructive Analysis.Sam Sanders - forthcoming - Logique Et Analyse.
    Constructive Analysis and Nonstandard Analysis are often characterized as completely antipodal approaches to analysis. We discuss the possibility of capturing the central notion of Constructive Analysis (i.e. algorithm, finite procedure or explicit construction) by a simple concept inside Nonstandard Analysis. To this end, we introduce Omega-invariance and argue that it partially satisfies our goal. Our results provide a dual approach to Erik Palmgren's development of Nonstandard Analysis inside constructive mathematics.
    Download  
     
    Export citation  
     
    Bookmark  
  • Fast-Collapsing Theories.Samuel A. Alexander - 2013 - Studia Logica (1):1-21.
    Reinhardt’s conjecture, a formalization of the statement that a truthful knowing machine can know its own truthfulness and mechanicalness, was proved by Carlson using sophisticated structural results about the ordinals and transfinite induction just beyond the first epsilon number. We prove a weaker version of the conjecture, by elementary methods and transfinite induction up to a smaller ordinal.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Kolmogorov complexity and the second incompleteness theorem.Makoto Kikuchi - 1997 - Archive for Mathematical Logic 36 (6):437-443.
    We shall prove the second incompleteness theorem via Kolmogorov complexity.
    Download  
     
    Export citation  
     
    Bookmark   7 citations  
  • Axioms in Mathematical Practice.Dirk Schlimm - 2013 - Philosophia Mathematica 21 (1):37-92.
    On the basis of a wide range of historical examples various features of axioms are discussed in relation to their use in mathematical practice. A very general framework for this discussion is provided, and it is argued that axioms can play many roles in mathematics and that viewing them as self-evident truths does not do justice to the ways in which mathematicians employ axioms. Possible origins of axioms and criteria for choosing axioms are also examined. The distinctions introduced aim at (...)
    Download  
     
    Export citation  
     
    Bookmark   20 citations  
  • The Metamathematics of Putnam’s Model-Theoretic Arguments.Tim Button - 2011 - Erkenntnis 74 (3):321-349.
    Putnam famously attempted to use model theory to draw metaphysical conclusions. His Skolemisation argument sought to show metaphysical realists that their favourite theories have countable models. His permutation argument sought to show that they have permuted models. His constructivisation argument sought to show that any empirical evidence is compatible with the Axiom of Constructibility. Here, I examine the metamathematics of all three model-theoretic arguments, and I argue against Bays (2001, 2007) that Putnam is largely immune to metamathematical challenges.
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • Proof theory in philosophy of mathematics.Andrew Arana - 2010 - Philosophy Compass 5 (4):336-347.
    A variety of projects in proof theory of relevance to the philosophy of mathematics are surveyed, including Gödel's incompleteness theorems, conservation results, independence results, ordinal analysis, predicativity, reverse mathematics, speed-up results, and provability logics.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Logicism Revisited.Otávio Bueno - 2001 - Principia 5 (1-2):99-124.
    In this paper, I develop a new defense of logicism: one that combines logicism and nominalism. First, I defend the logicist approach from recent criticisms; in particular from the charge that a cruciai principie in the logicist reconstruction of arithmetic, Hume's Principle, is not analytic. In order to do that, I argue, it is crucial to understand the overall logicist approach as a nominalist view. I then indicate a way of extending the nominalist logicist approach beyond arithmetic. Finally, I argue (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • A general theory of abstraction operators.Neil Tennant - 2004 - Philosophical Quarterly 54 (214):105-133.
    I present a general theory of abstraction operators which treats them as variable-binding term- forming operators, and provides a reasonably uniform treatment for definite descriptions, set abstracts, natural number abstraction, and real number abstraction. This minimizing, extensional and relational theory reveals a striking similarity between definite descriptions and set abstracts, and provides a clear rationale for the claim that there is a logic of sets (which is ontologically non- committal). The theory also treats both natural and real numbers as answering (...)
    Download  
     
    Export citation  
     
    Bookmark   18 citations  
  • Gödel's functional interpretation and its use in current mathematics.Ulrich Kohlenbach - 2008 - Dialectica 62 (2):223–267.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • The determinacy strength of Π 2 1 -comprehension.Christoph Heinatsch & Michael Möllerfeld - 2010 - Annals of Pure and Applied Logic 161 (12):1462-1470.
    Determinacy axioms state the existence of winning strategies for infinite games played by two players on natural numbers. We show that a base theory enriched by a certain scheme of determinacy axioms is proof-theoretically equivalent to -comprehension.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Ordered groups: A case study in reverse mathematics.Reed Solomon - 1999 - Bulletin of Symbolic Logic 5 (1):45-58.
    The fundamental question in reverse mathematics is to determine which set existence axioms are required to prove particular theorems of mathematics. In addition to being interesting in their own right, answers to this question have consequences in both effective mathematics and the foundations of mathematics. Before discussing these consequences, we need to be more specific about the motivating question.Reverse mathematics is useful for studying theorems of either countable or essentially countable mathematics. Essentially countable mathematics is a vague term that is (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Is Cantor's continuum problem inherently vague?Kai Hauser - 2002 - Philosophia Mathematica 10 (3):257-285.
    I examine various claims to the effect that Cantor's Continuum Hypothesis and other problems of higher set theory are ill-posed questions. The analysis takes into account the viability of the underlying philosophical views and recent mathematical developments.
    Download  
     
    Export citation  
     
    Bookmark   11 citations  
  • Number theory and elementary arithmetic.Jeremy Avigad - 2003 - Philosophia Mathematica 11 (3):257-284.
    is a fragment of first-order aritlimetic so weak that it cannot prove the totality of an iterated exponential fimction. Surprisingly, however, the theory is remarkably robust. I will discuss formal results that show that many theorems of number theory and combinatorics are derivable in elementary arithmetic, and try to place these results in a broader philosophical context.
    Download  
     
    Export citation  
     
    Bookmark   19 citations  
  • Short note: Least fixed points versus least closed points.Gerhard Jäger - 2021 - Archive for Mathematical Logic 60 (7):831-835.
    This short note is on the question whether the intersection of all fixed points of a positive arithmetic operator and the intersection of all its closed points can proved to be equivalent in a weak fragment of second order arithmetic.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Theories and Ordinals in Proof Theory.Michael Rathjen - 2006 - Synthese 148 (3):719-743.
    How do ordinals measure the strength and computational power of formal theories? This paper is concerned with the connection between ordinal representation systems and theories established in ordinal analyses. It focusses on results which explain the nature of this connection in terms of semantical and computational notions from model theory, set theory, and generalized recursion theory.
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • The Constructive Hilbert Program and the Limits of Martin-Löf Type Theory.Michael Rathjen - 2005 - Synthese 147 (1):81-120.
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • The logical structure of evolutionary explanation and prediction: Darwinism’s fundamental schema.Neil Tennant - 2014 - Biology and Philosophy 29 (5):611-655.
    We present a logically detailed case-study of Darwinian evolutionary explanation. Special features of Darwin’s explanatory schema made it an unusual theoretical breakthrough, from the point of view of the philosophy of science. The schema employs no theoretical terms, and puts forward no theoretical hypotheses. Instead, it uses three observational generalizations—Variability, Heritability and Differential Reproduction—along with an innocuous assumption of Causal Efficacy, to derive Adaptive Evolution as a necessary consequence. Adaptive Evolution in turn, with one assumption of scale (‘Deep Time’), implies (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Reflections on reflections in explicit mathematics.Gerhard Jäger & Thomas Strahm - 2005 - Annals of Pure and Applied Logic 136 (1-2):116-133.
    We give a broad discussion of reflection principles in explicit mathematics, thereby addressing various kinds of universe existence principles. The proof-theoretic strength of the relevant systems of explicit mathematics is couched in terms of suitable extensions of Kripke–Platek set theory.
    Download  
     
    Export citation  
     
    Bookmark   7 citations  
  • On the proof-theoretic strength of monotone induction in explicit mathematics.Thomas Glaß, Michael Rathjen & Andreas Schlüter - 1997 - Annals of Pure and Applied Logic 85 (1):1-46.
    We characterize the proof-theoretic strength of systems of explicit mathematics with a general principle asserting the existence of least fixed points for monotone inductive definitions, in terms of certain systems of analysis and set theory. In the case of analysis, these are systems which contain the Σ12-axiom of choice and Π12-comprehension for formulas without set parameters. In the case of set theory, these are systems containing the Kripke-Platek axioms for a recursively inaccessible universe together with the existence of a stable (...)
    Download  
     
    Export citation  
     
    Bookmark   9 citations  
  • Reverse-engineering Reverse Mathematics.Sam Sanders - 2013 - Annals of Pure and Applied Logic 164 (5):528-541.
    An important open problem in Reverse Mathematics is the reduction of the first-order strength of the base theory from IΣ1IΣ1 to IΔ0+expIΔ0+exp. The system ERNA, a version of Nonstandard Analysis based on the system IΔ0+expIΔ0+exp, provides a partial solution to this problem. Indeed, weak Königʼs lemma and many of its equivalent formulations from Reverse Mathematics can be ‘pushed down’ into ERNA, while preserving the equivalences, but at the price of replacing equality with ‘≈’, i.e. infinitesimal proximity . The logical principle (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Kripke-Platek Set Theory and the Anti-Foundation Axiom.Michael Rathjen - 2001 - Mathematical Logic Quarterly 47 (4):435-440.
    The paper investigates the strength of the Anti-Foundation Axiom, AFA, on the basis of Kripke-Platek set theory without Foundation. It is shown that the addition of AFA considerably increases the proof theoretic strength.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • The strong soundness theorem for real closed fields and Hilbert’s Nullstellensatz in second order arithmetic.Nobuyuki Sakamoto & Kazuyuki Tanaka - 2004 - Archive for Mathematical Logic 43 (3):337-349.
    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.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • A note on the theory of positive induction, $${{\rm ID}^*_1}$$.Bahareh Afshari & Michael Rathjen - 2010 - Archive for Mathematical Logic 49 (2):275-281.
    The article shows a simple way of calibrating the strength of the theory of positive induction, ${{\rm ID}^{*}_{1}}$ . Crucially the proof exploits the equivalence of ${\Sigma^{1}_{1}}$ dependent choice and ω-model reflection for ${\Pi^{1}_{2}}$ formulae over ACA 0. Unbeknown to the authors, D. Probst had already determined the proof-theoretic strength of ${{\rm ID}^{*}_{1}}$ in Probst, J Symb Log, 71, 721–746, 2006.
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • An ordinal analysis for theories of self-referential truth.Graham Emil Leigh & Michael Rathjen - 2010 - Archive for Mathematical Logic 49 (2):213-247.
    The first attempt at a systematic approach to axiomatic theories of truth was undertaken by Friedman and Sheard (Ann Pure Appl Log 33:1–21, 1987). There twelve principles consisting of axioms, axiom schemata and rules of inference, each embodying a reasonable property of truth were isolated for study. Working with a base theory of truth conservative over PA, Friedman and Sheard raised the following questions. Which subsets of the Optional Axioms are consistent over the base theory? What are the proof-theoretic strengths (...)
    Download  
     
    Export citation  
     
    Bookmark   14 citations  
  • Harrington’s conservation theorem redone.Fernando Ferreira & Gilda Ferreira - 2008 - Archive for Mathematical Logic 47 (2):91-100.
    Leo Harrington showed that the second-order theory of arithmetic WKL 0 is ${\Pi^1_1}$ -conservative over the theory RCA 0. Harrington’s proof is model-theoretic, making use of a forcing argument. A purely proof-theoretic proof, avoiding forcing, has been eluding the efforts of researchers. In this short paper, we present a proof of Harrington’s result using a cut-elimination argument.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Fixed point theories and dependent choice.Gerhard Jäger & Thomas Strahm - 2000 - Archive for Mathematical Logic 39 (7):493-508.
    In this paper we establish the proof-theoretic equivalence of (i) $\hbox {\sf ATR}$ and $\widehat{\hbox{\sf ID}}_{\omega}$ , (ii) $\hbox{\sf ATR}_0+ (\Sigma^1_1-\hbox{\sf DC})$ and $\widehat{\hbox {\sf ID}}_{<\omega^\omega} , and (iii) $\hbox {\sf ATR}+(\Sigma^1_1-\hbox{\sf DC})$ and $\widehat{\hbox {\sf ID}}_{<\varepsilon_0} $.
    Download  
     
    Export citation  
     
    Bookmark   10 citations  
  • Expressive power of digraph solvability.Marc Bezem, Clemens Grabmayer & Michał Walicki - 2012 - Annals of Pure and Applied Logic 163 (3):200-213.
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • On arbitrary sets and ZFC.José Ferreirós - 2011 - Bulletin of Symbolic Logic 17 (3):361-393.
    Set theory deals with the most fundamental existence questions in mathematics—questions which affect other areas of mathematics, from the real numbers to structures of all kinds, but which are posed as dealing with the existence of sets. Especially noteworthy are principles establishing the existence of some infinite sets, the so-called “arbitrary sets.” This paper is devoted to an analysis of the motivating goal of studying arbitrary sets, usually referred to under the labels of quasi-combinatorialism or combinatorial maximality. After explaining what (...)
    Download  
     
    Export citation  
     
    Bookmark   7 citations  
  • (1 other version)Predicativity.Solomon Feferman - 2005 - In Stewart Shapiro (ed.), Oxford Handbook of Philosophy of Mathematics and Logic. Oxford and New York: Oxford University Press. pp. 590-624.
    What is predicativity? While the term suggests that there is a single idea involved, what the history will show is that there are a number of ideas of predicativity which may lead to different logical analyses, and I shall uncover these only gradually. A central question will then be what, if anything, unifies them. Though early discussions are often muddy on the concepts and their employment, in a number of important respects they set the stage for the further developments, and (...)
    Download  
     
    Export citation  
     
    Bookmark   30 citations  
  • Groundwork for weak analysis.António M. Fernandes & Fernando Ferreira - 2002 - Journal of Symbolic Logic 67 (2):557-578.
    This paper develops the very basic notions of analysis in a weak second-order theory of arithmetic BTFA whose provably total functions are the polynomial time computable functions. We formalize within BTFA the real number system and the notion of a continuous real function of a real variable. The theory BTFA is able to prove the intermediate value theorem, wherefore it follows that the system of real numbers is a real closed ordered field. In the last section of the paper, we (...)
    Download  
     
    Export citation  
     
    Bookmark   10 citations