Ode to Hippasus

I was so glad to be involved with this project of Hannah Hoffman. She had inquired on Twitter whether mathematicians could provide a proof of the irrationality of root two that rhymes. I set off immediately, of course, to answer the challenge. My wife Barbara Gail Montero and our daughter Hypatia and I spent a day thinking, writing, revising, rewriting, rethinking, rewriting, and eventually we had a set lyrics providing the proof, in rhyme and meter. We had wanted specifically to highlight not only the logic of the proof, but also to tell the fateful story of Hippasus, credited with the discovery.

Hannah proceeded to create the amazing musical version:

Forcing as a computational process, Kobe Set Theory Workshop, March 2021

This will be a talk for the Kobe Set Theory Workshop, held on the occasion of Sakaé Fuchino’s retirement, 9-11 March 2021.

Abstract. I shall discuss senses in which set-theoretic forcing can be seen as a computational process on the models of set theory. Given an oracle for the atomic or elementary diagram of a model of set theory $\langle M,\in^M\rangle$, for example, one may in various senses compute $M$-generic filters $G\subset P\in M$ and the corresponding forcing extensions $M[G]$. Meanwhile, no such computational process is functorial, for there must always be isomorphic alternative presentations of the same model of set theory $M$ that lead by the computational process to non-isomorphic forcing extensions $M[G]\not\cong M[G’]$. Indeed, there is no Borel function providing generic filters that is functorial in this sense.

This is joint work with Russell Miller and Kameryn Williams.

Forcing as a computational process

[bibtex key=”HamkinsMillerWilliams:Forcing-as-a-computational-process”]

Determinacy for proper class games, Seminaire de Logique Lyon-Paris, April 2021

This will be a talk for the Seminaire de Logique Lyon-Paris on 14 April 2021 4pm Paris time (3pm UK). The talk will be held on Zoom at
875 1148 7359
.

Abstract. The principle of open determinacy for class games — two-player games of perfect information with plays of length ω, where the moves are chosen from a possibly proper class, such as games on the ordinals — is not provable in Zermelo-Fraenkel set theory ZFC or Gödel-Bernays set theory GBC, if these theories are consistent, because provably in ZFC there is a definable open proper class game with no definable winning strategy. In fact, the principle of open determinacy and even merely clopen determinacy for class games implies Con(ZFC) and iterated instances Con(Con(ZFC)) and more, because it implies that there is a satisfaction class for first-order truth, and indeed a transfinite tower of truth predicates $\text{Tr}_\alpha$ for iterated truth-about-truth, relative to any class parameter. This is perhaps explained, in light of the Tarskian recursive definition of truth, by the more general fact that the principle of clopen determinacy is exactly equivalent over GBC to the principle of elementary transfinite recursion ETR over well-founded class relations. Meanwhile, the principle of open determinacy for class games is strictly stronger, although it is provable in the stronger theory GBC+$\Pi^1_1$-comprehension, a proper fragment of Kelley-Morse set theory KM.

Nonlinearity in the hierarchy of large cardinal consistency strength

This is currently a draft version only of my article-in-progress on the topic of linearity in the hierarchy of consistency strength, especially with large cardinals. Comments are very welcome, since I am still writing the article. Please kindly send me comments by email or just post here.

This article will be the basis of the Weeks 7 & 8 discussion in the Graduate Philosophy of Logic seminar I am currently running with Volker Halbach at Oxford in Hilary term 2021.

I present instances of nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength—as natural or as nearly natural as I can make them—and consider philosophical aspects of the question of naturality with regard to this phenomenon.

It is a mystery often mentioned in the foundations of mathematics, a fundamental phenomenon to be explained, that our best and strongest mathematical theories seem to be linearly ordered and indeed well-ordered by consistency strength. Given any two of the familiar large cardinal hypotheses, for example, generally one of them will prove the consistency of the other.

Why should it be linear? Why should the large cardinal notions line up like this, when they often arise from completely different mathematical matters? Measurable cardinals arise from set-theoretic issues in measure theory; Ramsey cardinals generalize ideas in graph coloring combinatorics; compact cardinals arise with compactness properties of infinitary logic. Why should these disparate considerations lead to principles that are linearly related by direct implication and consistency strength?

