"What is mathematics?" is a question that has been debated since antiquity. This book presents a groundbreaking and surprising answer to the question-showing through the concept of the physicalization of metamathematics how both mathematics and physics as experienced by humans can be seen to emerge from the unique underlying computational structure of the recently formulated ruliad. Written with Stephen Wolfram's characteristic expositional flair and richly illustrated with remarkable algorithmic diagrams, the book takes the reader on a unprecedented intellectual journey (...) to the center of some of the deepest questions about mathematics and its nature-and points the way to a new understanding of the foundations and future of mathematics, taking a major step beyond ideas from Plato, Kant, Hilbert, Gödel and others. (shrink)

Putnam famously attempted to use model theory to draw metaphysical conclusions. His Skolemisation argument sought to show metaphysical realists that their favourite theories have countable models. His permutation argument sought to show that they have permuted models. His constructivisation argument sought to show that any empirical evidence is compatible with the Axiom of Constructibility. Here, I examine the metamathematics of all three model-theoretic arguments, and I argue against Bays (2001, 2007) that Putnam is largely immune to metamathematical challenges.

Stephen Cole Kleene was one of the greatest logicians of the twentieth century and this book is the influential textbook he wrote to teach the subject to the next generation. It was first published in 1952, some twenty years after the publication of Godel's paper on the incompleteness of arithmetic, which marked, if not the beginning of modern logic. The 1930s was a time of creativity and ferment in the subject, when the notion of computable moved from the realm of (...) philosophical speculation to the realm of science. This was accomplished by the work of Kurt Gode1, Alan Turing, and Alonzo Church, who gave three apparently different precise definitions of computable. When they all turned out to be equivalent, there was a collective realization that this was indeed the right notion. Kleene played a key role in this process. One could say that he was there at the beginning of modern logic. He showed the equivalence of lambda calculus with Turing machines and with Godel's recursion equations, and developed the modern machinery of partial recursive functions. This textbook played an invaluable part in educating the logicians of the present. It played an important role in their own logical education.". (shrink)

The metamathematical tradition, tracing back to Hilbert, employs syntactic modeling to study the methods of contemporary mathematics. A central goal has been, in particular, to explore the extent to which infinitary methods can be understood in computational or otherwise explicit terms. Ergodic theory provides rich opportunities for such analysis. Although the field has its origins in seventeenth century dynamics and nineteenth century statistical mechanics, it employs infinitary, nonconstructive, and structural methods that are characteristically modern. At the same time, computational concerns (...) and recent applications to combinatorics and number theory force us to reconsider the constructive character of the theory and its methods. This paper surveys some recent contributions to the metamathematical study of ergodic theory, focusing on the mean and pointwise ergodic theorems and the Furstenberg structure theorem for measure preserving systems. In particular, I characterize the extent to which these theorems are nonconstructive, and explain how proof-theoretic methods can be used to locate their "constructive content.". (shrink)

The metamathematical theorems of Gödel and Church are frequently applied to the philosophy of mind, typically as rational evidence against mechanism. Using methods of Post and Smullyan, these results are presented as purely mathematical theorems and various such applications are discussed critically. In particular, J. Lucas's use of Gödel's theorem to distinguish between conscious and unconscious beings is refuted, while more generally, attempts to extract philosophy from metamathematics are shown to involve only dramatizations of the constructivity problem in foundations. (...) More specifically, philosophical extrapolations from metamathematics are shown to involve premature extensions of Church's thesis. (shrink)

Pursuing the proof-theoretic program of Friedman and Simpson, we begin the study of the metamathematics of countable linear orderings by proving two main results. Over the weak base system consisting of arithmetic comprehension, II 1 1 -CA0 is equivalent to Hausdorff's theorem concerning the canonical decomposition of countable linear orderings into a sum over a dense or singleton set of scattered linear orderings. Over the same base system, ATR0 is equivalent to a version of the Continuum Hypothesis for linear (...) orderings, which states that every countable linear ordering either has countably many or continuum many Dedekind cuts. (shrink)

