The period from 1900 to 1935 was particularly fruitful and important for the development of logic and logical metatheory. This survey is organized along eight "itineraries" concentrating on historically and conceptually linked strands in this development. Itinerary I deals with the evolution of conceptions of axiomatics. Itinerary II centers on the logical work of Bertrand Russell. Itinerary III presents the development of set theory from Zermelo onward. Itinerary IV discusses the contributions of the algebra of logic tradition, in particular, Löwenheim (...) and Skolem. Itinerary V surveys the work in logic connected to the Hilbert school, and itinerary V deals specifically with consistency proofs and metamathematics, including the incompleteness theorems. Itinerary VII traces the development of intuitionistic and many-valued logics. Itinerary VIII surveys the development of semantical notions from the early work on axiomatics up to Tarski's work on truth. (shrink)

This volume will be of particular interest to researchers working in the history, and in the philosophy, of logic and mathematics, and more generally, to ...

(new version: 10/30/07). Click here to download the companion Mathematica 6 notebook that goes along with this paper.

Traces the development of recursive functions from their origins in the late nineteenth century to the mid-1930s, with particular emphasis on the work and influence of Kurt Gödel.

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 focusses on the generality of the entities involved in a geometric proof of the kind found in ancient Greek treatises: it shows that the standard modern translation of Greek mathematical propositions falsifies crucial syntactical elements, and employs an incorrect conception of the denotative letters in a Greek geometric proof; epigraphic evidence is adduced to show that these denotative letters are ‘letter-labels’. On this basis, the article explores the consequences of seeing that a Greek mathematical proposition is fully general, (...) and the ontological commitments underlying the stylistic practice. (shrink)

Based on the relevant logic R, the system R# was proposed as a relevant Peano arithmetic. R# has many nice properties: the most conspicuous theorems of classical Peano arithmetic PA are readily provable therein; it is readily and effectively shown to be nontrivial; it incorporates both intuitionist and classical proof methods. But it is shown here that R# is properly weaker than PA, in the sense that there is a strictly positive theorem QRF of PA which is unprovable in R#. (...) The reason is interesting: if PA is slightly weakened to a subtheory P+, it admits the complex ring C as a model; thus QRF is chosen to be a theorem of PA but false in C. Inasmuch as all strictly positive theorems of R# are already theorems of P+, this nonconservativity result shows that QRF is also a nontheorem of R#. As a consequence, Ackermann's rule γ is inadmissible in R#. Accordingly, an extension of R# which retains its good features is desired. The system R##, got by adding an omega-rule, is such an extension. Central question: is there an effectively axiomatizable system intermediate between R# and R##, which does formalize arithmetic on relevant principles, but also admits γ in a natural way? (shrink)

Often philosophers, logicians, and mathematicians employ a notion of intended structure when talking about a branch of mathematics. In addition, we know that there are foundational mathematical theories that can find representatives for the objects of informal mathematics. In this paper, we examine how faithfully foundational theories can represent intended structures, and show that this question is closely linked to the decidability of the theory of the intended structure. We argue that this sheds light on the trade-off between expressive power (...) and meta-theoretic properties when comparing first-order and second-order logic. (shrink)

We give a general account of the goals of axiomatization, introducing a variant on Detlefsen’s notion of ‘complete descriptive axiomatization’. We describe how distinctions between the Greek and modern view of number, magnitude, and proportion impact the interpretation of Hilbert’s axiomatization of geometry. We argue, as did Hilbert, that Euclid’s propositions concerning polygons, area, and similar triangles are derivable from Hilbert’s first-order axioms. We argue that Hilbert’s axioms including continuity show much more than the geometrical propositions of Euclid’s theorems and (...) thus are an immodest complete descriptive axiomatization of that subject. (shrink)

We study the foundation of space-time theory in the framework of first-order logic (FOL). Since the foundation of mathematics has been successfully carried through (via set theory) in FOL, it is not entirely impossible to do the same for space-time theory (or relativity). First we recall a simple and streamlined FOL-axiomatization Specrel of special relativity from the literature. Specrel is complete with respect to questions about inertial motion. Then we ask ourselves whether we can prove the usual relativistic properties of (...) accelerated motion (e.g., clocks in acceleration) in Specrel. As it turns out, this is practically equivalent to asking whether Specrel is strong enough to “handle” (or treat) accelerated observers. We show that there is a mathematical principle called induction (IND) coming from real analysis which needs to be added to Specrel in order to handle situations involving relativistic acceleration. We present an extended version AccRel of Specrel which is strong enough to handle accelerated motion, in particular, accelerated observers. Among others, we show that~the Twin Paradox becomes provable in AccRel, but it is not provable without IND. (shrink)

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 (...) show how to interpret the theory BTFA in Robinson's theory of arithmetic Q. This fact entails that the elementary theory of the real closed ordered fields is interpretable in Q. (shrink)

