In finite type arithmetic, the real numbers are represented by rapidly converging Cauchy sequences of rational numbers. Ulrich Kohlenbach introduced abstract types for certain structures such as metric spaces, normed spaces, Hilbert spaces, etc. With these types, the elements of the spaces are given directly, not through the mediation of a representation. However, these abstract spaces presuppose the real numbers. In this paper, we show how to set up an abstract type for the real numbers. The appropriateness of our construction (...) works in tandem with the bounded functional interpretation. (shrink)

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.

This paper aims to study the foundations of applied mathematics, using a formalized base theory for applied mathematics: ZFCAσ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \mathsf {ZFCA}_{\sigma }$$\end{document} with atoms, where the subscript used refers to a signature specific to the application. Examples are given, illustrating the following five features of applied mathematics: comprehension principles, application conditionals, representation hypotheses, transfer principles and abstract equivalents.

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 (...) potential infinite one can interpret first-order Peano arithmetic, but not second-order Peano arithmetic. We conclude that in order for the logicist to weaken the metaphysically loaded claim of necessary actual infinities, they must also weaken the mathematics they recover. (shrink)

This dissertation examines several of the problems that Hilbert discovered in the foundations of mathematics, from a metalogical perspective. The problems manifest themselves in four different aspects of Hilbert’s views: (i) Hilbert’s axiomatic approach to the foundations of mathematics; (ii) His response to criticisms of set theory; (iii) His response to intuitionist criticisms of classical mathematics; (iv) Hilbert’s contribution to the specification of the role of logical inference in mathematical reasoning. This dissertation argues that Hilbert’s axiomatic approach was guided primarily (...) by model theoretical concerns. Accordingly, the ultimate aim of his consistency program was to prove the model-theoretical consistency of mathematical theories. It turns out that for the purpose of carrying out such consistency proofs, a suitable modification of the ordinary first-order logic is needed. To effect this modification, independence-friendly logic is needed as the appropriate conceptual framework. It is then shown how the model theoretical consistency of arithmetic can be proved by using IF logic as its basic logic. Hilbert’s other problems, manifesting themselves as aspects (ii), (iii), and (iv)—most notably the problem of the status of the axiom of choice, the problem of the role of the law of excluded middle, and the problem of giving an elementary account of quantification—can likewise be approached by using the resources of IF logic. It is shown that by means of IF logic one can carry out Hilbertian solutions to all these problems. The two major results concerning aspects (ii), (iii) and (iv) are the following: (a) The axiom of choice is a logical principle; (b) The law of excluded middle divides metamathematical methods into elementary and non-elementary ones. It is argued that these results show that IF logic helps to vindicate Hilbert’s nominalist philosophy of mathematics. On the basis of an elementary approach to logic, which enriches the expressive resources of ordinary first-order logic, this dissertation shows how the different problems that Hilbert discovered in the foundations of mathematics can be solved. (shrink)

There are close similarities between the Weihrauch lattice and the zoo of axiom systems in reverse mathematics. Following these similarities has often allowed researchers to translate results from one setting to the other. However, amongst the big five axiom systems from reverse mathematics, so far $\mathrm {ATR}_0$ has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated.

We study the computational content of various theorems with reverse mathematical strength around Arithmetical Transfinite Recursion (ATR_0) from the point of view of computability-theoretic reducibilities, in particular Weihrauch reducibility. Our main result states that it is equally hard to construct an embedding between two given well-orderings, as it is to construct a Turing jump hierarchy on a given well-ordering. This answers a question of Marcone. We obtain a similar result for Fraïssé's conjecture restricted to well-orderings.

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).

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.

We present statements equivalent to some fragments of the principle of non-deterministic inductive definitions (NID) by van den Berg (2013), working in a weak subsystem of constructive set theory CZF. We show that several statements in constructive topology which were initially proved using NID are equivalent to the elementary and finitary NIDs. We also show that the finitary NID is equivalent to its binary fragment and that the elementary NID is equivalent to a variant of NID based on the notion (...) of biclosed subset. Our result suggests that proving these statements in constructive topology requires genuine extensions of CZF with the elementary or finitary NID. (shrink)

