Turing and Church formulated two different formal accounts of computability that turned out to be extensionally equivalent. Since the accounts refer to different properties they cannot both be adequate conceptual analyses of the concept of computability. This insight has led to a discussion concerning which account is adequate. Some authors have suggested that this philosophical debate—which shows few signs of converging on one view—can be circumvented by regarding Church’s and Turing’s theses as explications. This move opens up the possibility that (...) both accounts could be adequate, albeit in their own different ways. In this paper, I focus on the question of whether Church’s thesis can be seen as an explication in the precise Carnapian sense. Most importantly, I address an additional constraint that Carnap puts on the explicative power of axiomatic systems—an axiomatisation explicates when it is clear which mathematical entities form the theory’s intended model—and that implicitly applies to axiomatisations of recursion theory used in Church’s account of computability. To overcome this difficulty, I propose two possible clarifications of the pre-systematic concept of “computability” that can both be captured in recursion theory, and I show how both clarifications avoid an objection arising from Carnap’s constraint. (shrink)

We give a rough statement of the main result. Let D be a compact subset of ℝ3× ℝ. The propagation u of a wave can be noncomputable in any neighborhood of any point of D even though the initial conditions which determine the wave propagation uniquely are computable. A precise statement of the result appears below.

The best known and most widely discussed aspect of Kurt Gödel's philosophy of mathematics is undoubtedly his robust realism or platonism about mathematical objects and mathematical knowledge. This has scandalized many philosophers but probably has done so less in recent years than earlier. Bertrand Russell's report in his autobiography of one or more encounters with Gödel is well known:Gödel turned out to be an unadulterated Platonist, and apparently believed that an eternal “not” was laid up in heaven, where virtuous logicians (...) might hope to meet it hereafter.On this Gödel commented:Concerning my “unadulterated” Platonism, it is no more unadulterated than Russell's own in 1921 when in the Introduction to Mathematical Philosophy … he said, “Logic is concerned with the real world just as truly as zoology, though with its more abstract and general features.” At that time evidently Russell had met the “not” even in this world, but later on under the infuence of Wittgenstein he chose to overlook it.One of the tasks I shall undertake here is to say something about what Gödel's platonism is and why he held it.A feature of Gödel's view is the manner in which he connects it with a strong conception of mathematical intuition, strong in the sense that it appears to be a basic epistemological factor in knowledge of highly abstract mathematics, in particular higher set theory. Other defenders of intuition in the foundations of mathematics, such as Brouwer and the traditional intuitionists, have a much more modest conception of what mathematical intuition will accomplish. (shrink)

In the paper the problem of definability and undefinability of the concept of satisfaction and truth is considered. Connections between satisfaction and truth on the one hand and consistency of certain systems of omega-logic and transfinite induction on the other are indicated.

We present a two-level theory to formalize constructive mathematics as advocated in a previous paper with G. Sambin.One level is given by an intensional type theory, called Minimal type theory. This theory extends a previous version with collections.The other level is given by an extensional set theory that is interpreted in the first one by means of a quotient model.This two-level theory has two main features: it is minimal among the most relevant foundations for constructive mathematics; it is constructive thanks (...) to the way the extensional level is linked to the intensional one which fulfills the “proofs-as-programs” paradigm and acts as a programming language. (shrink)