We propose and investigate a uniform modal logic framework for reasoning about topology and relative distance in metric and more general distance spaces, thus enabling the comparison and combination of logics from distinct research traditions such as Tarski’s for topological closure and interior, conditional logics, and logics of comparative similarity. This framework is obtained by decomposing the underlying modal-like operators into first-order quantifier patterns. We then show that quite a powerful and natural fragment of the resulting first-order logic can be (...) captured by one binary operator comparing distances between sets and one unary operator distinguishing between realised and limit distances . Due to its greater expressive power, this logic turns out to behave quite differently from both and conditional logics. We provide finite axiomatisations and ExpTime-completeness proofs for the logics of various classes of distance spaces, in particular metric spaces. But we also show that the logic of the real line is not recursively enumerable. This result is proved by an encoding of Diophantine equations. (shrink)

This article presents Tarski's Address at the Princeton Bicentennial Conference on Problems of Mathematics, together with a separate summary. Two accounts of the discussion which followed are also included. The central topic of the Address and of the discussion is decision problems. The introductory note gives information about the Conference, about the background of the subjects discussed in the Address, and about subsequent developments to these subjects.

Edward Nelson published in 1986 a book defending an extreme formalist view of mathematics according to which there is animpassable barrierin the totality of exponentiation. On the positive side, Nelson embarks on a program of investigating how much mathematics can be interpreted in Raphael Robinson's theory of arithmetic. In the shadow of this program, some very nice logical investigations and results were produced by a number of people, not only regarding what can be interpreted inbut also what cannot be so (...) interpreted. We explain some of these results and rely on them to discuss Nelson's position. (shrink)

1. One theory or many? In 2004 a very interesting and readable article by Lenore Blum, entitled “Computing over the reals: Where Turing meets Newton,” appeared in the Notices of the American Mathematical Society. It explained a basic model of computation over the reals due to Blum, Michael Shub and Steve Smale (1989), subsequently exposited at length in their influential book, Complexity and Real Computation (1997), coauthored with Felipe Cucker. The ‘Turing’ in the title of Blum’s article refers of course (...) to Alan Turing, famous for his explication of the notion of mechanical computation on discrete data such as the integers. The ‘Newton’ there has to do to with the well known numerical method due to Isaac Newton for approximating the zeros of continuous functions under suitable conditions that is taken to be a paradigm of scientific computing. Finally, the meaning of “Turing meets Newton” in the title of Blum’s article has another, more particular aspect: in connection with the problem of controlling errors in the numerical solution of linear equations and inversion of matrices,Turing (1948) defined a notion of condition for the relation of changes in the output of a computation due to small changes in the input that is analogous to Newton’s definition of the derivative. The thrust of Blum’s 2004 article was that the BSS model of computation on the reals is the appropriate foundation for scientific computing in general. By way of response, two years later another very interesting and equally readable article appeared in the Notices, this time by Mark Braverman and Stephen Cook (2006) entitled “Computing over the reals: Foundations for scientific computing,” in which the authors argued that the requisite foundation is provided by a quite different “bit computation” model, that is in fact prima facie incompatible with the BSS model. The bit computation model goes back to ideas due to Stefan Banach and Stanislaw Mazur in the latter part of the 1930s, but the first publication was not made until Mazur (1963).. (shrink)

We shall prove quantifier elimination theorems for neocompact formulas, which define neocompact sets and are built from atomic formulas using finite disjunctions, infinite conjunctions, existential quantifiers, and bounded universal quantifiers. The neocompact sets were first introduced to provide an easy alternative to nonstandard methods of proving existence theorems in probability theory, where they behave like compact sets. The quantifier elimination theorems in this paper can be applied in a general setting to show that the family of neocompact sets is countably (...) compact. To provide the necessary setting we introduce the notion of a law structure. This notion was motivated by the probability law of a random variable. However, in this paper we discuss a variety of model theoretic examples of the notion in the light of our quantifier elimination results. (shrink)

In [8], the third author defined a reducibility$\le _w^{\rm{*}}$that lets us compare the computing power of structures of any cardinality. In [6], the first two authors showed that the ordered field of reals${\cal R}$lies strictly above certain related structures. In the present paper, we show that$\left \equiv _w^{\rm{*}}{\cal R}$. More generally, for the weak-looking structure${\cal R}$ℚconsisting of the real numbers with just the ordering and constants naming the rationals, allo-minimal expansions of${\cal R}$ℚare equivalent to${\cal R}$. Using this, we show that (...) for any analytic functionf,$\left \equiv _w^{\rm{*}}{\cal R}$. $is noto-minimal.). (shrink)