A number of examples of studies from the field ‘The Philosophy of Mathematical Practice’ (PMP) are given. To characterise this new field, three different strands are identified: an agent-based, a historical, and an epistemological PMP. These differ in how they understand ‘practice’ and which assumptions lie at the core of their investigations. In the last part a general framework, capturing some overall structure of the field, is proposed.

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 (...) introducing the notions of incommensurability and radical variations in meaning of the basic notions. This change was already anticipated by several proposals within each subject-matter. (shrink)

MethodologyA new hypothesis on the basic features characterizing the Foundations of Mathematics is suggested.Application of the methodBy means of it, the several proposals, launched around the year 1900, for discovering the FoM are characterized. It is well known that the historical evolution of these proposals was marked by some notorious failures and conflicts. Particular attention is given to Cantor's programme and its improvements. Its merits and insufficiencies are characterized in the light of the new conception of the FoM. After the (...) failures of Frege's and Cantor's programmes owing to the discoveries of an antinomy and internal contradictions, respectively, the two remaining, more radical programmes, i.e. Hilbert's and Brouwer's, generated a great debate; the explanation given here is their mutual incommensurability, defined by means of the differences in their foundational features.ResultsThe ignorance of this phenomenon explains the inconclusiveness of a century-long debate between the advocates of these two proposals. Which however have been so greatly improved as to closely approach or even recognize some basic features of the FoM.Discussion on the resultsYet, no proposal has recognized the alternative basic feature to Hilbert's main one, the deductive organization of a theory, although already half a century before the births of all the programmes this alternative was substantially instantiated by Lobachevsky's theory on parallel lines. Some conclusive considerations of a historical and philosophical nature are offered. In particular, the conclusive birth of a pluralism in the FoM is stressed. (shrink)

We introduce the notion of a convex tree. We show that the binary expansion for real numbers in the unit interval ) is equivalent to weak König lemma ) for trees having at most two nodes at each level, and we prove that the intermediate value theorem is equivalent to \ for convex trees, in the framework of constructive reverse mathematics.

Hirst investigated a natural restriction of Hindman’s Finite Sums Theorem—called Hilbert’s Theorem—and proved it equivalent over \ to the Infinite Pigeonhole Principle for all colors. This gave the first example of a natural restriction of Hindman’s Theorem provably much weaker than Hindman’s Theorem itself. We here introduce another natural restriction of Hindman’s Theorem—which we name the Adjacent Hindman’s Theorem with apartness—and prove it to be provable from Ramsey’s Theorem for pairs and strictly stronger than Hirst’s Hilbert’s Theorem. The lower bound (...) is obtained by a direct combinatorial implication from the Adjacent Hindman’s Theorem with apartness to the Increasing Polarized Ramsey’s Theorem for pairs introduced by Dzhafarov and Hirst. In the Adjacent Hindman’s Theorem homogeneity is required only for finite sums of adjacent elements. (shrink)

It is a striking fact from reverse mathematics that almost all theorems of countable and countably representable mathematics are equivalent to just five subsystems of second order arithmetic. The standard view is that the significance of these equivalences lies in the set existence principles that are necessary and sufficient to prove those theorems. In this article I analyse the role of set existence principles in reverse mathematics, and argue that they are best understood as closure conditions on the powerset of (...) the natural numbers. (shrink)

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.

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.

The conservativeness argument poses a dilemma to deflationism about truth, according to which a deflationist theory of truth must be conservative but no adequate theory of truth is conservative. The debate on the conservativeness argument has so far been framed in a specific formal setting, where theories of truth are formulated over arithmetical base theories. I will argue that the appropriate formal setting for evaluating the conservativeness argument is provided not by theories of truth over arithmetic but by those over (...) subject matters ‘richer’ than arithmetic, such as set theory. The move to this new formal setting provides deflationists with better defence and brings a broader perspective to the debate. (shrink)