Strengthening a theorem of Hjorth this paper gives a new characterization of which Polish groups admit compatible complete left invariant metrics. As a corollary it is proved that any Polish group without a complete left invariant metric has a continuous action on a Polish space whose associated orbit equivalence relation is not essentially countable.

Turing's programme, the idea that intelligence can be modelled computationally, is set in the context of a parallel between certain elements from metamathematics and Popper's schema for the evolution of knowledge. The parallel is developed at both the formal level, where it hinges on the recursive structuring of Popper's schema, and at the contentual level, where a few key issues common to both epistemology and metamathematics are briefly discussed. In light of this connection Popper's principle of transference, akin (...) to Turing's belief in the relevance of the theory of computation for modelling psychological functions, is widened into the extended principle of transference. Thus Turing's programme gains a solid epistemological footing. *I am grateful to Claude Lamontagne and Jean-Pierre Delage for their comments on this paper. (shrink)

The automatic verification of large parts of mathematics has been an aim of many mathematicians from Leibniz to Hilbert. While Gödel's first incompleteness theorem showed that no computer program could automatically prove certain true theorems in mathematics, the advent of electronic computers and sophisticated software means in practice there are many quite effective systems for automated reasoning that can be used for checking mathematical proofs. This book describes the use of a computer program to check the proofs of several celebrated (...) theorems in metamathematics including those of Gödel and Church-Rosser. The computer verification using the Boyer-Moore theorem prover yields precise and rigorous proofs of these difficult theorems. It also demonstrates the range and power of automated proof checking technology. The mechanization of metamathematics itself has important implications for automated reasoning, because metatheorems can be applied as labor-saving devices to simplify proof construction. (shrink)

Metamathematics and the Philosophical Tradition is the first work to explore in such historical depth the relationship between fundamental philosophical quandaries regarding self-reference and meta-mathematical notions of consistency and incompleteness. Using the insights of twentieth-century logicians from Gödel through Hilbert and their successors, this volume revisits the writings of Aristotle, the ancient skeptics, Anselm, and enlightenment and seventeenth and eighteenth century philosophers Leibniz, Berkeley, Hume, Pascal, Descartes, and Kant to identify ways in which these both encode and evade problems (...) of a priori definition and self-reference. The final chapters critique and extend more recent insights of late 20th-century logicians and quantum physicists, and offer new applications of the completeness theorem as a means of exploring "metatheoretical ascent" and the limitations of scientific certainty. Broadly syncretic in range, Metamathematics and the Philosophical Tradition addresses central and recurring problems within epistemology. The volume’s elegant, condensed writing style renders accessible its wealth of citations and allusions from varied traditions and in several languages. Its arguments will be of special interest to historians and philosophers of science and mathematics, particularly scholars of classical skepticism, the Enlightenment, Kant, ethics, and mathematical logic. (shrink)

In this paper, we trace the conceptual history of the term ?metamathematics? in the nineteenth century. It is well known that Hilbert introduced the term for his proof-theoretic enterprise in about 1922. But he was verifiably inspired by an earlier usage of the phrase in the 1870s. After outlining Hilbert's understanding of the term, we will explore the lines of inducement and elucidate the different meanings of ?metamathematics? in the final decades of the nineteenth century. Finally, we will (...) investigate the earlier occurrences and come to the conclusion that the conceptual prehistory of the Hilbertian notion of metamathematics dates back to 1870, whereas the history of the word starts in 1799 at the latest. What is this: metamathematics? It is something amazing everybody, [?] since it makes the mind dizzy and withdraws thinking its sole fulcrum.1 1 Brunner 1898, p. 832: ?Was ist das: Metamathematik? Es ist etwas, was einen Jeden in das äusserste Staunen versetzt, [?] was das Gehirn schwindlig macht und dem Denken seinen einzigen Stütz- und Angelpunkt zu entziehen droht? (shrink)

