This monograph offers a fresh perspective on the applicability of mathematics in science. It explores what mathematics must be so that its applications to the empirical world do not constitute a mystery. In the process, readers are presented with a new version of mathematical structuralism. The author details a philosophy of mathematics in which the problem of its applicability, particularly in physics, in all its forms can be explained and justified. Chapters cover: mathematics as a formal science, mathematical ontology: what (...) does it mean to exist, mathematical structures: what are they and how do we know them, how different layers of mathematical structuring relate to each other and to perceptual structures, and how to use mathematics to find out how the world is. The book simultaneously develops along two lines, both inspired and enlightened by Edmund Husserl’s phenomenological philosophy. One line leads to the establishment of a particular version of mathematical structuralism, free of “naturalist” and empiricist bias. The other leads to a logical-epistemological explanation and justification of the applicability of mathematics carried out within a unique structuralist perspective. This second line points to the “unreasonable” effectiveness of mathematics in physics as a means of representation, a tool, and a source of not always logically justified but useful and effective heuristic strategies. (shrink)

This paper outlines an account of numbers based on the numerical equivalence schema (NES), which consists of all sentences of the form ‘#x.Fx=n if and only if ∃nx Fx’, where # is the number-of operator and ∃n is defined in standard Russellian fashion. In the first part of the paper, I point out some analogies between the NES and the T-schema for truth. In light of these analogies, I formulate a minimalist account of numbers, based on the NES, which strongly (...) parallels the minimalist (deflationary) account of truth. One may be tempted to develop the minimalist account in a fictionalist direction, according to which arithmetic is useful but untrue, if taken at face value. In the second part, I argue that this suggestion is not as attractive as it may first appear. The NES suffers from a similar problem to the T-schema: it is deductively weak and does not enable the derivation of any non-trivial generalizations. In the third part of the paper, I explore some strategies to deal with the generalization problem, again drawing inspiration from the literature on truth. In closing this paper, I briefly compare the minimalist to some other accounts of numbers. (shrink)

This article presents an analysis of Gödel's dialectica interpretation via a refinement of intuitionistic logic known as linear logic. Linear logic comes naturally into the picture once one observes that the structural rule of contraction is the main cause of the lack of symmetry in Gödel's interpretation. We use the fact that the dialectica interpretation of intuitionistic logic can be viewed as a composition of Girard's embedding of intuitionistic logic into linear logic followed by de Paiva's dialectica interpretation of linear (...) logic. We then investigate the various properties of the dialectica interpretation, such as the characterisation theorem, and variants of Gödel's interpretation within the linear logic context. The role of contraction in extensions to classical logic, arithmetic and analysis is also discussed. (shrink)

Canonical Propositional Gentzen-type systems are systems which in addition to the standard axioms and structural rules have only pure logical rules with the sub-formula property, in which exactly one occurrence of a connective is introduced in the conclusion, and no other occurrence of any connective is mentioned anywhere else. In this paper we considerably generalize the notion of a “canonical system” to first-order languages and beyond. We extend the Propositional coherence criterion for the non-triviality of such systems to rules with (...) unary quantifiers and show that it remains constructive. Then we provide semantics for such canonical systems using 2-valued non-deterministic matrices extended to languages with quantifiers, and prove that the following properties are equivalent for a canonical system G: (1) G admits Cut-Elimination, (2) G is coherent, and (3) G has a characteristic 2-valued non-deterministic matrix. (shrink)

With quantifier elimination and restriction of language to a binary relation symbol and constant symbols it is shown that countable complete theories having three isomorphism types of countable models are "essentially" the Ehrenfeucht example [4, $\s6$ ].

A box type is an n-type of an o-minimal structure which is uniquely determined by the projections to the coordinate axes. We characterize heirs of box types of a polynomially bounded o-minimal structure M. From this, we deduce various structure theorems for subsets of $M^k $ , definable in the expansion M of M by all convex subsets of the line. We show that M after naming constants, is model complete provided M is model complete.