In this article we investigate whether the following conjecture is true or not: does the addition-free theta functions form a canonical notation system for the linear versions of Friedman’s well-partial-orders with the so-called gap-condition over a finite set of n labels. Rather surprisingly, we can show this is the case for two labels, but not for more than two labels. To this end, we determine the order type of the notation systems for addition-free theta functions in terms of ordinals less (...) than ε0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon _0$$\end{document}. We further show that the maximal order type of the Friedman ordering can be obtained by a certain ordinal notation system which is based on specific binary theta functions. (shrink)

We show how to interpret weak Kőnig's lemma in some recently defined theories of nonstandard arithmetic in all finite types. Two types of interpretations are described, with very different verifications. The celebrated conservation result of Friedman's about weak Kőnig's lemma can be proved using these interpretations. We also address some issues concerning the collecting of witnesses in herbrandized functional interpretations.

In this paper we study several translations that map models and formulae of the language of second-order arithmetic to models and formulae of the language of truth. These translations are useful because they allow us to exploit results from the extensive literature on arithmetic to study the notion of truth. Our purpose is to present these connections in a systematic way, generalize some well-known results in this area, and to provide a number of new results. Sections 3 and 4 contain (...) some recursion- and proof-theoretic results about Kripke-style fixed-point theories of truth. Section 5 shows how to derive full second-order arithmetic from principles of truth. Section 6 investigates the proof-theoretic strength of disquotation without an arithmetical base theory. (shrink)

The present volume is an introduction to the use of tools from computability theory and reverse mathematics to study combinatorial principles, in particular Ramsey's theorem and special cases such as Ramsey's theorem for pairs. It would serve as an excellent textbook for graduate students who have completed a course on computability theory.

First order reasoning about hyperintegers can prove things about sets of integers. In the author’s paper Nonstandard Arithmetic and Reverse Mathematics, Bulletin of Symbolic Logic 12 100–125, it was shown that each of the “big five” theories in reverse mathematics, including the base theory, has a natural nonstandard counterpart. But the counterpart of has a defect: it does not imply the Standard Part Principle that a set exists if and only if it is coded by a hyperinteger. In this paper (...) we find another nonstandard counterpart, *RCA0′, that does imply the Standard Part Principle. (shrink)