My goal here is to explore the relationship between pure and applied mathematics and then, eventually, to draw a few morals for both. In particular, I hope to show that this relationship has not been static, that the historical rise of pure mathematics has coincided with a gradual shift in our understanding of how mathematics works in application to the world. In some circles today, it is held that historical developments of this sort simply represent changes in fashion, or in (...) social arrangements, governments, power structures, or some such thing, but I resist the full force of this way of thinking, clinging to the old school notion that we have gradually learned more about the world over time, that our opinions on these matters have improved, and that seeing how we reached the point we now occupy may help us avoid falling back into old philosophies that are now no longer viable. In that spirit, it seems to me that once we focus on the general question of how mathematics relates to science, one observation is immediate: the march of the centuries has produced an amusing reversal of philosophical fortunes. Let me begin there. In the beginning, that is, in Plato, mathematical knowledge was sharply distinguished from ordinary perceptual belief about the world. According to Plato’s metaphysics, mathematics is the study of eternal and unchanging abstract Forms,1 while science is uncertain and changeable opinion about the world of mere becoming. Indeed, in Plato’s lights, of the two, only mathematics deserves to be called ‘knowledge’ at all! Of course if sense perception cannot give us knowledge, if mathematics is not about perceivable things, then Plato owes us an account of how we ordinary humans achieve this wonderful insight into the properties of the abstract world of Forms. Plato’s answer is that we do not actually acquire mathematical knowledge at all; rather, we recollect it from a time before birth, when our souls, unencumbered by physical bodies, were free to commune with the Forms, and not just the mathematical ones, either – also Truth, Beauty, Justice, the Good, and so on.2 Whatever appeal this position may have held for the ancient Greeks, it will not begin to satisfy a contemporary, scientifically minded philosopher.. (shrink)

Gödei's Theorem seems to me to prove that Mechanism is false, that is, that minds cannot be explained as machines. So also has it seemed to many other people: almost every mathematical logician I have put the matter to has confessed to similar thoughts, but has felt reluctant to commit himself definitely until he could see the whole argument set out, with all objections fully stated and properly met. This I attempt to do.

Examples of possible theological influences upon the development of mathematics are indicated. The best known connection can be found in the realm of infinite sets treated by us as known or graspable, which constitutes a divine-like approach. Also the move to treat infinite processes as if they were one finished object that can be identified with its limits is routine in mathematicians, but refers to seemingly super-human power. For centuries this was seen as wrong and even today some philosophers, for (...) example Brian Rotman, talk critically about “theological mathematics”. Theological metaphors, like “God’s view”, are used even by contemporary mathematicians. While rarely appearing in official texts they are rather easily invoked in “the kitchen of mathematics”. There exist theories developing without the assumption of actual infinity the tools of classical mathematics needed for applications (For instance, Mycielski’s approach). Conclusion: mathematics could have developed in another way. Finally, several specific examples of historical situations are mentioned where, according to some authors, direct theological input into mathematics appeared: the possibility of the ritual genesis of arithmetic and geometry, the importance of the Indian religious background for the emergence of zero, the genesis of the theories of Cantor and Brouwer, the role of Name-worshipping for the research of the Moscow school of topology. Neither these examples nor the previous illustrations of theological metaphors provide a certain proof that religion or theology was directly influencing the development of mathematical ideas. They do suggest, however, common points and connections that merit further exploration. (shrink)

In his classic 1936 paper Tarski sought to motivate his definition of logical consequence by appeal to the inference form: P(0), P(1), . . ., P(n), . . . therefore ∀nP(n). This is prima facie puzzling because these inferences are seemingly first-order and Tarski knew that Gödel had shown first-order proof methods to be complete, and because ∀nP(n) is not a logical consequence of P(0), P(1), . . ., P(n), . . . by Taski's proposed definition. An attempt to resolve (...) the puzzle due to Etchemendy is considered and rejected. A second attempt due to Gómez-Torrente is accepted as far as it goes, but it is argued that it raises a further puzzle of its own: it takes the plausibility of Tarski's claim that his definition captures our common concept of logical consequence to depend upon our common concept being a reductive conception. A further interpretation of what Tarski had in mind when he offered the example is proposed, using materials well known to Tarski at the time. It is argued that this interpretation makes the motivating example independent of reductive definitions which take natural numbers to be higher-order set theoretic entities, and it also explains why he did not regard the distinction between defined and primitive terms as pressing, as was the distinction between logical and nonlogical terms. (shrink)