§1. Iterated Gödelian extensions of theories. The idea of iterating ad infinitum the operation of extending a theory T by adding as a new axiom a Gödel sentence for T, or equivalently a formalization of “T is consistent”, thus obtaining an infinite sequence of theories, arose naturally when Godel's incompleteness theorem first appeared, and occurs today to many non-specialists when they ponder the theorem. In the logical literature this idea has been thoroughly explored through two main approaches. One is that (...) initiated by Turing in his “ordinal logics” and taken very much further in Feferman's work on transfinite progressions, which also introduced the more general study of extensions by reflection principles, of which consistency statements are a special case. This approach starts from an assignment of theories to ordinal notations, and extracts sequences of theories through a suitable choice of a path in the set of ordinal notations. The second approach, illustrated in particular by the work of Schmerl and Beklemishev, starts instead from a suitably well-behaved primitive recursive well-ordering, which is used to define a sequence of theories. This second approach has led to precise results about the relative proof-theoretical strength of sequences of theories obtained by iterating different reflection principles. The Turing-Feferman approach, on the other hand, lends itself well to an investigation in qualitative and philosophical terms of the relevance of such iterated reflection extensions to mathematical knowledge, in particular because of two developments associated with this approach. (shrink)

The purpose of this paper is to investigate continuity properties arising in elementary (i.e., first-order) logic in the hope of illuminating the special status of this logic. The continuity properties turn out to be closely related to conditions which characterize elementary logic uniquely, and lead to various further questions.

In the present paper I wish to regard constructivelogic as a self-contained system for the treatment ofepistemological issues; the explanations of theconstructivist logical notions are cast in anepistemological mold already from the outset. Thediscussion offered here intends to make explicit thisimplicit epistemic character of constructivism.Particular attention will be given to the intendedinterpretation laid down by Heyting. This interpretation, especially as refined in the type-theoretical work of Per Martin-Löf, puts thesystem on par with the early efforts of Frege andWhitehead-Russell. This quite (...) recent work, however,has proved valuable not only in the philosophy andfoundations of mathematics, but has also foundpractical application in computer science, where thelanguage of constructivism serves as an implementableprogramming language, and within the philosophy oflanguage.\footnote{Nordstr\"{o}m et al. give an overview of the work in computerscience, whereas Ranta provides an impressiveconstructivist alternative to Montague Grammar usingthe richer type structure of Martin-L\"{o}f in placeof the simple classical type theory of Church.} Mypresentation will be carried out through a contrastwith standard metamathematical work.\footnote{Troelstra and van Dalen give an encyclopedictreatment of the metamathematics of constructivism.}In the course of the development I have occasion tooffer some novel considerations on thenature of proof and inference. (shrink)

The main result proved in the paper is that on every recursive structure the intrinsically hyperarithmetical sets coincide with the relatively intrinsically hyperarithmetical sets. As a side effect of the proof an effective version of the Kueker's theorem on definability by means of infinitary formulas is obtained.

An external characterization of the inductive sets on countable abstract structures is presented. The main result is an abstract version of the classical Suslin-Kleene characterization of the hyperarithmetical sets.

We consider the informal concept of "computability" or "effective calculability" and two of the formalisms commonly used to define it, "(Turing) computability" and "(general) recursiveness". We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas. After a careful (...) historical and conceptual analysis of computability and recursion we make several recommendations in section §7 about preserving the intensional differences between the concepts of "computability" and "recursion." Specifically we recommend that: the term "recursive" should no longer carry the additional meaning of "computable" or "decidable;" functions defined using Turing machines, register machines, or their variants should be called "computable" rather than "recursive;" we should distinguish the intensional difference between Church's Thesis and Turing's Thesis, and use the latter particularly in dealing with mechanistic questions; the name of the subject should be "Computability Theory" or simply Computability rather than "Recursive Function Theory.". (shrink)

A well known fact is that every Lebesgue measurable set is regular, i.e., it includes an F$_{\sigma}$ set of the same measure. We analyze this fact from a metamathematical or foundational standpoint. We study a family of Muchnik degrees corresponding to measure-theoretic regularity at all levels of the effective Borel hierarchy. We prove some new results concerning Nies's notion of LR-reducibility. We build some $\omega$-models of RCA$_0$which are relevant for the reverse mathematics of measure-theoretic regularity.

This paper outlines an account of numbers based on the numerical equivalence schema, which consists of all sentences of the form ‘#x.Fx=n if and only if ∃nx Fx’, where # is the number-of operator and ∃n is defined in standard Russellian fashion. In the first part of the paper, I point out some analogies between the NES and the T-schema for truth. In light of these analogies, I formulate a minimalist account of numbers, based on the NES, which strongly parallels (...) the minimalist account of truth. One may be tempted to develop the minimalist account in a fictionalist direction, according to which arithmetic is useful but untrue, if taken at face value. In the second part, I argue that this suggestion is not as attractive as it may first appear. The NES suffers from a similar problem to the T-schema: it is deductively weak and does not enable the derivation of any non-trivial generalizations. In the third part of the paper, I explore some strategies to deal with the generalization problem, again drawing inspiration from the literature on truth. In closing this paper, I briefly compare the minimalist to some other accounts of numbers. (shrink)

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)

