An introduction to the philosophy of mathematics grounded in mathematics and motivated by mathematical inquiry and practice. In this book, Joel David Hamkins offers an introduction to the philosophy of mathematics that is grounded in mathematics and motivated by mathematical inquiry and practice. He treats philosophical issues as they arise organically in mathematics, discussing such topics as platonism, realism, logicism, structuralism, formalism, infinity, and intuitionism in mathematical contexts. He organizes the book by mathematical themes--numbers, rigor, geometry, proof, (...) computability, incompleteness, and set theory--that give rise again and again to philosophical considerations. (shrink)

An introduction to writing proofs, presented through compelling mathematical statements with interesting elementary proofs. This book offers an introduction to the art and craft of proof-writing. The author, a leading research mathematician, presents a series of engaging and compelling mathematical statements with interesting elementary proofs. These proofs capture a wide range of topics, including number theory, combinatorics, graph theory, the theory of games, geometry, infinity, order theory, and real analysis. The goal is to show students and aspiring mathematicians how to (...) write proofs with elegance and precision. (shrink)

A textbook for students who are learning how to write a mathematical proof, a validation of the truth of a mathematical statement.

We analyze the precise modal commitments of several natural varieties of set-theoretic potentialism, using tools we develop for a general model-theoretic account of potentialism, building on those of Hamkins, Leibman and Löwe [14], including the use of buttons, switches, dials and ratchets. Among the potentialist conceptions we consider are: rank potentialism, Grothendieck–Zermelo potentialism, transitive-set potentialism, forcing potentialism, countable-transitive-model potentialism, countable-model potentialism, and others. In each case, we identify lower bounds for the modal validities, which are generally either S4.2 or (...) S4.3, and an upper bound of S5, proving in each case that these bounds are optimal. The validity of S5 in a world is a potentialist maximality principle, an interesting set-theoretic principle of its own. The results can be viewed as providing an analysis of the modal commitments of the various set-theoretic multiverse conceptions corresponding to each potentialist account. (shrink)

The multiverse view in set theory, introduced and argued for in this article, is the view that there are many distinct concepts of set, each instantiated in a corresponding set-theoretic universe. The universe view, in contrast, asserts that there is an absolute background set concept, with a corresponding absolute set-theoretic universe in which every set-theoretic question has a definite answer. The multiverse position, I argue, explains our experience with the enormous range of set-theoretic possibilities, a phenomenon that challenges the universe (...) view. In particular, I argue that the continuum hypothesis is settled on the multiverse view by our extensive knowledge about how it behaves in the multiverse, and as a result it can no longer be settled in the manner formerly hoped for. (shrink)

The lottery preparation, a new general kind of Laver preparation, works uniformly with supercompact cardinals, strongly compact cardinals, strong cardinals, measurable cardinals, or what have you. And like the Laver preparation, the lottery preparation makes these cardinals indestructible by various kinds of further forcing. A supercompact cardinal κ, for example, becomes fully indestructible by <κ-directed closed forcing; a strong cardinal κ becomes indestructible by κ-strategically closed forcing; and a strongly compact cardinal κ becomes indestructible by, among others, the forcing to (...) add a Cohen subset to κ, the forcing to shoot a club Cκ avoiding the measurable cardinals and the forcing to add various long Prikry sequences. The lottery preparation works best when performed after fast function forcing, which adds a new completely general kind of Laver function for any large cardinal, thereby freeing the Laver function concept from the supercompact cardinal context. (shrink)

Recently in the philosophical literature there has been some effort made to understand the proper application of the theory of utilitarianism to worlds in which there are infinitely many bearers of utility. Here, we point out that one of the best, most inclusive principles proposed to date contradicts fundamental utilitarian ideas, such as the idea that adding more utility makes a better world.

According to the math tea argument, there must be real numbers that we cannot describe or define, because there are uncountably many real numbers, but only countably many definitions. And yet, the existence of pointwise-definable models of set theory, in which every individual is definable without parameters, challenges this conclusion. In this article, I introduce a flexible new method for constructing pointwise-definable models of arithmetic and set theory, showing furthermore that every countable model of Zermelo-Fraenkel ZF set theory and of (...) Peano arithmetic PA has a pointwise-definable end extension. In the arithmetic case, I use the universal algorithm and its Σ n generalizations to build a progressively elementary tower making any desired individual a n definable at each stage n, while preserving these definitions through to the limit model, which can thus be arranged to be pointwise definable. A similar method works in set theory, and one can moreover achieve V = L in the extension or indeed any other suitable theory holding in an inner model of the original model, thereby fulfilling the resurrection phenomenon. For example, every countable model of ZF with an inner model with a measurable cardinal has an end extension to a pointwise-definable model of ZFC + V = L[μ]. (shrink)