The phenomenon is viewed by many in the philosophy of mathematics as significant in our quest for mathematical truth. In light of Gödel incompleteness, after all, we must eternally seek to strengthen even our best and strongest theories. Is the linear hierarchy of consistency strength directing us along the elusive path, the “one road upward” as John Steel describes it, toward the final, ultimate mathematical truth? That is the tantalizing possibility.

Meanwhile, we do know as a purely formal matter that the hierarchy of consistency strength is not actually well-ordered—it is ill-founded, densely ordered, and nonlinear. The statements usually used to illustrate these features, however, are weird self-referential assertions constructed in the Gödelian manner via the fixed-point lemma—logic-game trickery, often dismissed as unnatural.

Many set theorists claim that amongst the natural assertions, consistency strengths remain linearly ordered and indeed well ordered. H. Friedman refers to “the apparent comparability of naturally occurring logical strengths as one of the great mysteries of [the foundations of mathematics].” Andrés Caicedo says,

It is a remarkable empirical phenomenon that we indeed have comparability for natural theories. We expect this to always be the case, and a significant amount of work in inner model theory is guided by this belief.

Stephen G. Simpson writes:

It is striking that a great many foundational theories are linearly ordered by <. Of course it is possible to construct pairs of artificial theories which are incomparable under <. However, this is not the case for the “natural” or non-artificial theories which are usually regarded as significant in the foundations of mathematics. The problem of explaining this observed regularity is a challenge for future foundational research.

John Steel writes “The large cardinal hypotheses [the ones we know] are themselves wellordered by consistency strength,” and he formulates what he calls the “vague conjecture” asserting that

If T is a natural extension of ZFC, then there is an extension H axiomatized by large cardinal hypotheses such that T ≡ Con H. Moreover, ≤ Con is a prewellorder of the natural extensions of ZFC. In particular, if T and U are natural extensions of ZFC, then either T ≤ Con U or U ≤ Con T.

Peter Koellner writes

Remarkably, it turns out that when one restricts to those theories that “arise in nature” the interpretability ordering is quite simple: There are no descending chains and there are no incomparable elements—the interpretability ordering on theories that “arise in nature” is a wellordering.

Let me refer to this position as the natural linearity position, the assertion that all natural assertions of mathematics are linearly ordered by consistency strength. The strong form of the position, asserted by some of those whom I have cited above, asserts that the natural assertions of mathematics are indeed well-ordered by consistency strength. By all accounts, this view appears to be widely held in large cardinal set theory and the philosophy of set theory.

Despite the popularity of this position, I should like in this article to explore the contrary view and directly to challenge the natural linearity position.

Main Question. Can we find natural instances of nonlinearity and illfoundedness in the hierarchy of consistency strength?

I shall try my best.

You have to download the article to see my candidates for natural instances of nonlinearity in the hierarchy of large cardinal consistency strength, but I can tease you a little by mentioning that there are various cautious enumerations of the ZFC axioms which actually succeed in enumerating all the ZFC axioms, but with a strictly weaker consistency strength than the usual (incautious) enumeration. And similarly there are various cautious versions of the large cardinal hypothesis, which are natural, but also incomparable in consistency strength.

(Please note that it was Uri Andrews, rather than Uri Abraham, who settled question 16 with the result of theorem 17. I have corrected this from an earlier draft.)

A review of the Gödel fixed-point lemma, with generalizations and applications

This bried unpublished note (11 pages) contains an overview of the Gödel fixed-point lemma, along with several generalizations and applications, written for use in the Week 3 lecture of the Graduate Philosophy of Logic seminar that I co-taught with Volker Halbach at Oxford in Hilary term 2021. The theme of the seminar was self-reference, truth, and consistency strengths, and in this lecture we discussed the nature of Gödel’s fixed-point lemma and generalizations, with various applications in logic.