The relevance of metamathematical researches for philosophy of math- ematics is an indubitable matter. In the paper I shall speak about impli- cations of metamathematics for general philosophy, especially for classical epistemological problems. Let us start with a historical observation con- cerning Hilbert's programme, the rst research programme in metamathe- matics as a separate study of formal systems. This programme was strongly in uence by epistemological considerations. In fact, Hilbert wanted to se- cure all classical mathematics against inconsistencies and (...) this aim had be achieved with the help of nitary consistency proof. Hilbert's claim is like the Cartesian project of reduction of all concepts to clarae et distinctae ideae. The epistemological commitment of original Hilbert's programme may be treated as a prelim- inary heuristic motivation for looking for epistemological implications of metamathematical results. It seems reasonable to examine in this respect three so-called limitative theorems: the rst Godel's incompleteness theo- rem , the second Godel's incom- pleteness theorem consistency of S, cannot be proved in S, providing that S is consistent) and Tarski's undenability theorem ; \S" stands for formal system containing elementary number theory. From the above-mentioned theorems we obtain an important, from philosophical point of view, conclusion: semantics of S cannot be expressed in S. Now, I shall present three applications of limitative theorems to the analysis of classical epistemological problems. (shrink)

In this article the author first described the developments which brought to focus the importance of consistency proofs for mathematics, and which led Hilbert to promote the science of metamathemat-ics. Further comments and remarks concern the (partly analogous) beginnings of the work on the decision problem, Gödel?s theorems and related matters, and general metamathematics. An appendix summarizes a text by the author on completeness and categoricity.

In this article, it is suggested a possible profile for the historical and philosophical migration of several issues from the metamathematical domain to the domain of functionalist neuro-computational Cognitive Science. The description of such a transition is accomplished by an analysis of the ideas of Post, Church, Gödel, and, in particular, Turing on the possibility of formalization of creative thinking in Mathematics.Neste artigo, propõe-se uma configuração possível para a transição histórico-filosófica de temas investigados no domínio da metamatemática para o domínio (...) da Ciência Cognitiva funcionalista neurocomputacional. A descrição de tal transição é feita por meio de uma breve análise das idéias de Post, Church, Gödel e Turing sobre a possibilidade de formalização do pensamento criador na matemática, enfatizando as contribuições deste último. (shrink)

The paper is concerned with Quine's substitutional account of logical truth. The critique of Quine's definition tends to focus on miscellaneous odds and ends, such as problems with identity. However, in an appendix to his influential article On Second Order Logic, George Boolos offered an ingenious argument that seems to diminish Quine's account of logical truth on a deeper level. In the article he shows that Quine's substitutional account of logical truth cannot be generalized properly to the general concept of (...) logical consequence. The purpose of this paper is threefold: first, to introduce the reader to the metamathematics of Quine's substitutional definition of logical truth; second, to make Boolos' result accessible to a broader audience by giving a detailed and self-contained presentation of his proof; and, finally, to discuss some of the possible implications and how a defender of the Quinean concepts might react to the challenge posed by Boolos' result. (shrink)

We explain and summarize the use of logic to provide a uniform perspective for studying limit laws on finite probability spaces. This work connects developments in stability theory, finite model theory, abstract model theory, and probability. We conclude by linking this context with work on the Urysohn space.

This paper describes an axiomatic theory BT, which is a suitable formal theory for developing constructive mathematics, due to its expressive language with countable number of set types and its constructive properties such as the existence and disjunction properties, and consistency with the formal Church thesis. BT has a predicative comprehension axiom and usual combinatorial operations. BT has intuitionistic logic and is consistent with classical logic. BT is mutually interpretable with a so called theory of arithmetical truth PATr and with (...) a second-order arithmetic SA that contains infinitely many sorts of sets of natural numbers. We compare BT with some standard second-order arithmetics and investigate the proof-theoretical strengths of fragments of BT, PATr and SA. (shrink)