This book concerns the foundations of epistemic modality and hyperintensionality and their applications to the philosophy of mathematics. I examine 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 propositions, (...) and abstraction principles in the philosophy of mathematics; to the modal and hyperintensional profiles of the logic of rational intuition; and to the types of intention, when the latter is interpreted as a hyperintensional mental state. Chapter \textbf{2} argues for a novel type of expressivism based on the duality between the categories of coalgebras and algebras, and argues that the duality permits of the reconciliation between modal and hyperintensional cognitivism and modal and hyperintensional expressivism. I also develop a novel topic-sensitive truthmaker semantics for dynamic epistemic logic, and develop a novel dynamic two-dimensional semantics grounded in two-dimensional hyperintensional Turing machines. Chapter \textbf{3} provides an abstraction principle for epistemic (hyper-)intensions. Chapter \textbf{4} advances a topic-sensitive two-dimensional truthmaker semantics, and provides three novel interpretations of the framework along with the epistemic and metasemantic. Chapter \textbf{5} applies the fixed points of the modal $\mu$-calculus in order to account for the iteration of epistemic states in a single agent, by contrast to availing of modal axiom 4 (i.e. the KK principle). The fixed point operators in the modal $\mu$-calculus are rendered hyperintensional, which yields the first hyperintensional construal of the modal $\mu$-calculus in the literature and the first application of the calculus to the iteration of epistemic states in a single agent instead of the common knowledge of a group of agents. Chapter \textbf{6} advances a solution to the Julius Caesar problem based on Fine's `criterial' identity conditions which incorporate conditions on essentiality and grounding. Chapter \textbf{7} provides a ground-theoretic regimentation of the proposals in the metaphysics of consciousness and examines its bearing on the two-dimensional conceivability argument against physicalism. The topic-sensitive epistemic two-dimensional truthmaker semantics developed in chapters \textbf{2} and \textbf{4} are availed of in order for epistemic states to be a guide to metaphysical states in the hyperintensional setting. -/- Chapters \textbf{8-12} provide cases demonstrating how the two-dimensional hyperintensions of hyperintensional, i.e. topic-sensitive epistemic two-dimensional truthmaker, semantics, solve the access problem in the epistemology of mathematics. Chapter \textbf{8} examines the interaction between my hyperintensional semantics and the axioms of epistemic set theory, large cardinal axioms, the Epistemic Church-Turing Thesis, the modal axioms governing the modal profile of $\Omega$-logic, Orey sentences such as the Generalized Continuum Hypothesis, and absolute decidability. These results yield inter alia the first hyperintensional Epistemic Church-Turing Thesis and hyperintensional epistemic set theories in the literature. Chapter \textbf{9} examines the modal and hyperintensional commitments of abstractionism, in particular necessitism, and epistemic hyperintensionality, epistemic utility theory, and the epistemology of abstraction. I countenance a hyperintensional semantics for novel epistemic abstractionist modalities. I suggest, too, that observational type theory can be applied to first-order abstraction principles in order to make first-order abstraction principles recursively enumerable, i.e. Turing machine computable, and that the truth of the first-order abstraction principle for hyperintensions is grounded in its being possibly recursively enumerable and the machine being physically implementable. Chapter \textbf{10} examines the philosophical significance of hyperintensional $\Omega$-logic in set theory and discusses the hyperintensionality of metamathematics. Chapter \textbf{11} provides a modal logic for rational intuition and provides a hyperintensional semantics. Chapter \textbf{12} avails of modal coalgebras to interpret the defining properties of indefinite extensibility, and avails of hyperintensional epistemic two-dimensional semantics in order to account for the interaction between interpretational and objective modalities and the truthmakers thereof. This yields the first hyperintensional category theory in the literature. I invent a new mathematical trick in which first-order structures are treated as categories, and Vopenka's principle can be satisfied because of the elementary embeddings between the categories and generate Vopenka cardinals in the category of Set in category theory. Chapter \textbf{13} examines modal responses to the alethic paradoxes. I provide a counter-example to epistemic closure for logical deduction. Chapter \textbf{14} examines, finally, the modal and hyperintensional semantics for the different types of intention and the relation of the latter to evidential decision theory. (shrink)