We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. Everyset. for example, is decidable by such machines, and the semi-decidable sets form a portion of thesets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.

The Lévy-Solovay Theorem [8] limits the kind of large cardinal embeddings that can exist in a small forcing extension. Here I announce a generalization of this theorem to a broad new class of forcing notions. One consequence is that many of the forcing iterations most commonly found in the large cardinal literature create no new weakly compact cardinals, measurable cardinals, strong cardinals, Woodin cardinals, strongly compact cardinals, supercompact cardinals, almost huge cardinals, huge cardinals, and so on.

The dream solution of the continuum hypothesis would be a solution by which we settle the continuum hypothesis on the basis of a newly discovered fundamental principle of set theory, a missing axiom, widely regarded as true. Such a dream solution would indeed be a solution, since we would all accept the new axiom along with its consequences. In this article, however, I argue that such a dream solution to $\mathrm {CH}$ is unattainable.

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

We introduce the resurrection axioms, a new class of forcing axioms, and the uplifting cardinals, a new large cardinal notion, and prove that various instances of the resurrection axioms are equiconsistent over ZFC with the existence of an uplifting cardinal.

In this paper, following an idea of Christophe Chalons. I propose a new kind of forcing axiom, the Maximality Principle, which asserts that any sentence varphi holding in some forcing extension $V^P$ and all subsequent extensions $V^{P\ast Q}$ holds already in V. It follows, in fact, that such sentences must also hold in all forcing extensions of V. In modal terms, therefore, the Maximality Principle is expressed by the scheme $(\lozenge \square \varphi) \Rightarrow \square \varphi$ , and is equivalent to (...) the modal theory S5. In this article. I prove that the Maximality Principle is relatively consistent with ZFC. A boldface version of the Maximality Principle, obtained by allowing real parameters to appear in φ, is equiconsistent with the scheme asserting that $V_\delta \prec V$ for an inaccessible cardinal δ, which in turn is equiconsistent with the scheme asserting that ORD is Mahlo. The strongest principle along these lines is $\square MP\!_{\!\!\!\!\!\!_{\!\!_\sim}}$ , which asserts that $MP\!_{\!\!\!\!\!\!_{\!\!_\sim}}$ holds in V and all forcing extensions. From this, it follows that $0^\#$ exists, that $x^\#$ exists for every set x, that projective truth is invariant by forcing, that Woodin cardinals are consistent and much more. Many open questions remain. (shrink)

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

We present several generalizations of the well-known Kunen inconsistency that there is no nontrivial elementary embedding from the set-theoretic universe V to itself. For example, there is no elementary embedding from the universe V to a set-forcing extension V[G], or conversely from V[G] to V, or more generally from one set-forcing ground model of the universe to another, or between any two models that are eventually stationary correct, or from V to HOD, or conversely from HOD to V, or indeed (...) from any definable class to V, among many other possibilities we consider, including generic embeddings, definable embeddings and results not requiring the axiom of choice. We have aimed in this article for a unified presentation that weaves together some previously known unpublished or folklore results, several due to Woodin and others, along with our new contributions. (shrink)

We introduce the $\Sigma _1$ -definable universal finite sequence and prove that it exhibits the universal extension property amongst the countable models of set theory under end-extension. That is, the sequence is $\Sigma _1$ -definable and provably finite; the sequence is empty in transitive models; and if M is a countable model of set theory in which the sequence is s and t is any finite extension of s in this model, then there is an end-extension of M to a (...) model in which the sequence is t. Our proof method grows out of a new infinitary-logic-free proof of the Barwise extension theorem, by which any countable model of set theory is end-extended to a model of $V=L$ or indeed any theory true in a suitable submodel of the original model. The main theorem settles the modal logic of end-extensional potentialism, showing that the potentialist validities of the models of set theory under end-extensions are exactly the assertions of S4. Finally, we introduce the end-extensional maximality principle, which asserts that every possibly necessary sentence is already true, and show that every countable model extends to a model satisfying it. (shrink)

The halting problem for Turing machines is decidable on a set of asymptotic probability one. The proof is sensitive to the particular computational models.

