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)

Presburger arithmetic is the first-order theory of the natural numbers with addition. We characterize sets that can be defined by a Presburger formula as exactly the sets whose characteristic functions can be represented by rational generating functions; a geometric characterization of such sets is also given. In addition, ifp= are a subset of the free variables in a Presburger formula, we can define a counting functiong to be the number of solutions to the formula, for a givenp. We show that (...) every counting function obtained in this way may be represented as, equivalently, either a piecewise quasi-polynomial or a rational generating function. Finally, we translate known computational complexity results into this setting and discuss open directions. (shrink)

This article outlines the work of a group of US mathematicians called the American Postulate Theorists and their influence on Tarski's work in the 1930s that was to be foundational for model theory. The American Postulate Theorists were influenced by the European foundational work of the period around 1900, such as that of Peano and Hilbert. In the period roughly from 1900???1940, they developed an indigenous American approach to foundational investigations. This made use of interpretations of precisely formulated axiomatic theories (...) to prove such metatheoretic properties as independence, consistency, categoricity and, in some cases, completeness of axiom sets. This approach to foundations was in many respects similar to that later taken by Tarski, who frequently cites the work of American Postulate Theorists. Their work served as paradigm examples of the theories and concepts investigated in model theory. The article also examines the possibility of a more specific impetus to Tarski's model theoretic investigation, arising from his having studied in 1927???1929 a paper by C. H. Langford proving completeness for various axiom sets for linear orders. This used the method of elimination of quantifiers. The article concludes with an examination of one example of Langford's methods to indicate how their correct formulation seems to call for model-theoretic concepts. (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.

We examine the question of whether scientific theories can ever be complete. For two closely related reasons, we will argue that they cannot. The first reason is the inability to determine what are “valid empirical observations”, a result that is based on a self-reference Gödel/Tarski-like proof. The second reason is the existence of “meta-empirical” evidence of the inherent incompleteness of observations. These reasons, along with theoretical incompleteness, are intimately connected to the notion of belief and to theses within the philosophy (...) of science: the Quine-Duhem (and underdetermination) thesis and the observational/theoretical distinction failure. Some puzzling aspects of the philosophical theses will become clearer in light of these connections. Other results that follow are: no absolute measure of the informational content of empirical data, no absolute measure of the entropy of physical systems, and no complete computer simulation of the natural world are possible. The connections with the mathematical theorems of Gödel and Tarski reveal the existence of other connections between scientific and mathematical incompleteness: computational irreducibility, complexity, infinity, arbitrariness and self-reference. Finally, suggestions will be offered of where a more rigorous (or formal) “proof” of scientific incompleteness can be found. (shrink)