In a series of papers, Don Fallis points out that although mathematicians are generally unwilling to accept merely probabilistic proofs, they do accept proofs that are incomplete, long and complicated, or partly carried out by computers. He argues that there are no epistemic grounds on which probabilistic proofs can be rejected while these other proofs are accepted. I defend the practice by presenting a property I call ‘transferability’, which probabilistic proofs lack and acceptable proofs have. I also consider what this (...) says about the similarities between mathematics and, on the one hand natural sciences, and on the other hand philosophy. (shrink)

The present collection brings together in a convenient form the seminal articles in the philosophy of mathematics by these and other major thinkers.

Following Marr’s famous three-level distinction between explanations in cognitive science, it is often accepted that focus on modeling cognitive tasks should be on the computational level rather than the algorithmic level. When it comes to mathematical problem solving, this approach suggests that the complexity of the task of solving a problem can be characterized by the computational complexity of that problem. In this paper, I argue that human cognizers use heuristic and didactic tools and thus engage in cognitive processes that (...) make their problem solving algorithms computationally suboptimal, in contrast with the optimal algorithms studied in the computational approach. Therefore, in order to accurately model the human cognitive tasks involved in mathematical problem solving, we need to expand our methodology to also include aspects relevant to the algorithmic level. This allows us to study algorithms that are cognitively optimal for human problem solvers. Since problem solving methods are not universal, I propose that they should be studied in the framework of enculturation, which can explain the expected cultural variance in the humanly optimal algorithms. While mathematical problem solving is used as the case study, the considerations in this paper concern modeling of cognitive tasks in general. (shrink)

Propositional proof complexity is the study of the sizes of propositional proofs, and more generally, the resources necessary to certify propositional tautologies. Questions about proof sizes have connections with computational complexity, theories of arithmetic, and satisfiability algorithms. This is article includes a broad survey of the field, and a technical exposition of some recently developed techniques for proving lower bounds on proof sizes.

This massive two-volume reference presents a comprehensive selection of the most important works on the foundations of mathematics. While the volumes include important forerunners like Berkeley, MacLaurin, and D'Alembert, as well as such followers as Hilbert and Bourbaki, their emphasis is on the mathematical and philosophical developments of the nineteenth century. Besides reproducing reliable English translations of classics works by Bolzano, Riemann, Hamilton, Dedekind, and Poincare, William Ewald also includes selections from Gauss, Cantor, Kronecker, and Zermelo, all translated here for (...) the first time. (shrink)

An engaging account of the origins of the modern mathematical theory of the infinite, his book is also a spirited defense against the attacks and misconceptions ...

One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory---the field that studies the resources needed to solve computational problems---leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume's problem of induction and Goodman's (...) grue riddle, the foundations of quantum mechanics, economic rationality, closed timelike curves, and several other topics of philosophical interest. I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis. (shrink)

This book develops arithmetic without the induction principle, working in theories that are interpretable in Raphael Robinson's theory Q. Certain inductive formulas, the bounded ones, are interpretable in Q. A mathematically strong, but logically very weak, predicative arithmetic is constructed. Originally published in 1986. The Princeton Legacy Library uses the latest print-on-demand technology to again make available previously out-of-print books from the distinguished backlist of Princeton University Press. These paperback editions preserve the original texts of these important books while presenting (...) them in durable paperback editions. The goal of the Princeton Legacy Library is to vastly increase access to the rich scholarly heritage found in the thousands of books published by Princeton University Press since its founding in 1905. (shrink)

