Gödel's two incompleteness theorems are among the most important results in modern logic, and have deep implications for various issues. They concern the limits of provability in formal axiomatic theories. The first incompleteness theorem states that in any consistent formal system F within which a certain amount of arithmetic can be carried out, there are statements of the language of F which can neither be proved nor disproved in F. According to the second incompleteness theorem, such a formal system cannot (...) prove that the system itself is consistent (assuming it is indeed consistent). These results have had a great impact on the philosophy of mathematics and logic. There have been attempts to apply the results also in other areas of philosophy such as the philosophy of mind, but these attempted applications are more controversial. The present entry surveys the two incompleteness theorems and various issues surrounding them. (shrink)

Hilbert’s program was an ambitious and wide-ranging project in the philosophy and foundations of mathematics. In order to “dispose of the foundational questions in mathematics once and for all,” Hilbert proposed a two-pronged approach in 1921: first, classical mathematics should be formalized in axiomatic systems; second, using only restricted, “finitary” means, one should give proofs of the consistency of these axiomatic systems. Although Gödel’s incompleteness theorems show that the program as originally conceived cannot be carried out, it had many partial (...) successes, and generated important advances in logical theory and metatheory, both at the time and since. The article discusses the historical background and development of Hilbert’s program, its philosophical underpinnings and consequences, and its subsequent development and influences since the 1930s. (shrink)

Logic has pride of place in mathematics and its 20th century offshoot, computer science. Modern symbolic logic was developed, in part, as a way to provide a formal framework for mathematics: Frege, Peano, Whitehead and Russell, as well as Hilbert developed systems of logic to formalize mathematics. These systems were meant to serve either as themselves foundational, or at least as formal analogs of mathematical reasoning amenable to mathematical study, e.g., in Hilbert’s consistency program. Similar efforts continue, but have been (...) expanded by the development of sophisticated methods to study the properties of such systems using proof and model theory. In parallel with this evolution of logical formalisms as tools for articulating mathematical theories (broadly speaking), much progress has been made in the quest for a mechanization of logical inference and the investigation of its theoretical limits, culminating recently in the development of new foundational frameworks for mathematics with sophisticated computer-assisted proof systems. In addition, logical formalisms developed by logicians in mathematical and philosophical contexts have proved immensely useful in describing theories and systems of interest to computer scientists, and to some degree, vice versa. Three examples of the influence of logic in computer science are automated reasoning, computer verification, and type systems for programming languages. (shrink)

Tarski, Carnap and Quine spent the academic year 1940?1941 together at Harvard. In their autobiographies, both Carnap and Quine highlight the importance of the conversations that took place among them during the year. These conversations centred around semantical issues related to the analytic/synthetic distinction and on the project of a finitist/nominalist construction of mathematics and science. Carnap's Nachlaß in Pittsburgh contains a set of detailed notes, amounting to more than 80 typescripted pages, taken by Carnap while these discussions were taking (...) place. In my article, I present a survey of these notes with special emphasis on Tarski's rejection of the analytic/synthetic distinction, the passage from typed languages to first-order languages, Tarski's finitism/nominalism, and the construction of a finitist language for mathematics and science. (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)

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.

The purpose of this article is to explain why I believe that the Continuum Hypothesis (CH) is not a definite mathematical problem. My reason for that is that the concept of arbitrary set essential to its formulation is vague or underdetermined and there is no way to sharpen it without violating what it is supposed to be about. In addition, there is considerable circumstantial evidence to support the view that CH is not definite.

We introduce an effective translation from proofs in the display calculus to proofs in the labelled calculus in the context of tense logics. We identify the labelled calculus proofs in the image of this translation as those built from labelled sequents whose underlying directed graph possesses certain properties. For the basic normal tense logic Kt, the image is shown to be the set of all proofs in the labelled calculus G3Kt.

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.

In this paper I propose a position in the ontology of mathematics which is inspired mainly by a case study in the mathematical discipline if-theory. The main theses of this position are that mathematical objects are introduced by mathematicians and that after mathematical objects have been introduced, they exist as objectively accessible abstract objects.