Although the case for the judgment-dependence of many other domains has been pored over, surprisingly little attention has been paid to mathematics and logic. This paper presents two dilemmas for a judgment-dependent account of these areas. First, the extensionality-substantiality dilemma: in each case, either the judgment-dependent account is extensionally inadequate or it cannot meet the substantiality condition (roughly: non-vacuous specification). Second, the extensionality-extremality dilemma: in each case, either the judgment-dependent account is extensionally inadequate or it cannot meet the extremality condition (...) (roughly: absence of independent explanation). The paper concludes with a moral concerning the judgment-dependence of a posteriori areas of discourse that emerges from consideration of these two a priori cases. (shrink)

Can we do science without numbers? How much contingency is there? These seemingly unrelated questions--one in the philosophy of math and science and the other in metaphysics--share an unexpectedly close connection. For as it turns out, a radical answer to the second leads to a breakthrough on the first. The radical answer is new view about modality called compossible immutabilism. The breakthrough is a new strategy for doing science without numbers. One of the chief benefits of the new strategy is (...) that, unlike the existing substantialism approach from Field (1980), the new strategy naturally generalizes to theories formulated in terms of state space. (shrink)

Alfred Tarski was one of the greatest logicians of the twentieth century. His influence comes not merely through his own work but from the legion of students who pursued his projects, both in Poland and Berkeley. This chapter focuses on three key areas of Tarski's research, beginning with his groundbreaking studies of the concept of truth. Tarski's work led to the creation of the area of mathematical logic known as model theory and prefigured semantic approaches in the philosophy of language (...) and philosophical logic, such as Kripke's possible worlds semantics for modal logic. We also examine the paradoxical decomposition of the sphere known as the Banach–Tarski paradox. Finally we examine Tarski's work on decidable and undecidable theories, which he carried out in collaboration with students such as Mostowski, Presburger, Robinson and others. (shrink)

We carry out a systematic study of decidability for theories of real vector spaces, inner product spaces, and Hilbert spaces and of normed spaces, Banach spaces and metric spaces, all formalized using a 2-sorted first-order language. The theories for list turn out to be decidable while the theories for list are not even arithmetical: the theory of 2-dimensional Banach spaces, for example, has the same many-one degree as the set of truths of second-order arithmetic.We find that the purely universal and (...) purely existential fragments of the theory of normed spaces are decidable, as is the ∀∃ fragment of the theory of metric spaces. These results are sharp of their type: reductions of Hilbertʼs 10th problem show that the ∃∀ fragments for metric and normed spaces and the ∀∃ fragment for normed spaces are all undecidable. (shrink)

Alfred Tarski’s influence on computer science was indirect but significant in a number of directions and was in certain respects fundamental. Here surveyed is Tarski’s work on the decision procedure for algebra and geometry, the method of elimination of quantifiers, the semantics of formal languages, model-theoretic preservation theorems, and algebraic logic; various connections of each with computer science are taken up.

For a finite von Neumann algebra factor M, the projections form a modular ortholattice L(M). We show that the equational theory of L(M) coincides with that of some resp. all L(ℂ n × n ) and is decidable. In contrast, the uniform word problem for the variety generated by all L(ℂ n × n ) is shown to be undecidable.

This paper provides a definitive answer, based on considerations derived from first-order logic, to the question regarding the status of elementary geometry, whether elementary geometry can be reduced to algebra. The answer we arrive at is negative, and is based on a series of structural questions that can be asked only inside the geometric formal theory, as well as the consideration of reverse geometry, which is the art of finding minimal axiom systems strong enough to prove certain geometrical theorems, given (...) that there are no algebraic structures that one could associate with those minimal axiom systems. (shrink)

Let R be a real closed field. An integer part I for R is a discretely ordered subring such that for every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r \in R}$$\end{document}, there exists an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${i \in I}$$\end{document} so that i ≤ r < i + 1. Mourgues and Ressayre (J Symb Logic 58:641–647, 1993) showed that every real closed field has an integer part. The procedure of Mourgues and (...) Ressayre appears to be quite complicated. We would like to know whether there is a simple procedure, yielding an integer part that is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2(R)}$$\end{document} —limit computable relative to R. We show that there is a maximal Z-ring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I \subseteq R}$$\end{document} which is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2(R)}$$\end{document}. However, this I may not be an integer part for R. By a result of Wilkie (Logic Colloquium ’77), any Z-ring can be extended to an integer part for some real closed field. Using Wilkie’s ideas, we produce a real closed field R with a Z-ring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I \subseteq R}$$\end{document} such that I does not extend to an integer part for R. For a computable real closed field, we do not know whether there must be an integer part in the class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2}$$\end{document}. We know that certain subclasses of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2}$$\end{document} are not sufficient. We show that for each \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n \in \omega}$$\end{document}, there is a computable real closed field with no n-c.e. integer part. In fact, there is a computable real closed field with no n-c.e. integer part for any n. (shrink)