This book concerns the foundations of epistemic modality and hyperintensionality and their applications to the philosophy of mathematics. I examine 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 propositions, (...) and abstraction principles in the philosophy of mathematics; to the modal and hyperintensional profiles of the logic of rational intuition; and to the types of intention, when the latter is interpreted as a hyperintensional mental state. Chapter \textbf{2} argues for a novel type of expressivism based on the duality between the categories of coalgebras and algebras, and argues that the duality permits of the reconciliation between modal and hyperintensional cognitivism and modal and hyperintensional expressivism. I also develop a novel topic-sensitive truthmaker semantics for dynamic epistemic logic, and develop a novel dynamic two-dimensional semantics grounded in two-dimensional hyperintensional Turing machines. Chapter \textbf{3} provides an abstraction principle for epistemic (hyper-)intensions. Chapter \textbf{4} advances a topic-sensitive two-dimensional truthmaker semantics, and provides three novel interpretations of the framework along with the epistemic and metasemantic. Chapter \textbf{5} applies the fixed points of the modal $\mu$-calculus in order to account for the iteration of epistemic states in a single agent, by contrast to availing of modal axiom 4 (i.e. the KK principle). The fixed point operators in the modal $\mu$-calculus are rendered hyperintensional, which yields the first hyperintensional construal of the modal $\mu$-calculus in the literature and the first application of the calculus to the iteration of epistemic states in a single agent instead of the common knowledge of a group of agents. Chapter \textbf{6} advances a solution to the Julius Caesar problem based on Fine's `criterial' identity conditions which incorporate conditions on essentiality and grounding. Chapter \textbf{7} provides a ground-theoretic regimentation of the proposals in the metaphysics of consciousness and examines its bearing on the two-dimensional conceivability argument against physicalism. The topic-sensitive epistemic two-dimensional truthmaker semantics developed in chapters \textbf{2} and \textbf{4} are availed of in order for epistemic states to be a guide to metaphysical states in the hyperintensional setting. -/- Chapters \textbf{8-12} provide cases demonstrating how the two-dimensional hyperintensions of hyperintensional, i.e. topic-sensitive epistemic two-dimensional truthmaker, semantics, solve the access problem in the epistemology of mathematics. Chapter \textbf{8} examines the interaction between my hyperintensional semantics and the axioms of epistemic set theory, large cardinal axioms, the Epistemic Church-Turing Thesis, the modal axioms governing the modal profile of $\Omega$-logic, Orey sentences such as the Generalized Continuum Hypothesis, and absolute decidability. These results yield inter alia the first hyperintensional Epistemic Church-Turing Thesis and hyperintensional epistemic set theories in the literature. Chapter \textbf{9} examines the modal and hyperintensional commitments of abstractionism, in particular necessitism, and epistemic hyperintensionality, epistemic utility theory, and the epistemology of abstraction. I countenance a hyperintensional semantics for novel epistemic abstractionist modalities. I suggest, too, that observational type theory can be applied to first-order abstraction principles in order to make first-order abstraction principles recursively enumerable, i.e. Turing machine computable, and that the truth of the first-order abstraction principle for hyperintensions is grounded in its being possibly recursively enumerable and the machine being physically implementable. Chapter \textbf{10} examines the philosophical significance of hyperintensional $\Omega$-logic in set theory and discusses the hyperintensionality of metamathematics. Chapter \textbf{11} provides a modal logic for rational intuition and provides a hyperintensional semantics. Chapter \textbf{12} avails of modal coalgebras to interpret the defining properties of indefinite extensibility, and avails of hyperintensional epistemic two-dimensional semantics in order to account for the interaction between interpretational and objective modalities and the truthmakers thereof. This yields the first hyperintensional category theory in the literature. I invent a new mathematical trick in which first-order structures are treated as categories, and Vopenka's principle can be satisfied because of the elementary embeddings between the categories and generate Vopenka cardinals in the category of Set in category theory. Chapter \textbf{13} examines modal responses to the alethic paradoxes. I provide a counter-example to epistemic closure for logical deduction. Chapter \textbf{14} examines, finally, the modal and hyperintensional semantics for the different types of intention and the relation of the latter to evidential decision theory. (shrink)

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 (...) main tenet. Ironically, already half a century before the births of these programs the alternative organization has been substantially represented by Lobachevsky's theory on parallel lines. Moreover, although each program’s founder recognised the basic features in a partial way only, all together these programs represented just the four possible foundational approaches. (shrink)

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.

The rather unrestrained use of second-order logic in the neo-logicist program is critically examined. It is argued in some detail that it brings with it genuine set-theoretical existence assumptions and that the mathematical power that Hume’s Principle seems to provide, in the derivation of Frege’s Theorem, comes largely from the ‘logic’ assumed rather than from Hume’s Principle. It is shown that Hume’s Principle is in reality not stronger than the very weak Robinson Arithmetic Q. Consequently, only a few rudimentary facts (...) of arithmetic are logically derivable from Hume’s Principle. And that hardly counts as a vindication of logicism. (shrink)

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.

In this paper we apply methods of proof mining to obtain a highly uniform effective rate of asymptotic regularity for the Ishikawa iteration associated with nonexpansive self-mappings of convex subsets of a class of uniformly convex geodesic spaces. Moreover, we show that these results are guaranteed by a combination of logical metatheorems for classical and semi-intuitionistic systems.

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.