Contents

  1. Introduction
  2. Gödel’s fixed-point lemma
    An application to the Gödel incompleteness theorem
  3. Finite self-referential schemes
    An application to nonindependent disjunctions of independent sentences
  4. Gödel-Carnap fixed point lemma
    Deriving the double fixed-point lemma as a consequence
    An application to the provability version of Yablo’s paradox
  5. Kleene recursion theorem
    An application involving computable numbers
    An application involving the universal algorithm
    An application to Quine programs and Ouroborous chains
  6. References

Graduate Seminar in Philosophy of Logic, Oxford, Hilary Term 2021

This is a graduate seminar in the Philosophy of Logic at the University of Oxford, run jointly by myself and Volker Halbach in Hilary Term 2021.

The theme will be self-reference, truth, and the hierarchy of consistency strength.

A detailed schedule, including the list of topics and readings is available on Volker’s web site.

The seminar will be held Fridays 9-11 am during term, online via Zoom at 812 2300 3837.

The final two sessions of term will be specifically on the hierarchy of consistency strength, based on my current article in progress concerning the possibility of natural instances of incomparability and ill-foundedness in the hierarchy of large cardinal consistency strength.

Definability and the Math Tea argument: must there be numbers we cannot describe or define? University of Warsaw, 22 January 2021

This will be a talk for a new mathematical logic seminar at the University of Warsaw in the Department of Hhilosophy, entitled Epistemic and Semantic Commitments of Foundational Theories, devoted to formal truth theories and implicit commitments of foundational theories as well as their conceptual surroundings.

My talk will be held 22 January 2021, 8 pm CET (7 pm UK), online via Zoom https://us02web.zoom.us/j/83366049995.

Tran Tuan, CC BY-SA 4.0 <https://creativecommons.org/licenses/by-sa/4.0>, via Wikimedia Commons

Abstract. According to the math tea argument, perhaps heard at a good afternoon tea, there must be some real numbers that we can neither describe nor define, since there are uncountably many real numbers, but only countably many definitions. Is it correct? In this talk, I shall discuss the phenomenon of pointwise definable structures in mathematics, structures in which every object has a property that only it exhibits. A mathematical structure is Leibnizian, in contrast, if any pair of distinct objects in it exhibit different properties. Is there a Leibnizian structure with no definable elements? We shall discuss many interesting elementary examples, eventually working up to the proof that every countable model of set theory has a pointwise definable extension, in which every mathematical object is definable.

Pointwise definable models of set theory

[bibtex key=”HamkinsLinetskyReitz2013:PointwiseDefinableModelsOfSetTheory”]

Can there be natural instances of nonlinearity in the hierarchy of consistency strength? UWM Logic Seminar, January 2021

This is a talk for the University of Wisconsin, Madison Logic Seminar, 25 January 2020 1 pm (7 pm UK).

The talk will be held online via Zoom ID: 998 6013 7362.

Abstract. It is a mystery often mentioned in the foundations of mathematics that our best and strongest mathematical theories seem to be linearly ordered and indeed well-ordered by consistency strength. Given any two of the familiar large cardinal hypotheses, for example, generally one of them proves the consistency of the other. Why should this be? The phenomenon is seen as significant for the philosophy of mathematics, perhaps pointing us toward the ultimately correct mathematical theories. And yet, we know as a purely formal matter that the hierarchy of consistency strength is not well-ordered. It is ill-founded, densely ordered, and nonlinear. The statements usually used to illustrate these features are often dismissed as unnatural or as Gödelian trickery. In this talk, I aim to overcome that criticism—as well as I am able to—by presenting a variety of natural hypotheses that reveal ill-foundedness in consistency strength, density in the hierarchy of consistency strength, and incomparability in consistency strength.

The talk should be generally accessible to university logic students, requiring little beyond familiarity with the incompleteness theorem and some elementary ideas from computability theory.

Proof and the Art of Mathematics: Examples and Extensions

A companion volume to my proof-writing book, Proof and the Art of Mathematics.

[bibtex key=”Hamkins2021:Proof-and-the-art-examples”]

Now available!

From the Preface:

The best way to learn mathematics is to dive in and do it. Don’t just listen passively to a lecture or read a book—you have got to take hold of the mathematical ideas yourself! Mount your own mathematical analysis. Formulate your own mathematical assertions. Consider your own mathematical examples. I recommend play—adopt an attitude of playful curiosity about mathematical ideas; grasp new concepts by exploring them in particular cases; try them out; understand how the mathematical constructions from your proofs manifest in your examples; explore all facets, going beyond whatever had been expected. You will find vast new lands of imagination. Let one example generalize to a whole class of examples; have favorite examples. Ask questions about the examples or about the mathematical idea you are investigating. Formulate conjectures and test them with your examples. Try to prove the conjectures—when you succeed, you will have proved a theorem. The essential mathematical activity is to make clear claims and provide sound reasons for them. Express your mathematical ideas to others, and practice the skill of stating matters well, succinctly, with accuracy and precision. Don’t be satisfied with your initial account, even when it is sound, but seek to improve it. Find alternative arguments, even when you already have a solid proof. In this way, you will come to a deeper understanding. Test the statements of others; ask for further explanation. Look into the corner cases of your results to probe the veracity of your claims. Set yourself the challenge either to prove or to refute a given statement. Aim to produce clear and correct mathematical arguments that logically establish their conclusions, with whatever insight and elegance you can muster.

This book is offered as a companion volume to my book Proof and the Art of Mathematics, which I have described as a mathematical coming-of-age book for students learning how to write mathematical proofs.

Spanning diverse topics from number theory and graph theory to game theory and real analysis, Proof and the Art shows how to prove a mathematical theorem, with advice and tips for sound mathematical habits and practice, as well as occasional reflective philosophical discussions about what it means to undertake mathematical proof. In Proof and the Art, I offer a few hundred mathematical exercises, challenges to the reader to prove a given mathematical statement, each a small puzzle to figure out; the intention is for students to develop their mathematical skills with these challenges of mathematical reasoning and proof.

Here in this companion volume, I provide fully worked-out solutions to all of the odd-numbered exercises, as well as a few of the even-numbered exercises. In many cases, the solutions here explore beyond the exercise question itself to natural extensions of the ideas. My attitude is that, once you have solved a problem, why not push the ideas harder to see what further you can prove with them? These solutions are examples of how one might write a mathematical proof. I hope that you will learn from them; let us go through them together. The mathematical development of this text follows the main book, with the same chapter topics in the same order, and all theorem and exercise numbers in this text refer to the corresponding statements of the main text.

Cantor’s Ice Cream Shoppe

Welcome to Cantor’s Ice Cream Shoppe! A huge choice of flavors—pile your cone high with as many scoops as you want!

Have two scoops, or three, four, or more! Why not infinitely many? Would you like $\omega$ many scoops, or $\omega\cdot2+5$ many scoops? You can have any countable ordinal number of scoops on your cone.

And furthermore, after ordering your scoops, you can order more scoops to be placed on top—all I ask is that you let me know how many such extra orders you plan to make. Let’s simply proceed transfinitely. You can announce any countable ordinal $\eta$, which will be the number of successive orders you will make; each order is a countable ordinal number of ice cream scoops to be placed on top of whatever cone is being assembled.

In fact, I’ll even let you change your mind about $\eta$ as we proceed, so as to give you more orders to make a taller cone.

So the process is:

  • You pick a countable ordinal $\eta$, which is the number of orders you will make.
  • For each order, you can pick any countable ordinal number of scoops to be added to the top of your ice-cream cone.
  • After making your order, you can freely increase $\eta$ to any larger countable ordinal, giving you the chance to make as many additional orders as you like.

At each limit stage of the ordering process, the ice cream cone you are assembling has all the scoops you’ve ordered so far, and we set the current $\eta$ value to the supremum of the values you had chosen so far.

If at any stage, you’ve used up your $\eta$ many orders, then the process has completed, and I serve you your ice cream cone. Enjoy!

Question. Can you arrange to achieve uncountably many scoops on your cone?

Although at each stage we place only countably many ice cream scoops onto the cone, nevertheless we can keep giving ourselves extra stages, as many as we want, simply by increasing $\eta$. Can you describe a systematic process of increasing the number of steps that will enable you to make uncountably many orders? This would achieve an unountable ice cream cone.

What is your solution? Give it some thought before proceeding. My solution appears below.