Non-standard models were introduced by Skolem, first for set theory, then for Peano arithmetic. In the former, Skolem found support for an anti-realist view of absolutely uncountable sets. But in the latter he saw evidence for the impossibility of capturing the intended interpretation by purely deductive methods. In the history of mathematics the concept of a nonstandard model is new. An analysis of some major innovations–the discovery of irrationals, the use of negative and complex numbers, the modern concept of function, (...) and non-Euclidean geometry–reveals them as essentially different from the introduction of non-standard models. Yet, non-Euclidean geometry, which is discussed at some length, is relevant to the present concern; for it raises the issue of intended interpretation. The standard model of natural numbers is the best candidate for an intended interpretation that cannot be captured by a deductive system. Next, I suggest, is the concept of a wellordered set, and then, perhaps, the concept of a constructible set. One may have doubts about a realistic conception of the standard natural numbers, but such doubts cannot gain support from non-standard models. Attempts to utilize non-standard models for an anti-realist position in mathematics, which appeal to meaning-as-use, or to arguments of the kind proposed by Putnam, fail through irrelevance, or lead to incoherence. Robinson’s skepticism, on the other hand, is a coherent position, though one that gives up on providing a detailed philosophical account. The last section enumerates various uses of non-standard models. (shrink)

Part of the ambiguity lies in the various points of view from which this question might be considered. The crudest di erence lies between the point of view of the working mathematician and that of the logician concerned with the foundations of mathematics. Now some of my fellow mathematical logicians might protest this distinction, since they consider themselves to be just more of those \working mathematicians". Certainly, modern logic has established itself as a very respectable branch of mathematics, and there (...) are quite a few highly technical journals in logic, such as The Journal of Sym-. (shrink)

There are different ways to present a Presidential Address to the APA; the one I have chosen is simply to report on work that I am doing right now, on work in progress. I am going to present some of my further explorations into the computational model of the mind.\**.

This systematic investigation of computation and mental phenomena by a noted psychologist and computer scientist argues that cognition is a form of computation, that the semantic contents of mental states are encoded in the same general way as computer representations are encoded. It is a rich and sustained investigation of the assumptions underlying the directions cognitive science research is taking. 1 The Explanatory Vocabulary of Cognition 2 The Explanatory Role of Representations 3 The Relevance of Computation 4 The Psychological Reality (...) of Programs: Strong Equivalence 5 Constraining Functional Architecture 6 The Bridge from Physical to Symbolic: Transduction 7 Functional Architecture and Analogue Processes 8 Mental Imagery and Functional Architecture 9 Epilogue: What is Cognitive Science the Science of? (shrink)

We construct a weak second-order theory of arithmetic which includes Weak König's Lemma (WKL) for trees defined by bounded formulae. The provably total functions (with Σ b 1 -graphs) of this theory are the polynomial time computable functions. It is shown that the first-order strength of this version of WKL is exactly that of the scheme of collection for bounded formulae.

It is argued that an instrumentalist notion of proof such as that represented in Hilbert's viewpoint is not obligated to satisfy the conservation condition that is generally regarded as a constraint on Hilbert's Program. A more reasonable soundness condition is then considered and shown not to be counter-exemplified by Godel's First Theorem. Finally, attention is given to the question of what a theory is; whether it should be seen as a "list" or corpus of beliefs, or as a method for (...) selecting beliefs. The significance of this question for assessing "intensional" results like Godel's Second Theorem, and their bearing on Hilbert's Program are discussed. (shrink)

In Minimal Rationality, Christopher Cherniak boldly challenges the myth of Man the the Rational Animal and the central role that the "perfectly rational...

Charles Parsons; X*—Mathematical Intuition, Proceedings of the Aristotelian Society, Volume 80, Issue 1, 1 June 1980, Pages 145–168, https://doi.org/10.1093/ari.

Throughout history, mathematicians have expressed preference for solutions to problems that avoid introducing concepts that are in one sense or another “foreign” or “alien” to the problem under investigation. This preference for “purity” (which German writers commonly referred to as “methoden Reinheit”) has taken various forms. It has also been persistent. This notwithstanding, it has not been analyzed at even a basic philosophical level. In this paper we give a basic analysis of one conception of purity—what we call topical purity—and (...) discuss its epistemological significance. (shrink)