In this paper we study the reverse mathematics of two theorems by Bonnet about partial orders. These results concern the structure and cardinality of the collection of initial intervals. The first theorem states that a partial order has no infinite antichains if and only if its initial intervals are finite unions of ideals. The second one asserts that a countable partial order is scattered and does not contain infinite antichains if and only if it has countably many initial intervals. We (...) show that the left to right directions of these theorems are equivalent to ACA0 and ATR0, respectively. On the other hand, the opposite directions are both provable in WKL0, but not in RCA0. We also prove the equivalence with ACA0 of the following result of Erdös and Tarski: a partial order with no infinite strong antichains has no arbitrarily large finite strong antichains. (shrink)

Let f be a computable function from finite sequences of 0ʼs and 1ʼs to real numbers. We prove that strong f-randomness implies strong f-randomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that f-randomness relative to a (...) PA-degree implies strong f-randomness, hence f-randomness does not imply f-randomness relative to a PA-degree. (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.

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.

The aim of this article is to give the proof-theoretic analysis of various subsystems of Feferman's theory T1 for explicit mathematics which contain the non-constructive μ-operator and join. We make use of standard proof-theoretic techniques such as cut-elimination of appropriate semiformal systems and asymmetrical interpretations in standard structures for explicit mathematics.

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 (...) ordinal. In all cases, the exact strength depends on what forms of induction are admitted in the respective systems. (shrink)

Continuing the earlier research from [T. Bigorajska, H. Kotlarski, Partitioning α-large sets: some lower bounds, Trans. Amer. Math. Soc. 358 4981–5001] we show that for the price of multiplying the number of parts by 3 we may construct partitions all of whose homogeneous sets are much smaller than in [T. Bigorajska, H. Kotlarski, Partitioning α-large sets: some lower bounds, Trans. Amer. Math. Soc. 358 4981–5001]. We also show that the Paris–Harrington independent statement remains unprovable if the number of colors is (...) restricted to 2, in fact, the statement is unprovable in IΣb. Other results concern some lower bounds for partitions of pairs. (shrink)

The topic of this paper is our knowledge of the natural numbers, and in particular, our knowledge of the basic axioms for the natural numbers, namely the Peano axioms. The thesis defended in this paper is that knowledge of these axioms may be gained by recourse to judgements of probability. While considerations of probability have come to the forefront in recent epistemology, it seems safe to say that the thesis defended here is heterodox from the vantage point of traditional philosophy (...) of mathematics. So this paper focuses on providing a preliminary defense of this thesis, in that it focuses on responding to several objections. Some of these objections are from the classical literature, such as Frege's concern about indiscernibility and circularity, while other are more recent, such as Baker's concern about the unreliability of small samplings in the setting of arithmetic. Another family of objections suggests that we simply do not have access to probability assignments in the setting of arithmetic, either due to issues related to the~$\omega$-rule or to the non-computability and non-continuity of probability assignments. Articulating these objections and the responses to them involves developing some non-trivial results on probability assignments, such as a forcing argument to establish the existence of continuous probability assignments that may be computably approximated. In the concluding section, two problems for future work are discussed: developing the source of arithmetical confirmation and responding to the probabilistic liar. (shrink)

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 (...) from contemporary mathematical logic. It is argued that the theory-based versions of such logicism are either too liberal (the plethora problem) or are committed to intuitively incorrect closure conditions (the consistency problem). Structure-based versions must on the other hand respond to a charge of begging the question (the circularity problem) or explain how one may have a knowledge of structure in advance of a knowledge of axioms (the signature problem). This discussion is significant because it gives us a better idea of what a notion of representation must look like if it is to aid in realizing some of the traditional epistemic aims of logicism in the philosophy of mathematics. (shrink)

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 (...) corresponding to weak Königʼs lemma is the universal transfer principle from Nonstandard Analysis. Here, we consider the intermediate and mean value theorem and their uniform generalizations. We show that ERNAʼs Reverse Mathematics mirrors the situation in classical Reverse Mathematics. This further supports our claim from Sanders [19] that the Reverse Mathematics of ERNA plus universal transfer is a copy up to infinitesimals of that of WKL0. We discuss some of the philosophical implications of our results. (shrink)

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.

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)