Model theory is concerned mainly, although not exclusively, with infinite structures. In recent years, finite structures have risen to greater prominence, both within the context of mainstream model theory, e.g., in work of Lachlan, Cherlin, Hrushovski, and others, and with the advent of finite model theory, which incorporates elements of classical model theory, combinatorics, and complexity theory. The purpose of this survey is to provide an overview of what might be called the model theory of finite structures. Some topics in (...) finite model theory have strong connections to theoretical computer science, especially descriptive complexity theory. In fact, it has been suggested that finite model theory really is, or should be, logic for computer science. These connections with computer science will, however, not be treated here.It is well-known that many classical results of ‘infinite model theory’ fail over the class of finite structures, including the compactness and completeness theorems, as well as many preservation and interpolation theorems. The failure of compactness in the finite, in particular, means that the standard proofs of many theorems are no longer valid in this context. At present, there is no known example of a classical theorem that remains true over finite structures, yet must be proved by substantially different methods. It is generally concluded that first-order logic is ‘badly behaved’ over finite structures.From the perspective of expressive power, first-order logic also behaves badly: it is both too weak and too strong. Too weak because many natural properties, such as the size of a structure being even or a graph being connected, cannot be defined by a single sentence. Too strong, because every class of finite structures with a finite signature can be defined by an infinite set of sentences. Even worse, every finite structure is defined up to isomorphism by a single sentence. In fact, it is perhaps because of this last point more than anything else that model theorists have not been very interested in finite structures. Modern model theory is concerned largely with complete first-order theories, which are completely trivial here. (shrink)

Completeness and other forms of Zorn’s Lemma are sometimes invoked for semantic proofs of conservation in relatively elementary mathematical contexts in which the corresponding syntactical conservation would suffice. We now show how a fairly general syntactical conservation theorem that covers plenty of the semantic approaches follows from an utmost versatile criterion for conservation given by Scott in 1974.To this end we work with multi-conclusion entailment relations as extending single-conclusion entailment relations. In a nutshell, the additional axioms with disjunctions in positive (...) position can be eliminated by reducing them to the corresponding disjunction elimination rules, which in turn prove admissible in all known mathematical instances. In deduction terms this means to fold up branchings of proof trees by way of properties of the relevant mathematical structures.Applications include the syntactical counterparts of the theorems or lemmas known under the names of Artin–Schreier, Krull–Lindenbaum, and Szpilrajn. Related work has been done before on individual instances, e.g., in locale theory, dynamical algebra, formal topology and proof analysis. (shrink)