Alas, I claim that at Cantor’s Ice Cream Shoppe you cannot make an ice cream cone with uncountably many scoops. Specifically, I claim that there will inevitably come a countable ordinal stage at which you have used up all your orders.

Suppose that you begin by ordering $\beta_0$ many scoops, and setting a large value $\eta_0$ for the number of orders you will make. You subsequently order $\beta_1$ many additional scoops, and then $\beta_2$ many on top of that, and so on. At each stage, you may also have increased the value of $\eta_0$ to $\eta_1$ and then $\eta_2$ and so on. Probably all of these are enormous countable ordinals, making a huge ice cream cone.

At each stage $\alpha$, provided $\alpha<\eta_\alpha$, then you can make an order of $\beta_\alpha$ many scoops on top of your cone, and increase $\eta_\alpha$ to $\eta_{\alpha+1}$, if desired, or keep it the same.

At a limit stage $\lambda$, your cone has $\sum_{\alpha<\lambda}\beta_\alpha$ many scoops, and we update the $\eta$ value to the supremum of your earlier declarations $\eta_\lambda=\sup_{\alpha<\lambda}\eta_\alpha$.

What I claim now is that there will inevitably come a countable stage $\lambda$ for which $\lambda=\eta_\lambda$, meaning that you have used up all your orders with no possibility to further increase $\eta$. To see this, consider the sequence $$\eta_0\leq \eta_{\eta_0}\leq \eta_{\eta_{\eta_0}}\leq\cdots$$ We can define the sequence recursively by $\lambda_0=\eta_0$ and $\lambda_{n+1}=\eta_{\lambda_n}$. Let $\lambda=\sup_{n<\omega}\lambda_n$, the limit of this sequence. This is a countable supremum of countable ordinals and hence countable. But notice that $$\eta_\lambda=\sup_{n<\omega}\eta_{\lambda_n}=\sup_{n<\omega}\lambda_{n+1}=\lambda.$$ That is, $\eta_\lambda=\lambda$ itself, and so your orders have run out at $\lambda$, with no possibility to add more scoops or to increase $\eta$. So your order process completed at a countable stage, and you have therefore altogether only a countable ordinal number of scoops of ice cream. I’m truly very sorry at your pitiable impoverishment.

Set-theoretic and arithmetic potentialism: the state of current developments, CACML 2020

This will be a plenary talk for the Chinese Annual Conference on Mathematical Logic (CACML 2020), held online 13-15 November 2020. My talk will be held 14 November 17:00 Beijing time (9 am GMT).

Potentialist perspectives

Abstract. Recent years have seen a flurry of mathematical activity in set-theoretic and arithmetic potentialism, in which we investigate a collection of models under various natural extension concepts. These potentialist systems enable a modal perspective—a statement is possible in a model, if it is true in some extension, and necessary, if it is true in all extensions. We consider the models of ZFC set theory, for example, with respect to submodel extensions, rank-extensions, forcing extensions and others, and these various extension concepts exhibit different modal validities. In this talk, I shall describe the state of current developments, including the most recent tools and results.

Continuous models of arithmetic, MOPA, November 2020

This will be a talk for the Models of Peano Arithmetic (MOPA) seminar on 11 November 2020, 12 pm EST (5pm GMT). Kindly note the rescheduled date and time.

Abstract. Ali Enayat had asked whether there is a model of Peano arithmetic (PA) that can be represented as $\newcommand\Q{\mathbb{Q}}\langle\Q,\oplus,\otimes\rangle$, where $\oplus$ and $\otimes$ are continuous functions on the rationals $\Q$. We prove, affirmatively, that indeed every countable model of PA has such a continuous presentation on the rationals. More generally, we investigate the topological spaces that arise as such topological models of arithmetic. The reals $\mathbb{R}$, the reals in any finite dimension $\mathbb{R}^n$, the long line and the Cantor space do not, and neither does any Suslin line; many other spaces do; the status of the Baire space is open.

This is joint work with Ali Enayat, myself and Bartosz Wcisło.

Article: Topological models of arithmetic