This is a critical reexamination of several pieces in van Heijenoort’s Selected Essays that are directly or indirectly concerned with the philosophy of logic or the relation of logic to natural language. Among the topics discussed are absolutism and relativism in logic, mass terms, the idea of a rational dictionary, and sense and identity of sense in Frege.

In this article, I wish to discuss in an informal way the motivations and the motifs of the constructivist approach to logic and mathematics and by a natural extension to the general field of science, particularly theoretical physics. Foundational questions in those domains are not ruled by philosophical principles, but a critical philosophy of foundations could be the leitmotiv to the extent that it can be used as a criterion to decide between the theoretical options of scientific practices that are (...) often oblivious to their own doctrinal presuppositions. My objective is to provide the justificatory reasons for a constructivist option or posture in the field of scientific knowledge. (shrink)

We consider semi‐algebraic sets and properties of these sets that are expressible by sentences in first‐order logic over the reals. We are interested in first‐order properties that are invariant under topological transformations of the ambient space. Two semi‐algebraic sets are called topologically elementarily equivalent if they cannot be distinguished by such topological first‐order sentences. So far, only semi‐algebraic sets in one and two‐dimensional space have been considered in this context. Our contribution is a natural characterisation of topological elementary equivalence of (...) regular closed semi‐algebraic sets in three‐dimensional space, extending a known characterisation for the two‐dimensional case. Our characterisation is based on the local topological behaviour of semi‐algebraic sets and the key observation that topologically elementarily equivalent sets can be transformed into each other by means of geometric transformations, each of them mapping a set to a first‐order indistinguishable one. (shrink)

We introduce new first-order languages for the elementary n-dimensional geometry and elementary n-dimensional affine geometry , based on extending equation image and equation image, respectively, with new function symbols. Here, β stands for the betweenness relation and ≡ for the congruence relation. We show that the associated theories admit effective quantifier elimination.

Model theorists have been studying analytic functions since the late 1970s. Highlights include the seminal work of Denef and van den Dries on the theory of the p-adics with restricted analytic functions, Wilkie's proof of o-minimality of the theory of the reals with the exponential function, and the formulation of Zilber's conjecture for the complex exponential. My goal in this talk is to survey these main developments and to reflect on today's open problems, in particular for theories of valued fields.

We present a model of computation for string functions over single-sorted, total algebraic structures and study some basic features of a general theory of computability within this framework. Our concept generalizes the Blum-Shub-Smale setting of computability over the reals and other rings. By dealing with strings of arbitrary length instead of tuples of fixed length, some suppositions of deeper results within former approaches to generalized recursion theory become superfluous. Moreover, this gives the basis for introducing computational complexity in a BSS-like (...) manner. Relationships both to classical computability and to Friedman's concept of eds computability are established. Two kinds of nondeterminism as well as several variants of recognizability are investigated with respect to interdependencies on each other and on properties of the underlying structures. For structures of finite signatures, there are universal programs with the usual characteristics. For the general case of not necessarily finite signature, this subject will be studied in a separate, forthcoming paper. (shrink)

We show that the theory of the real field with a generic real power function is decidable, relative to an oracle for the rational cut of the exponent of the power function. We also show the existence of generic computable real numbers, hence providing an example of a decidable o-minimal proper expansion of the real field by an analytic function.

The article deals with Cantor's argument for the non-denumerability of reals somewhat in the spirit of Lakatos' logic of mathematical discovery. At the outset Cantor's proof is compared with some other famous proofs such as Dedekind's recursion theorem, showing that rather than usual proofs they are resolutions to do things differently. Based on this I argue that there are "ontologically" safer ways of developing the diagonal argument into a full-fledged theory of continuum, concluding eventually that famous semantic paradoxes based on (...) diagonal construction are caused by superficial understanding of what a name is. (shrink)

The article deals with Cantor’s diagonal argument and its alleged philosophical consequences such as that there are more reals than integers and, hence, that some of the reals must be independent of language because the totality of words and sentences is always count-able. My claim is that the main flaw of the argument for the existence of non-nameable objects or truths lies in a very superficial understanding of what a name or representation actually is.

The main result of this paper were announced in Kosheleva — Kreinovich [7, 8]; for other algorithmic aspects of Hilbert's Third Problem see Kosheleva [6]. The authors are greatly thankful to Alexandr D. Alexandrov , Vladimir G. Boltianskii and Patrick Suppes for valuable discussions, and to the anonymous referee for important suggestions. This work was partially supported by an NSF grant No. CDA-9015006.