Turing computation over a non-linguistic domain presupposes a notation for the domain. Accordingly, computability theory studies notations for various non-linguistic domains. It illuminates how different ways of representing a domain support different finite mechanical procedures over that domain. Formal definitions and theorems yield a principled classification of notations based upon their computational properties. To understand computability theory, we must recognize that representation is a key target of mathematical inquiry. We must also recognize that computability theory is an intensional enterprise: it (...) studies entities as represented in certain ways, rather than entities detached from any means of representing them. (shrink)

Die Leitgedanken meiner Untersuchungen über die Grundlagen der Mathematik, die ich - anknüpfend an frühere Ansätze - seit 1917 in Besprechungen mit P. BERNAYS wieder aufgenommen habe, sind von mir an verschiedenen Stellen eingehend dargelegt worden. Diesen Untersuchungen, an denen auch W. ACKERMANN beteiligt ist, haben sich seither noch verschiedene Mathematiker angeschlossen. Der hier in seinem ersten Teil vorliegende, von BERNAYS abgefaßte und noch fortzusetzende Lehrgang bezweckt eine Darstellung der Theorie nach ihren heutigen Ergebnissen. Dieser Ergebnisstand weist zugleich die Richtung (...) für die weitere Forschung in der Beweistheorie auf das Endziel hin, unsere üblichen Methoden der Mathematik samt und sonders als widerspruchsfrei zu erkennen. Im Hinblick auf dieses Ziel möchte ich hervorheben, daß die zeit weilig aufgekommene Meinung, aus gewissen neueren Ergebnissen von GÖDEL folge die Undurchführbarkeit meiner Beweistheorie, als irrtüm lich erwiesen ist. Jenes Ergebnis zeigt in der Tat auch nur, daß man für die weitergehenden Widerspruchsfreiheitsbeweise den finiten Stand punkt in einer schärferen Weise ausnutzen muß, als dieses bei der Be trachtung der elementaren Formallsmen erforderlich ist. Göttingen, im März 1934 HILBERT Vorwort zur ersten Auflage Eine Darstellung der Beweistheorie, welche aus dem HILBERTschen Ansatz zur Behandlung der mathematisch-logischen Grundlagenpro bleme erwachsen ist, wurde schon seit längerem von HILBERT ange kündigt. (shrink)

This article bears on four topics: observational predicates and phenomenal properties, vagueness, strict finitism as a philosophy of mathematics, and the analysis of feasible computability. It is argued that reactions to strict finitism point towards a semantics for vague predicates in the form of nonstandard models of weak arithmetical theories of the sort originally introduced to characterize the notion of feasibility as understood in computational complexity theory. The approach described eschews the use of nonclassical logic and related devices like degrees (...) of truth or supervaluation. Like epistemic approaches to vagueness, it may thus be smoothly integrated with the use of classical model theory as widely employed in natural language semantics. But unlike epistemicism, the described approach fails to imply either the existence of sharp boundaries or the failure of tolerance for soritical predicates. Applications ofmeasurement theory(in the sense of Krantz, Luce, Suppes, & Tversky (1971)) to vagueness in the nonstandard setting are also explored. (shrink)

Putnam and Searle famously argue against computational theories of mind on the skeptical ground that there is no fact of the matter as to what mathematical function a physical system is computing: both conclude (albeit for somewhat different reasons) that virtually any physical object computes every computable function, implements every program or automaton. There has been considerable discussion of Putnam's and Searle's arguments, though as yet there is little consensus as to what, if anything, is wrong with these arguments. In (...) the present paper we show that an analogous line of reasoning can be raised against the numerical measurement (i.e., numerical representation) of physical magnitudes, and we argue that this result is a reductio ad absurdum of the challenge to computational skepticism. We then use this reductio to get clearer about both (i) what's wrong with Putnam's and Searle's arguments against computationalism, and (ii) what can be learned about both computational implementation and numerical measurement from the shortcomings of both sorts of skeptical argument. (shrink)