The context for this paper is Feferman's theory of explicit mathematics, a formal framework serving many purposes. It is suitable for representing Bishop-style constructive mathematics as well as generalized recursion, including direct expression of structural concepts which admit self-application. The object of investigation here is the theory of explicit mathematics augmented by the monotone fixed point principle, which asserts that any monotone operation on classifications (Feferman's notion of set) possesses a least fixed point. To be more precise, the new axiom (...) not merely postulates the existence of a least solution, but, by adjoining a new functional constant to the language, it is ensured that a fixed point is uniformly presentable as a function of the monotone operation. The upshot of the paper is that the latter extension of explicit mathematics (when based on classical logic) embodies considerable proof-theoretic strength. It is shown that it has at least the strength of the subsystem of second order arithmetic based on Π 1 2 comprehension. (shrink)

We use a new version of the Definability Theorem of Beth in order to unify classical theorems of Yuri Matiyasevich and Jan Denef in one structural statement. We give similar forms for other important definability results from Arithmetic and Number Theory.

Kochen and Specker’s theorem can be seen as a consequence of Gleason’s theorem and logical compactness. Similar compactness arguments lead to stronger results about finite sets of rays in Hilbert space, which we also prove by a direct construction. Finally, we demonstrate that Gleason’s theorem itself has a constructive proof, based on a generic, finite, effectively generated set of rays, on which every quantum state can be approximated. r 2003 Elsevier Ltd. All rights reserved.

Truth predicates are widely believed to be capable of serving a certain logical or quasi-logical function. There is little consensus, however, on the exact nature of this function. We offer a series of formal results in support of the thesis that disquotational truth is a device to simulate higher-order resources in a first-order setting. More specifically, we show that any theory formulated in a higher-order language can be naturally and conservatively interpreted in a first-order theory with a disquotational truth or (...) truth-of predicate. In the first part of the paper we focus on the relation between truth and full impredicative sentential quantification. The second part is devoted to the relation between truth-of and full impredicative predicate quantification. (shrink)

Proofs of Gödel's First Incompleteness Theorem are often accompanied by claims such as that the gödel sentence constructed in the course of the proof says of itself that it is unprovable and that it is true. The validity of such claims depends closely on how the sentence is constructed. Only by tightly constraining the means of construction can one obtain gödel sentences of which it is correct, without further ado, to say that they say of themselves that they are unprovable (...) and that they are true; otherwise a false theory can yield false gödel sentences. (shrink)

We prove that the minimal Logic of Formal Inconsistency $\mathsf{QmbC}$ validates a weaker version of Fraïssé’s theorem. LFIs are paraconsistent logics that relativize the Principle of Explosion only to consistent formulas. Now, despite the recent interest in LFIs, their model-theoretic properties are still not fully understood. Our aim in this paper is to investigate the situation. Our interest in FT has to do with its fruitfulness; the preservation of FT indicates that a number of other classical semantic properties can be (...) also salvaged in LFIs. Further, given that FT depends on truth-functionality, whether full FT holds for $\mathsf{QmbC}$ becomes a challenging question. (shrink)

I present a reconstruction of the logical system of the Tractatus, which differs from classical logic in two ways. It includes an account of Wittgenstein’s “form-series” device, which suffices to express some effectively generated countably infinite disjunctions. And its attendant notion of structure is relativized to the fixed underlying universe of what is named. -/- There follow three results. First, the class of concepts definable in the system is closed under finitary induction. Second, if the universe of objects is countably (...) infinite, then the property of being a tautology is \Pi^1_1-complete. But third, it is only granted the assumption of countability that the class of tautologies is \Sigma_1-definable in set theory. -/- Wittgenstein famously urges that logical relationships must show themselves in the structure of signs. He also urges that the size of the universe cannot be prejudged. The results of this paper indicate that there is no single way in which logical relationships could be held to make themselves manifest in signs, which does not prejudge the number of objects. (shrink)