The proposition that a decreasing sequence of ordinals necessarily terminates has been given a new, and perhaps unexpected, importance by the rôle which it plays in Gentzen's proof of the freedom from contradiction of the “reine Zahlentheorie.” Gödel's construction of non-demonstrable propositions and the establishment of the impossibility of a proof of freedom from contradiction, within the framework of a certain type of formal system, showed that a proof of freedom from contradiction could be found only by transcending the axioms (...) and proof processes of that formal system. Gentzen's proof succeeds by utilisingtransfinite inductionto prove that certain sequences of reduction processes, enumerated by ordinals less than ε (the first ordinal to satisfy ε = ὡ) are finite. Were it possible to provethe restricted ordinal theorem, that a descending sequence of ordinals, less thanε, is finite, in Gentzen's “reine Zahlentheorie,” then it would be possible to determine a contradiction in that number system. In his paper, Gentzen proves the theorem of transfinite induction, which he requires, by an intuitive argument. There is also a method of reducing transfinite induction, for ordinals less than ε, to a number-theoretic principle given by Hilbert and Bernays, and a similar method by Ackermann. None of these proofs of transfinite induction isfinitist. (shrink)

A look at Wittgenstein's comments on the incompleteness theorem with an inter-pretation that is consistent with what Gödel proved.

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)

Most scholars think of David Hilbert's program as the most demanding and ideologically motivated attempt to provide a foundation for mathematics, and because they see technical obstacles in the way of realizing the program's goals, they regard it as a failure. Against this view, Curtis Franks argues that Hilbert's deepest and most central insight was that mathematical techniques and practices do not need grounding in any philosophical principles. He weaves together an original historical account, philosophical analysis, and his own development (...) of the meta-mathematics of weak systems of arithmetic to show that the true philosophical significance of Hilbert's program is that it makes the autonomy of mathematics evident. The result is a vision of the early history of modern logic that highlights the rich interaction between its conceptual problems and technical development. (shrink)

People have always been interested in numbers, in particular the natural numbers. Of course, we all have an intuitive notion of what these numbers are. In the late 19th century mathematicians, such as Grassmann, Frege and Dedekind, gave definitions for these familiar objects. Since then the development of axiomatic schemes for arithmetic have played a fundamental role in a logical understanding of mathematics. There has been a need for some time for a monograph on the metamathematics of first-order arithmetic. The (...) aim of the book by Hajek and Pudlak is to cover some of the most important results in the study of a first order theory of the natural numbers, called Peano arithmetic and its fragments (subtheories). The field is quite active, but only a small part of the results has been covered in monographs. This book is divided into three parts. In Part A, the authors develop parts of mathematics and logic in various fragments. Part B is devoted to incompleteness. Part C studies systems that have the induction schema restricted to bounded formulas (Bounded Arithmetic). One highlight of this section is the relation of provability to computational complexity. The study of formal systems for arithmetic is a prerequisite for understanding results such as Gödel's theorems. This book is intended for those who want to learn more about such systems and who want to follow current research in the field. The book contains a bibliography of approximately 1000 items. (shrink)

Platonism is the most pervasive philosophy of mathematics. Indeed, it can be argued that an inarticulate, half-conscious Platonism is nearly universal among mathematicians. The basic idea is that mathematical entities exist outside space and time, outside thought and matter, in an abstract realm. In the more eloquent words of Edward Everett, a distinguished nineteenth-century American scholar, "in pure mathematics we contemplate absolute truths which existed in the divine mind before the morning stars sang together, and which will continue to exist (...) there when the last of their radiant host shall have fallen from heaven." In What is Mathematics, Really?, renowned mathematician Rueben Hersh takes these eloquent words and this pervasive philosophy to task, in a subversive attack on traditional philosophies of mathematics, most notably, Platonism and formalism. Virtually all philosophers of mathematics treat it as isolated, timeless, ahistorical, inhuman. Hersh argues the contrary, that mathematics must be understood as a human activity, a social phenomenon, part of human culture, historically evolved, and intelligible only in a social context. Mathematical objects are created by humans, not arbitrarily, but from activity with existing mathematical objects, and from the needs of science and daily life. Hersh pulls the screen back to reveal mathematics as seen by professionals, debunking many mathematical myths, and demonstrating how the "humanist" idea of the nature of mathematics more closely resembles how mathematicians actually work. At the heart of the book is a fascinating historical account of the mainstream of philosophy--ranging from Pythagoras, Plato, Descartes, Spinoza, and Kant, to Bertrand Russell, David Hilbert, Rudolph Carnap, and Willard V.O. Quine--followed by the mavericks who saw mathematics as a human artifact, including Aristotle, Locke, Hume, Mill, Peirce, Dewey, and Lakatos. In his epilogue, Hersh reveals that this is no mere armchair debate, of little consequence to the outside world. He contends that Platonism and elitism fit well together, that Platonism in fact is used to justify the claim that "some people just can't learn math." The humanist philosophy, on the other hand, links mathematics with geople, with society, and with history. It fits with liberal anti-elitism and its historical striving for universal literacy, universal higher education, and universal access to knowledge and culture. Thus Hersh's argument has educational and political ramifications. Written by the co-author of The Mathematical Experience, which won the American Book Award in 1983, this volume reflects an insider's view of mathematical life, based on twenty years of doing research on advanced mathematical problems, thirty-five years of teaching graduates and undergraduates, and many long hours of listening, talking to, and reading philosophers. A clearly written and highly iconoclastic book, it is sure to be hotly debated by anyone with a passionate interest in mathematics or the philosophy of science. (shrink)