The Gap Forcing Theorem, a key contribution of this paper, implies essentially that after any reverse Easton iteration of closed forcing, such as the Laver preparation, every supercompactness measure on a supercompact cardinal extends a measure from the ground model. Thus, such forcing can create no new supercompact cardinals, and, if the GCH holds, neither can it increase the degree of supercompactness of any cardinal; in particular, it can create no new measurable cardinals. In a crescendo of what I call (...) exact preservation theorems, I use this new technology to perform a kind of partial Laver preparation, and thereby finely control the class of posets which preserve a supercompact cardinal. Eventually, I prove the ‘As You Like It’ Theorem, which asserts that the class of κ -directed closed posets which preserve a supercompact cardinal κ can be made by forcing to conform with any pre-selected local definition which respects the equivalence of forcing. Along the way I separate completely the levels of the superdestructibility hierarchy, and, in an epilogue, prove that the notions of fragility and superdestructibility are orthogonal — all four combinations are possible. (shrink)

Small forcing always ruins the indestructibility of an indestructible supercompact cardinal. In fact, after small forcing, any cardinal κ becomes superdestructible--any further <κ--closed forcing which adds a subset to κ will destroy the measurability, even the weak compactness, of κ. Nevertheless, after small forcing indestructible cardinals remain resurrectible, but never strongly resurrectible.

The main theorem of this article is that every countable model of set theory 〈M, ∈M〉, including every well-founded model, is isomorphic to a submodel of its own constructible universe 〈LM, ∈M〉 by means of an embedding j : M → LM. It follows from the proof that the countable models of set theory are linearly pre-ordered by embeddability: if 〈M, ∈M〉 and 〈N, ∈N〉 are countable models of set theory, then either M is isomorphic to a submodel of N (...) or conversely. Indeed, these models are pre-well-ordered by embeddability in order-type exactly ω1+ 1. Specifically, the countable well-founded models are ordered under embeddability exactly in accordance with the heights of their ordinals; every shorter model embeds into every taller model; every model of set theory M is universal for all countable well-founded binary relations of rank at most OrdM; and every ill-founded model of set theory is universal for all countable acyclic binary relations. Finally, strengthening a classical theorem of Ressayre, the proof method shows that if M is any nonstandard model of PA, then every countable model of set theory — in particular, every model of ZFC plus large cardinals — is isomorphic to a submodel of the hereditarily finite sets 〈 HFM, ∈M〉 of M. Indeed, 〈 HFM, ∈M〉 is universal for all countable acyclic binary relations. (shrink)

A pointwise definable model is one in which every object is \loos definable without parameters. In a model of set theory, this property strengthens $V=\HOD$, but is not first-order expressible. Nevertheless, if \ZFC\ is consistent, then there are continuum many pointwise definable models of \ZFC. If there is a transitive model of \ZFC, then there are continuum many pointwise definable transitive models of \ZFC. What is more, every countable model of \ZFC\ has a class forcing extension that is pointwise definable. (...) Indeed, for the main contribution of this article, every countable model of Gödel-Bernays set theory has a pointwise definable extension, in which every set and class is first-order definable without parameters. (shrink)

Using the lottery preparation, we prove that any strongly unfoldable cardinal $\kappa$ can be made indestructible by all.

After reviewing various natural bi-interpretations in urelement set theory, including second-order set theories with urelements, we explore the strength of second-order reflection in these contexts. Ultimately, we prove, second-order reflection with the abundant atom axiom is bi-interpretable and hence also equiconsistent with the existence of a supercompact cardinal. The proof relies on a reflection characterization of supercompactness, namely, a cardinal κ is supercompact if and only if every Π11 sentence true in a structure M (of any size) containing κ in (...) a language of size less than κ is also true in a substructure m≺M of size less than κ with m∩κ∈κ. (shrink)

We analyze the effect of replacing several natural uses of definability in set theory by the weaker model-theoretic notion of algebraicity. We find, for example, that the class of hereditarily ordinal algebraic sets is the same as the class of hereditarily ordinal definable sets; that is, $\mathrm{HOA}=\mathrm{HOD}$. Moreover, we show that every algebraic model of $\mathrm{ZF}$ is actually pointwise definable. Finally, we consider the implicitly constructible universe Imp—an algebraic analogue of the constructible universe—which is obtained by iteratively adding not only (...) the sets that are definable over what has been built so far, but also those that are algebraic over the existing structure. While we know that $\mathrm{Imp}$ can differ from $L$, the subtler properties of this new inner model are just now coming to light. Many questions remain open. (shrink)