Hilbert’s program in the philosophy of mathematics comes in two parts. One part is a technical part. To carry out this part of the program one has to prove a certain technical result. The other part of the program is a philosophical part. It is concerned with philosophical questions that are the real aim of the program. To carry out this part one, basically, has to show why the technical part answers the philosophical questions one wanted to have answered. Hilbert (...) probably thought that he had completed the philosophical part of his program, maybe up to a few details. What was left to do was the technical part. To carry it out one, roughly, had to give a precise axiomatization of mathematics and show that it is consistent on purely finitistic grounds. This would come down to giving a relative consistency proof of mathematics in finitist mathematics, or to give a proof-theoretic reduction of mathematics on to finitist mathematics (we will look at these notions in more detail soon). It is widely believed that Gödel’s theorems showed that the technical part of Hilbert’s program could not be carried out. Gödel’s theorems show that the consistency of arithmetic can not even be proven in arithmetic, not to speak of by finitistic means alone. So, the technical part of Hilbert’s program is hopeless, and since Hilbert’s program essentially relied on both the technical and the philosophical part, Hilbert’s program as a whole is hopeless. Justified as this attitude is, it is a bit unfortunate. It is unfortunate because it takes away too much attention from the philosophical part of Hilbert’s program. And this is unfortunate for two reasons. (shrink)

In this paper, I consider an argument for the claim that any satisfactory epistemology of mathematics will violate core tenets of naturalism, i.e. that mathematics cannot be naturalized. I find little reason for optimism that the argument can be effectively answered.

A debated issue in the mathematical foundations in at least the last two decades is whether one can plausibly argue for the merits of treating undecidable questions of mathematics, e.g., the Continuum Hypothesis (CH), by relying on the existence of a plurality of set-theoretical universes except for a single one, i.e., the well-known set-theoretical universe V associated with the cumulative hierarchy of sets. The multiverse approach has some varying versions of the general concept of multiverse yet my intention is to (...) primarily address ontological multiversism as advocated, for instance, by Hamkins or Väätänen, precisely for the reason that they proclaim, to the one or the other extent, ontological preoccupations for the introduction of respective multiverse theories. Taking also into account Woodin’s and Steel’s multiverse versions, I take up an argumentation against multiversism, and in a certain sense against platonism in mathematical foundations, mainly on subjectively founded grounds, while keeping an eye on Clarke-Doane’s concern with Benacerraf’s challenge. I note that even though the paper is rather technically constructed in arguing against multiversism, the non-negligible philosophical part is influenced to a certain extent by a phenomenologically motivated view of the matter. (shrink)

Frege’s Grundgesetze der Arithmetik is formally inconsistent. This system is, except for minor differences, second-order logic together with an abstraction operator governed by Frege’s Axiom V. A few years ago, Richard Heck showed that the ramified predicative second-order fragment of the Grundgesetze is consistent. In this paper, we show that the above fragment augmented with the axiom of reducibility for concepts true of only finitely many individuals is still consistent, and that elementary Peano arithmetic (and more) is interpretable in this (...) extended system. (shrink)

This paper argues that Philip Kitcher's epistemology of mathematics, codified in his Naturalistic Constructivism, is not naturalistic on Kitcher's own conception of naturalism. Kitcher's conception of naturalism is committed to (i) explaining the correctness of belief-regulating norms and (ii) a realist notion of truth. Naturalistic Constructivism is unable to simultaneously meet both of these commitments.

Machines were introduced as calculating devices to simulate operations carried out by human computers following fixed algorithms. The mathematical study of (paper) machines is the topic of our essay. The first three sections provide necessary logical background, examine the analyses of effective calculability given in the thirties, and describe results that are central to recursion theory, reinforcing the conceptual analyses. In the final section we pursue our investigation in a quite different way and focus on principles that govern the operations (...) of physically realizable machines. (shrink)

Reverse mathematics studies which subsystems of second order arithmetic are equivalent to key theorems of ordinary, non-set-theoretic mathematics. The main philosophical application of reverse mathematics proposed thus far is foundational analysis, which explores the limits of different foundations for mathematics in a formally precise manner. This paper gives a detailed account of the motivations and methodology of foundational analysis, which have heretofore been largely left implicit in the practice. It then shows how this account can be fruitfully applied in the (...) evaluation of major foundational approaches by a careful examination of two case studies: a partial realization of Hilbert’s program due to Simpson [1988], and predicativism in the extended form due to Feferman and Schütte. -/- Shore [2010, 2013] proposes that equivalences in reverse mathematics be proved in the same way as inequivalences, namely by considering only omega-models of the systems in question. Shore refers to this approach as computational reverse mathematics. This paper shows that despite some attractive features, computational reverse mathematics is inappropriate for foundational analysis, for two major reasons. Firstly, the computable entailment relation employed in computational reverse mathematics does not preserve justification for the foundational programs above. Secondly, computable entailment is a Pi-1-1 complete relation, and hence employing it commits one to theoretical resources which outstrip those available within any foundational approach that is proof-theoretically weaker than Pi-1-1-CA0. (shrink)