"A valuable collection both for original source material as well as historical formulations of current problems."-- The Review of Metaphysics "Much more than a mere collection of papers . . . a valuable addition to the literature."-- Mathematics of Computation An anthology of fundamental papers on undecidability and unsolvability by major figures in the field, this classic reference opens with Godel's landmark 1931 paper demonstrating that systems of logic cannot admit proofs of all true assertions of arithmetic. Subsequent papers by (...) Godel, Church, Turing, and Post single out the class of recursive functions as computable by finite algorithms. Additional papers by Church, Turing, and Post cover unsolvable problems from the theory of abstract computing machines, mathematical logic, and algebra, and material by Kleene and Post includes initiation of the classification theory of unsolvable problems. Suitable for graduate and undergraduate courses. 1965 ed. (shrink)

Suppose now that two philosophers, McX and I, differ over ontology. Suppose McX maintains there is something which I maintain there is not. McX can, quite consistently with his own point of view, describe our difference of opinion by saying that I refuse to recognize certain entities. I should protest of course that he is wrong in his formulation of our disagreement, for I maintain that there are no entities, of the kind which he alleges, for me to recognize; but (...) my finding him wrong in his formulation of our disagreement is unimportant, for I am committed to considering him wrong in his ontology anyway. When I try to formulate our difference of opinion, on the other hand, I seem to be in a predicament. I cannot admit that there are some things which McX countenances and I do not, for in admitting that there are such things I should be contradicting my own rejection of them. (shrink)

In response to Bhupinder Singh Anand''s article CAN WE REALLY FALSIFY TRUTH BY DICTAT? in THE REASONER II, 1, January 2008,that denies the existence of nonstandard models of Peano Arithmetic, we prove from Compactness the existence of such models.

What is predicativity? While the term suggests that there is a single idea involved, what the history will show is that there are a number of ideas of predicativity which may lead to different logical analyses, and I shall uncover these only gradually. A central question will then be what, if anything, unifies them. Though early discussions are often muddy on the concepts and their employment, in a number of important respects they set the stage for the further developments, and (...) so I shall give them special attention. NB. Ahistorically, modern logical and set-theoretical notation will be used throughout, as long as it does not conflict with original intentions. (shrink)

Classical interpretations of Goedels formal reasoning, and of his conclusions, implicitly imply that mathematical languages are essentially incomplete, in the sense that the truth of some arithmetical propositions of any formal mathematical language, under any interpretation, is, both, non-algorithmic, and essentially unverifiable. However, a language of general, scientific, discourse, which intends to mathematically express, and unambiguously communicate, intuitive concepts that correspond to scientific investigations, cannot allow its mathematical propositions to be interpreted ambiguously. Such a language must, therefore, define mathematical truth (...) verifiably. We consider a constructive interpretation of classical, Tarskian, truth, and of Goedel's reasoning, under which any formal system of Peano Arithmetic---classically accepted as the foundation of all our mathematical Languages---is verifiably complete in the above sense. We show how some paradoxical concepts of Quantum mechanics can, then, be expressed, and interpreted, naturally under a constructive definition of mathematical truth. (shrink)