Applying the seed concept to Prikry tree forcing P μ , I investigate how well P μ preserves the maximality property of ordinary Prikry forcing and prove that P μ Prikry sequences are maximal exactly when μ admits no non-canonical seeds via a finite iteration. In particular, I conclude that if μ is a strongly normal supercompactness measure, then P μ Prikry sequences are maximal, thereby proving, for a large class of measures, a conjecture of W. Hugh Woodin's.

We introduce the strongly uplifting cardinals, which are equivalently characterized, we prove, as the superstrongly unfoldable cardinals and also as the almost-hugely unfoldable cardinals, and we show that their existence is equiconsistent over ZFC with natural instances of the boldface resurrection axiom, such as the boldface resurrection axiom for proper forcing.

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

If the Wholeness Axiom wa $_0$ is itself consistent, then it is consistent with v=hod. A consequence of the proof is that the various Wholeness Axioms are not all equivalent. Additionally, the theory zfc+wa $_0$ is finitely axiomatizable.

After small forcing, any $ -closed forcing will destroy the supercompactness and even the strong compactness of κ.

Unfoldable cardinals are preserved by fast function forcing and the Laver-like preparations that fast functions support. These iterations show, by set-forcing over any model of ZFC, that any given unfoldable cardinal κ can be made indestructible by the forcing to add any number of Cohen subsets to κ.

We consider a set-theoretic version of mereology based on the inclusion relation ⊆ and analyze how well it might serve as a foundation of mathematics. After establishing the non-definability of ∈ from ⊆, we identify the natural axioms for ⊆-based mereology, which constitute a finitely axiomatizable, complete, decidable theory. Ultimately, for these reasons, we conclude that this form of set-theoretic mereology cannot by itself serve as a foundation of mathematics. Meanwhile, augmented forms of set-theoretic mereology, such as that obtained by (...) adding the singleton operator, are foundationally robust. (shrink)

Superstrong cardinals are never Laver indestructible. Similarly, almost huge cardinals, huge cardinals, superhuge cardinals, rank-into-rank cardinals, extendible cardinals, 1-extendible cardinals, 0-extendible cardinals, weakly superstrong cardinals, uplifting cardinals, pseudo-uplifting cardinals, superstrongly unfoldable cardinals, Σn-reflecting cardinals, Σn-correct cardinals and Σn-extendible cardinals are never Laver indestructible. In fact, all these large cardinal properties are superdestructible: if κ exhibits any of them, with corresponding target θ, then in any forcing extension arising from nontrivial strategically <κ-closed forcing Q∈Vθ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} (...) \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{Q} \in V_\theta}$$\end{document}, the cardinal κ will exhibit none of the large cardinal properties with target θ or larger. (shrink)

If G is a centreless group, then τ denotes the height of the automorphism tower of G. We prove that it is consistent that for every cardinal λ and every ordinal α<λ, there exists a centreless group G such that τ=α; and if β is any ordinal such that 1β<λ, then there exists a notion of forcing , which preserves cofinalities and cardinalities, such that τ=β in the corresponding generic extension.

The infinite time Turing machine analogue of Post's problem, the question whether there are semi-decidable supertask degrees between 0 and the supertask jump 0∇, has in a sense both positive and negative solutions. Namely, in the context of the reals there are no degrees between 0 and 0∇, but in the context of sets of reals, there are; indeed, there are incomparable semi-decidable supertask degrees. Both arguments employ a kind of transfinite-injury construction which generalizes canonically to oracles.

The class forcing theorem, which asserts that every class forcing notion ${\mathbb {P}}$ admits a forcing relation $\Vdash _{\mathbb {P}}$, that is, a relation satisfying the forcing relation recursion—it follows that statements true in the corresponding forcing extensions are forced and forced statements are true—is equivalent over Gödel–Bernays set theory $\text {GBC}$ to the principle of elementary transfinite recursion $\text {ETR}_{\text {Ord}}$ for class recursions of length $\text {Ord}$. It is also equivalent to the existence of truth predicates for the (...) infinitary languages $\mathcal {L}_{\text {Ord},\omega }$, allowing any class parameter A; to the existence of truth predicates for the language $\mathcal {L}_{\text {Ord},\text {Ord}}$ ; to the existence of $\text {Ord}$ -iterated truth predicates for first-order set theory $\mathcal {L}_{\omega,\omega }$ ; to the assertion that every separative class partial order ${\mathbb {P}}$ has a set-complete class Boolean completion; to a class-join separation principle; and to the principle of determinacy for clopen class games of rank at most $\text {Ord}+1$. Unlike set forcing, if every class forcing notion ${\mathbb {P}}$ has a forcing relation merely for atomic formulas, then every such ${\mathbb {P}}$ has a uniform forcing relation applicable simultaneously to all formulas. Our results situate the class forcing theorem in the rich hierarchy of theories between $\text {GBC}$ and Kelley–Morse set theory $\text {KM}$. (shrink)