[bibtex key=”EnayatHamkinsWcislo2018:Topological-models-of-arithmetic”]

A new proof of the Barwise extension theorem, and the universal finite sequence, Barcelona Set Theory Seminar, 28 October 2020

This will be a talk for the Barcelona Set Theory Seminar, 28 October 2020 4 pm CET (3 pm UK). Contact Joan Bagaria bagaria@ub.edu for the access link.

Abstract. The Barwise extension theorem, asserting that every countable model of ZF set theory admits an end-extension to a model of ZFC+V=L, is both a technical culmination of the pioneering methods of Barwise in admissible set theory and infinitary logic and also one of those rare mathematical theorems that is saturated with philosophical significance. In this talk, I shall describe a new proof of the theorem that omits any need for infinitary logic and relies instead only on classical methods of descriptive set theory. This proof leads directly to the universal finite sequence, a Sigma_1 definable finite sequence, which can be extended arbitrarily as desired in suitable end-extensions of the universe. The result has strong consequences for the nature of set-theoretic potentialism.  This work is joint with Kameryn J. Williams.

Article: The $\Sigma_1$-definable universal finite sequence

[bibtex key=”HamkinsWilliams:The-universal-finite-sequence”]

Lectures on the Philosophy of Mathematics, Oxford Michaelmas Term 2020

This series of self-contained lectures on the philosophy of mathematics, offered for Oxford Michaelmas Term 2020, is intended for students preparing for philosophy exam paper 122, although all interested parties are welcome to join. The lectures will be organized loosely around mathematical themes, in such a way that brings various philosophical issues naturally to light.

Lectures will follow my new book Lectures on the Philosophy of Mathematics (MIT Press), with supplemental readings suggested each week for further tutorial work. The book is available for pre-order, to be released 2 February 2021.

Lectures will be held online via Zoom every Wednesday 11-12 am during term at the following Zoom coordinates:

https://us02web.zoom.us/j/82822228760?pwd=UHU1cjVxSFpmd3haak5vYU51eFRrUT09

Meeting ID: 828 2222 8760

Passcode: 242081

All lectures will be recorded and made available at a later date.

Lecture 1. Numbers

Numbers are perhaps the essential mathematical idea, but what are numbers? There are many kinds of numbers—natural numbers, integers, rational numbers, real numbers, complex numbers, hyperreal numbers, surreal numbers, ordinal numbers, and more—and these number systems provide a fruitful background for classical arguments on incommensurability and transcendentality, while setting the stage for discussions of platonism, logicism, the nature of abstraction, the significance of categoricity, and structuralism.

Lecture 2. Rigour

Let us consider the problem of mathematical rigour in the development of the calculus. Informal continuity concepts and the use of infinitesimals ultimately gave way to the epsilon-delta limit concept, which secured a more rigourous foundation while also enlarging our conceptual vocabulary, enabling us to express more refined notions, such as uniform continuity, equicontinuity, and uniform convergence. Nonstandard analysis resurrected the infinitesimals on a more secure foundation, providing a parallel development of the subject. Meanwhile, increasing abstraction emerged in the function concept, which we shall illustrate with the Devil’s staircase, space-filling curves, and the Conway base 13 function. Finally, does the indispensability of mathematics for science ground mathematical truth? Fictionalism puts this in question.

Lecture 3. Infinity

We shall follow the allegory of Hilbert’s hotel and the paradox of Galileo to the equinumerosity relation and the notion of countability. Cantor’s diagonal arguments, meanwhile, reveal uncountability and a vast hierarchy of different orders of infinity; some arguments give rise to the distinction between constructive and nonconstructive proof. Zeno’s paradox highlights classical ideas on potential versus actual infinity. Furthermore, we shall count into the transfinite ordinals.

Lecture 4. Geometry

Classical Euclidean geometry is the archetype of a mathematical deductive process. Yet the impossibility of certain constructions by straightedge and compass, such as doubling the cube, trisecting the angle, or squaring the circle, hints at geometric realms beyond Euclid. The rise of non-Euclidean geometry, especially in light of scientific theories and observations suggesting that physical reality is not Euclidean, challenges previous accounts of what geometry is about. New formalizations, such as those of David Hilbert and Alfred Tarski, replace the old axiomatizations, augmenting and correcting Euclid with axioms on completeness and betweenness. Ultimately, Tarski’s decision procedure points to a tantalizing possibility of automation in geometrical reasoning.