The paper exposes the philosophical and mathematical flaws in an attempt to settle the continuum problem by a new class of axioms based on probabilistic reasoning. I also examine the larger proposal behind this approach, namely the introduction of new primitive notions that would supersede the set theoretic foundation of mathematics.

A standard formalization of a scientific theory is a system of axioms for that theory in a first-order language (possibly many-sorted; possibly with the membership primitive $$\in$$ ). Suppes (in: Carvallo M (ed) Nature, cognition and system II. Kluwer, Dordrecht, 1992) expressed skepticism about whether there is a “simple or elegant method” for presenting mathematicized scientific theories in such a standard formalization, because they “assume a great deal of mathematics as part of their substructure”. The major difficulties amount to these. (...) First, as the theories of interest are mathematicized, one must specify the underlying applied mathematics base theory, which the physical axioms live on top of. Second, such theories are typically geometric, concerning quantities or trajectories in space/time: so, one must specify the underlying physical geometry. Third, the differential equations involved generally refer to coordinate representations of these physical quantities with respect to some implicit coordinate chart, not to the original quantities. These issues may be resolved. Once this is done, constructing standard formalizations is not so difficult—at least for the theories where the mathematics has been worked out rigorously. Here we give what may be claimed to be a simple and elegant means of doing that. This is for mathematicized scientific theories comprising differential equations for $$\mathbb{R}$$ -valued quantities Q (that is, scalar fields), defined on n (“spatial” or “temporal”) dimensions, taken to be isomorphic to the usual Euclidean space $$\mathbb{R}^n$$. For illustration, I give standard (in a sense, “text-book”) formalizations: for the simple harmonic oscillator equation in one-dimension and for the Laplace equation in two dimensions. (shrink)

It is well-known that the global structure of every space-time model for relativistic cosmology is observationally underdetermined. In order to alleviate the severity of this underdetermination, it has been proposed that we adopt the Cosmological Principle because the Principle restricts our attention to a distinguished class of space-time models (spatially homogeneous and isotropic models). I argue that, even assuming the Cosmological Principle, the topology of space remains observationally underdetermined. Nonetheless, I argue that we can muster reasons to prefer various topological (...) properties over others. In particular, I favor the adoption of multiply connected universe models on grounds of (i) simplicity, (ii) Machian considerations, and (iii) explanatory power. We are able to appeal to such grounds because multiply connected topologies open up the possibility of finite universe models (consistent with our best data), which in turn avoid thorny issues concerning the postulation of an actually infinite universe. (shrink)

When I was a teenager growing up in Los Angeles in the early 1940s, my dream was to become a mathematical physicist: I was fascinated by the ideas of relativity theory and quantum mechanics, and I read popular expositions which, in those days, besides Einstein’s The Meaning of Relativity, was limited to books by the likes of Arthur S. Eddington and James Jeans. I breezed through the high-school mathematics courses (calculus was not then on offer, and my teachers barely understood (...) it), but did less well in physics, which I should have taken as a reality check. On the philosophical side I read a mixed bag of Bertrand Russell, John Dewey and Alfred Korzybski (the missionary for “General Semantics” in Science and Sanity, a mish-mash of the theory of types, non-. (shrink)

I argue that contemporary set theory, as depicted in the 2011–2012 EFI lecture series, lacks a program that promises to decide, in a genuinely realist fashion, the continuum hypothesis (CH) and related questions about the “width” of the universe. We can distinguish three possible objectives for a realist completion of set theory: maximizing structures, maximizing sets, and maximizing interpretive power. However, none of these is allied to a program that can plausibly decide CH. I discuss the implications of this for (...) set theory and other foundational programs. (shrink)

In his book Shadows of the Mind: A search for the missing science of con- sciousness [SM below], Roger Penrose has turned in another bravura perfor- mance, the kind we have come to expect ever since The Emperor’s New Mind [ENM ] appeared. In the service of advancing his deep convictions and daring conjectures about the nature of human thought and consciousness, Penrose has once more drawn a wide swath through such topics as logic, computa- tion, artificial intelligence, quantum physics (...) and the neuro-physiology of the brain, and has produced along the way many gems of exposition of difficult mathematical and scientific ideas, without condescension, yet which should be broadly appealing. 1 While the aims and a number of the topics in SM are the same as in ENM, the focus now is much more on the two axes that Pen- rose grinds in earnest. Namely, in the first part of SM he argues anew and at great length against computational models of the mind and more specifi- cally against any account of mathematical thought in computational terms. Then in the second part, he argues that there must be a scientific account of consciousness but that will require a (still to be found) non-computational extension or modification of present-day quantum physics. (shrink)