We show that the theory, consisting of the usual axioms of but with the power set axiom removed—specifically axiomatized by extensionality, foundation, pairing, union, infinity, separation, replacement and the assertion that every set can be well‐ordered—is weaker than commonly supposed and is inadequate to establish several basic facts often desired in its context. For example, there are models of in which ω1 is singular, in which every set of reals is countable, yet ω1 exists, in which there are sets of (...) reals of every size, but none of size, and therefore, in which the collection axiom fails; there are models of for which the Łoś theorem fails, even when the ultrapower is well‐founded and the measure exists inside the model; there are models of for which the Gaifman theorem fails, in that there is an embedding of models that is Σ1‐elementary and cofinal, but not elementary; there are elementary embeddings of models whose cofinal restriction is not elementary. Moreover, the collection of formulas that are provably equivalent in to a Σ1‐formula or a Π1‐formula is not closed under bounded quantification. Nevertheless, these deficits of are completely repaired by strengthening it to the theory, obtained by using collection rather than replacement in the axiomatization above. These results extend prior work of Zarach. (shrink)

The generic Vopěnka principle, we prove, is relatively consistent with the ordinals being non-Mahlo. Similarly, the generic Vopěnka scheme is relatively consistent with the ordinals being definably non-Mahlo. Indeed, the generic Vopěnka scheme is relatively consistent with the existence of a \-definable class containing no regular cardinals. In such a model, there can be no \-reflecting cardinals and hence also no remarkable cardinals. This latter fact answers negatively a question of Bagaria, Gitman and Schindler.

Can a supercompact cardinal κ be Laver indestructible when there is a level-by-level agreement between strong compactness and supercompactness? In this article, we show that if there is a sufficiently large cardinal above κ, then no, it cannot. Conversely, if one weakens the requirement either by demanding less indestructibility, such as requiring only indestructibility by stratified posets, or less level-by-level agreement, such as requiring it only on measure one sets, then yes, it can.

If ZFC is consistent, then the collection of countable computably saturated models of ZFC satisfies all of the Multiverse Axioms of Hamkins.

The assertion that every definable set has a definable element is equivalent over to the principle, and indeed, we prove, so is the assertion merely that every Π2‐definable set has an ordinal‐definable element. Meanwhile, every model of has a forcing extension satisfying in which every Σ2‐definable set has an ordinal‐definable element. Similar results hold for and and other natural instances of.

The rigid relation principle, introduced in this article, asserts that every set admits a rigid binary relation. This follows from the axiom of choice, because well-orders are rigid, but we prove that it is neither equivalent to the axiom of choice nor provable in Zermelo-Fraenkel set theory without the axiom of choice. Thus, it is a new weak choice principle. Nevertheless, the restriction of the principle to sets of reals is provable without the axiom of choice.

I consider the natural infinitary variations of the games Wordle and Mastermind, as well as their game‐theoretic variations Absurdle and Madstermind, considering these games with infinitely long words and infinite color sequences and allowing transfinite game play. For each game, a secret codeword is hidden, which the codebreaker attempts to discover by making a series of guesses and receiving feedback as to their accuracy. In Wordle with words of any size from a finite alphabet of n letters, including infinite words (...) or even uncountable words, the codebreaker can nevertheless always win in n steps. Meanwhile, the mastermind number, defined as the smallest winning set of guesses in infinite Mastermind for sequences of length ω over a countable set of colors without duplication, is uncountable, but the exact value turns out to be independent of, for it is provably equal to the eventually different number, which is the same as the covering number of the meager ideal. I thus place all the various mastermind numbers, defined for the natural variations of the game, into the hierarchy of cardinal characteristics of the continuum. (shrink)

We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.

If κ is any strongly unfoldable cardinal, then this is preserved in a forcing extension in which κ fails. This result continues the progression of the corresponding results for weakly compact cardinals, due to Woodin, and for indescribable cardinals, due to Hauser.