La parution de la monographic de Sneed,The Logical Structure of Mathematical Physics a suscité un renouveau d'intérêt en philosophie contemporaine des sciences. Cet ouvrage arrivait à un moment où l'épistémologie des sciences, telle que développée dans les milieux germaniques et anglo-saxons, accusait de graves insuffisances dans la reconstruction rationnelle du développement historique des théories physiques. Mis sur la défensive par les thèses et arguments historiques de Kuhn et de Feyerabend, ces milieux « orthodoxes » devaient reconnaitre l'état embryonnaire de ce (...) qui devait être uneépistémologie diachroniquedes sciences, une épistémologie du changement scientifique où les méthodes d'analyse formelle puissent être aussi mises á contribution. A cela s'ajoutait un certain malaise, une certaine stagnation de la problématique, plus synchronique, de l'approche traditionnelle issue du mouvement empiriste logique. Le probleme de la dichotomielangage théorique—langage observationnel, ainsi que son fidèle compagnon, le problème destermes théoriques, le statut épistémologique desrègies de correspondance, la dèfinition du concept d'analyticitéen science, autant de questions qui avaient été discutées et critiquées, à maintes reprises, pour aboutir à des résultats peu concluants aux yeux des philosophes, comme à ceux des physiciens préoccupés des fondements de leur discipline et à qui la teneur de cette discussion semblait souvent étrangère à la pratique scientifique. (shrink)

ABSTRACTIn this paper, we present a generalisation of proof simulation procedures for Frege systems by Bonet and Buss to some logics for which the deduction theorem does not hold. In particular, we study the case of finite-valued Łukasiewicz logics. To this end, we provide proof systems and which augment Avron's Frege system HŁuk with nested and general versions of the disjunction elimination rule, respectively. For these systems, we provide upper bounds on speed-ups w.r.t. both the number of steps in proofs (...) and the length of proofs. We also consider Tamminga's natural deduction and Avron's hypersequent calculus GŁuk for 3-valued Łukasiewicz logic and generalise our results considering the disjunction elimination rule to all finite-valued Łukasiewicz logics. (shrink)

For a primitive recursive consistent and strong enough theory T we construct an independent statement which has some clear metamathematical meaning.

Set theory is an autonomous and sophisticated field of mathematics, enormously successful not only at its continuing development of its historical heritage but also at analyzing mathematical propositions cast in set-theoretic terms and gauging their consistency strength. But set theory is also distinguished by having begun intertwined with pronounced metaphysical attitudes, and these have even been regarded as crucial by some of its great developers. This has encouraged the exaggeration of crises in foundations and of metaphysical doctrines in general. However, (...) set theory has proceeded in the opposite direction, from a web of intensions to a theory of extensionpar excellence, and like other fields of mathematics its vitality and progress have depended on a steadily growing core of mathematical structures and methods, problems and results. There is also the stronger contention that from the beginning set theory actually developed through a progression ofmathematicalmoves, whatever and sometimes in spite of what has been claimed on its behalf.What follows is an account of the development of set theory from its beginnings through the creation of forcing based on these contentions, with an avowedly Whiggish emphasis on the heritage that has been retained and developed by current set theory. The whole transfinite landscape can be viewed as the result of Cantor's attempt to articulate and solve the Continuum Problem. (shrink)

This article serves to present a large mathematical perspective and historical basis for the Axiom of Replacement as well as to affirm its importance as a central axiom of modern set theory.

In this study, we prove the completeness and cut-elimination theorems for a first-order extension F4CC of Arieli, Avron, and Zamansky’s ideal paraconsistent four-valued logic known as 4CC. These theorems are proved using Schütte’s method, which can simultaneously prove completeness and cut-elimination.