A number of comparability theorems have been investigated from the viewpoint of reverse mathematics. Among these are various comparability theorems between countable well orderings ([2],[8]), and between closed sets in metric spaces ([3],[5]). Here we investigate the reverse mathematics of a comparability theorem for countable metric spaces, countable linear orderings, and sets of rationals. The previous work on closed sets used a strengthened notion of continuous embedding. The usual weaker notion of continuous embedding is used here. As a byproduct, we (...) sharpen previous results of [3],[5]. (shrink)

I ON THE PRIMITIVE TERM OF LOGISTICf IN this article I propose to establish a theorem belonging to logistic concerning some connexions, not widely known, ...

The classical Ulm theory provides a complete set of invariants for countable abelian p-groups, and hence also for countable torsion abelian groups. These invariants involve countable ordinals. One can read off many simple structural properties of such groups directly from the Ulm theory. We carry out a reverse mathematics analysis of several such properties. In many cases, we reverse to ATR0, thereby demonstrating a kind of necessary use of Ulm theory.

We discuss the problem of defining the collection of first-order elementary classes in terms of the natural topological space of countable models.

Published with the aid of a grant from the National Endowment for the Humanities. Contains the only complete English-language text of The Concept of Truth in Formalized Languages. Tarski made extensive corrections and revisions of the original translations for this edition, along with new historical remarks. It includes a new preface and a new analytical index for use by philosophers and linguists as well as by historians of mathematics and philosophy.

Published with the aid of a grant from the National Endowment for the Humanities. Contains the only complete English-language text of The Concept of Truth in Formalized Languages. Tarski made extensive corrections and revisions of the original translations for this edition, along with new historical remarks. It includes a new preface and a new analytical index for use by philosophers and linguists as well as by historians of mathematics and philosophy.

This book grew out of a graduate student paper [261] in which I set down some criticisms of J. R. Lucas' attempt to refute mechanism by means of G6del's theorem. I had made several such abortive attempts myself and had become familiar with their pitfalls, and especially with the double edged nature of incompleteness arguments. My original idea was to model the refutation of mechanism on the almost universally accepted G6delian refutation of Hilbert's formalism, but I kept getting stuck on (...) questions of mathematical philosophy which I found myself having to beg. A thorough study of the foundational works of Hilbert and Bernays finally convinced me that I had all too naively and uncritically bought this refutation of formalism. I did indeed discover points of surprisingly close contact between formalism and mechanism, but also that it was possible to under mine certain strong arguments against these positions precisely by invok ing G6del's and related work. I also began to realize that the Church Turing thesis itself is the principal bastion protecting mechanism, and that G6del's work was perhaps the best thing that ever happened to both mechanism and formalism. I pushed these lines of argument in my dis sertation with the patient help of my readers, Raymond Nelson and Howard Stein. I would especially like to thank the latter for many valuable criticisms of my dissertation as well as some helpful suggestions for reor ganizing it in the direction of the present book. (shrink)

The metamathematical tradition that developed from Hilbert’s program is based on syntactic characterizations of mathematics and the use of explicit, finitary methods in the metatheory. Although G¨.

The aim of this article is to give students a small sense of what metamathematics is—that is, how one might use mathematics to study mathematics itself. School or college teachers could base a classroom exercise on the letter games I shall describe and use them as a springboard for further exploration. Since I shall presuppose no knowledge of formal logic, the games are less an introduction to Gödel's theorems than an introduction to an introduction to them. Nevertheless, they show, (...) in an accessible way, how metamathematics can be mathematically interesting. (shrink)

This paper is an attempt to bring together two separated areas of research: classical mathematics and metamathematics on the one side, non-monotonic reasoning on the other. This is done by simulating nonmonotonic logic through antitonic theory extensions. In the first half, the specific extension procedure proposed here is motivated informally, partly in comparison with some well-known non-monotonic formalisms. Operators V and, more generally, U are obtained which have some plausibility when viewed as giving nonmonotonic theory extensions. In the second (...) half, these operators are treated from a mathematical and metamathematical point of view. Here an important role is played by U -closed theories and U -fixed points. The last section contains results on V-closed theories which are specific for V. (shrink)