Lecture 5. Proof

What is proof? What is the relation between proof and truth? Is every mathematical truth true for a reason? After clarifying the distinction between syntax and semantics and discussing various views on the nature of proof, including proof-as-dialogue, we shall consider the nature of formal proof. We shall highlight the importance of soundness, completeness, and verifiability in any formal proof system, outlining the central ideas used in proving the completeness theorem. The compactness property distills the finiteness of proofs into an independent, purely semantic consequence. Computer-verified proof promises increasing significance; its role is well illustrated by the history of the four-color theorem. Nonclassical logics, such as intuitionistic logic, arise naturally from formal systems by weakening the logical rules.

Lecture 6. Computability

What is computability? Kurt Gödel defined a robust class of computable functions, the primitive recursive functions, and yet he gave reasons to despair of a fully satisfactory answer. Nevertheless, Alan Turing’s machine concept of computability, growing out of a careful philosophical analysis of the nature of human computability, proved robust and laid a foundation for the contemporary computer era; the widely accepted Church-Turing thesis asserts that Turing had the right notion. The distinction between computable decidability and computable enumerability, highlighted by the undecidability of the halting problem, shows that not all mathematical problems can be solved by machine, and a vast hierarchy looms in the Turing degrees, an infinitary information theory. Complexity theory refocuses the subject on the realm of feasible computation, with the still-unsolved P versus NP problem standing in the background of nearly every serious issue in theoretical computer science.

Lecture 7. Incompleteness

David Hilbert sought to secure the consistency of higher mathematics by finitary reasoning about the formalism underlying it, but his program was dashed by Gödel’s incompleteness theorems, which show that no consistent formal system can prove even its own consistency, let alone the consistency of a higher system. We shall describe several proofs of the first incompleteness theorem, via the halting problem, self-reference, and definability, showing senses in which we cannot complete mathematics. After this, we shall discuss the second incompleteness theorem, the Rosser variation, and Tarski’s theorem on the nondefinability of truth. Ultimately, one is led to the inherent hierarchy of consistency strength rising above every foundational mathematical theory.

Lecture 8. Set Theory

We shall discuss the emergence of set theory as a foundation of mathematics. Cantor founded the subject with key set-theoretic insights, but Frege’s formal theory was naive, refuted by the Russell paradox. Zermelo’s set theory, in contrast, grew ultimately into the successful contemporary theory, founded upon a cumulative conception of the set-theoretic universe. Set theory was simultaneously a new mathematical subject, with its own motivating questions and tools, but it also was a new foundational theory with a capacity to represent essentially arbitrary abstract mathematical structure. Sophisticated technical developments, including in particular, the forcing method and discoveries in the large cardinal hierarchy, led to a necessary engagement with deep philosophical concerns, such as the criteria by which one adopts new mathematical axioms and set-theoretic pluralism.

Lectures on the Philosophy of Mathematics

[bibtex key=”Hamkins2021:Lectures-on-the-philosophy-of-mathematics”]

Now available for preorder!

From the Preface:

Philosophical conundrums pervade mathematics, from fundamental questions of mathematical ontology—What is a number? What is infinity?—to questions about the relations among truth, proof, and meaning. What is the role of figures in geometric argument? Do mathematical objects exist that we cannot construct? Can every mathematical question be solved in principle by computation? Is every truth of mathematics true for a reason? Can every mathematical truth be proved?

This book is an introduction to the philosophy of mathematics, in which we shall consider all these questions and more. I come to the subject from mathematics, and I have strived in this book for what I hope will be a fresh approach to the philosophy of mathematics—one grounded in mathematics, motivated by mathematical inquiry or mathematical practice. I have strived to treat philosophical issues as they arise organically in mathematics. Therefore, I have organized the book by mathematical themes, such as number, infinity, geometry, and computability, and I have included some mathematical arguments and elementary proofs when they bring philosophical issues to light.