Infinity, University of Notre Dame, Spring 2023

Infinity

Philosophy 20607 01 (32582)

University of Notre Dame                                                                              Spring 2023

Instructor: Joel David Hamkins, O’Hara Professor of Philosophy and Mathematics
3:30-4:45 Tuesdays + Thursdays, DeBartolo Hall 208

Course Description. This course will be a mathematical and philosophical exploration of infinity, covering a wide selection of topics illustrating this rich, fascinating concept—the mathematics and philosophy of the infinite.

Along the way, we shall find paradox and fun—and all my favorite elementary logic conundrums and puzzles. It will be part of my intention to reveal what I can of the quirky side of mathematics and logic in its connection with infinity, but with a keen eye open for when issues happen to engage with philosophically deeper foundational matters.

The lectures will be based on the chapters of my forthcoming book, The Book of Infinity, currently in preparation, and currently being serialized and made available on the Substack website as I explain below.

Topics. Among the topics we shall aim to discuss will be:

  • The Book of Numbers
  • Zeno’s paradox
  • The infinite coastline paradox
  • Supertasks
  • Largest number contest
  • The googol plex chitty bang stack hierarchy
  • Galileo’s Salviati on infinity
  • Hilbert’s Grand Hotel
  • The uncountable
  • How to count (to infinity and beyond!)
  • Slaying the Hydra
  • Transfinite recursion
  • The continuum hypothesis
  • The axiom of choice
  • Orders of infinity
  • The lattice of subsets of ℕ
  • Potential versus actual infinity
  • Confounding puzzles of infinity
  • Infinite liars
  • Infinite utilitarianism
  • Infinite computation
  • Infinite games
  • Indescribable numbers
  • Extremely remote events of enormous consequence
  • The sand reckoner
  • Paradox in high dimension
  • The outer limits of reason
  • Puzzles of epistemic logic and the problem of common knowledge

Mathematical background. The course will at times involve topics and concepts of a fundamentally mathematical nature, but no particular mathematical background or training will be assumed. Nevertheless, it is expected that students be open to mathematical thinking and ideas, and furthermore it is a core aim of the course to help develop the student’s mastery over various mathematical concepts connected with infinity.  

Readings. The lectures will be based on readings from the topic list above that will be made available on my Substack web page, Infinitely More. Readings for the topic list above will be gradually released there during the semester. Each reading will consist of a chapter essay my book-in-progress, The Book of Infinity, which is being serialized on the Substack site specifically for this course. In some weeks, there will be supplemental readings from other sources.

Student access. I will issue subscription invitations to the Substack site for all registered ND students using their ND email, with free access to the site during the semester, so that students can freely access the readings.  Students are free to manage their subscriptions however they see fit. Please inform me of any access issues. There are some excellent free Substack apps available for Apple iOS and Android for reading Substack content on a phone or other device.

Discussion forum. Students are welcome to participate in the discussion forums provided with the readings to discuss the topics, the questions, to post answer ideas, or engage in the discussion there. I shall try to participate myself by posting comments or hints.

Homework essays. Students are expected to engage fully with every topic covered in the class. Every chapter concludes with several Questions for Further Thought, with which the students should engage. It will be expected that students complete approximately half of the Questions for Further thought. Each question that is answered should be answered essay-style with a mini-essay of about half a page or more.

Extended essays. A student may choose at any time to answer one of the Questions for Further Thought more fully with a more extended essay of two or three pages, and in this case, other questions on that particular topic need not be engaged. Every student should plan to exercise this option at least twice during the semester.

Final exam.  There will be a final exam consisting of questions similar to those in the Questions for Further Thought, covering every topic that was covered in the course. The final grade will be based on the final exam and on the submitted homework solutions.

Open Invitation. Students outside of Notre Dame are welcome to follow along with the Infinity course, readings, and online discussion. Simply subscribe at Infinitely More, keep up with the readings and participate in the discussions we shall be having in the forums there.

Strategic thinking in infinite games, CosmoCaixa Science Museum, Barcelona, March 2023

I am deeply honored to be invited by la Caixa Foundation to give a talk in “The Greats of Science” talk series, to be held 16 March 2023 at the CosmoCaixa Science Museum in Barcelona. This talk series aspires to host “prestigious figures who have contributed towards admirable milestones, studies or discoveries,” who will bring the science to a general audience, aiming to “give viewers the chance to explore the most relevant parts of contemporary sicence through the top scientists of the moment.” Previous speakers include Jane Goodall and nearly a dozen Nobel Prize winners since 2018.

Cosmo Caixa announcement

I hope to rise to those high expectations!

My topic will be: Strategic thinking in infinite games.

Have you time for an infinite game? Many familiar finite games admit natural infinitary analogues, infinite games that may captivate and challenge us with intriguing patterns and sublime complexity. Shall we have a game of infinite chess? Or how about infinite draughts, infinite Hex, infinite Wordle, or infinite Sudoku? In the Chocolatier’s game, the Chocolatier serves up an infinite stream of delicious morsels, while the Glutton aims to eat every one. These games and others illustrate the often subtle strategic aspects of infinite games, and sometimes their downright logical peculiarity. Does every infinite game admit of a winning strategy? Must optimal play be in principle computable? Let us discover the fascinating nature of infinitary strategic thinking.

The theory builds upon the classical finitary result of Zermelo (1913), the fundamental theorem of finite games, which shows that in every finite two-player game of perfect information, one of the players must have a winning strategy or both players have draw-or-better strategies. This result extends to certain infinitary games by means of the ordinal game-value analysis, which assigns transfinite ordinal values $\alpha$ to positions in a game, generalizing the familiar mate-in-$n$ idea of chess to the infinite. Current work realizes high transfinite game values in infinite chess, infinite draughts (checkers), infinite Go, and many other infinite games. The highest-known game value arising in infinite chess is the infinite ordinal $\omega^4$, and every countable ordinal arises in infinite draughts, the optimal result. Games exhibiting high transfinite ordinal game values have a surreal absurd character of play. The winning player will definitely win in finitely many moves, but the doomed losing player controls the process with absurdly long deeply nested patterns of forcing moves that must be answered, as though counting down from the infinite game value—when 0 is reached, the game is over.

A model of set theory with a definable copy of the complex field in which the two roots of -1 are set-theoretically indiscernible

Mathematicians are deeply familiar with the complex number field $\newcommand\C{\mathbb{C}}\C$, the algebraic closure of the real field $\newcommand\R{\mathbb{R}}\R$, which can be constructed from $\R$ by adjoining a new ideal element $i$, the imaginary unit, and forming the complex numbers $a+bi$ as formal pairs, defining the arithmetic subject to the rule $i^2=–1$. Thus we may add and multiply the complex numbers, according to the familiar rules:

$$(a+bi)+(c+di)=(a+c)+(b+d)i$$ $$(a+bi)\cdot(c+di)=(ac-bd)+(ad+bc)i.$$

The complex field thus provides a system of numbers giving sense to expressions like $\sqrt{–1}$, while obeying the familiar algebraic rules of a field. Hamilton had presented this conception of complex numbers as pairs of real numbers to the Royal Irish Academy in 1833.

One may easily observe in the complex numbers, however, that $–i$ is also a square root of $–1$, because

$$(–i)\cdot(–i)=(–1)^2\cdot i^2=i^2=-1.$$

Thus, both $i$ and $–i$ have the property of being square roots of $–1$, and indeed, these are the only square roots of $–1$ in the complex field.

A small conundrum may arise when one realizes that $–i$ therefore also fulfills what might have been taken as the “defining” property of the ideal element $i$, namely, that it squares to $–1$. So this property doesn’t actually define $i$, in light of the fact that there is another distinct object $–i$ that also has this property. Can we tell $i$ and $–i$ apart?

Not in the complex field, no, we cannot. The basic fact is that $i$ and $–i$ are indiscernible as complex numbers with respect to the algebraic structure of $\C$—any property that $i$ has in the structure $\langle\C,+,\cdot,0,1\rangle$ will also hold of $–i$. One way to see this is to observe that complex conjugation, the map $$a+bi\quad\mapsto\quad a-bi$$ is an automorphism of the complex number field, an isomorphism of the structure with itself. And since this automorphism swaps $i$ with $–i$, it follows that any statement true of $i$ in the complex numbers, expressible in the language of fields, will also hold of $–i$.

In fact, the complex number field $\C$ has an extremely rich automorphism group, and every irrational complex number is indiscernible from various doppelgängers. There is an automorphism of $\C$ that swaps $\sqrt{2}$ and $–\sqrt{2}$, for example, and another that permutes the cube roots of $5$, mapping the real root $\sqrt[3]{5}$ with the two nonreal roots. So these numbers can have no property not shared by their various automorphic images. The general fact is that every complex number, except the rational numbers, is moved by some automorphism of $\C$. One can begin to see this by noticing that there are two ways to embed the algebraic field extensions $\newcommand\Q{\mathbb{Q}}\Q(\sqrt{2})$ into $\C$, and both embeddings extend fully to automorphisms of $\C$.

Because there is an automorphism of $\C$ swapping $\sqrt{2}$ and $–\sqrt{2}$, it means that these two numbers are also indiscernible as complex numbers, just like $i$ and $–i$ were—any property that $\sqrt{2}$ holds in the complex numbers is also held by $–\sqrt{2}$. But wait a minute, how can that be? After all, $\sqrt{2}$ is positive and $–\sqrt{2}$ is negative, and isn’t this a property that separates them? Well, yes, in the real numbers $\R$ this is a separating property, and since the order is definable from the algebraic structure of the real field (positive numbers are exactly the nonzero squares), it is a real algebraic property that distinguishes $\sqrt{2}$ from $–\sqrt{2}$, as only the former has itself a square root in $\R$. But this definition does not work in $\C$, since both have square roots there, and more generally, the surprise is that the real numbers $\R$ are not definable as a subfield in the complex field $\C$—there is no property expressible in the language of fields that picks out exactly the real numbers. There are $2^{2^{\aleph_0}}$ many distinct ways to embed $\R$ as a subfield of $\C$, and none of them is definable in $\C$.

The conclusion is that if we regard the complex numbers with the field structure only, $\langle\C,+,\cdot,0,1\rangle$, then we cannot refer unambiguously to $i$ or $–i$, to $\sqrt{2}$ or $–\sqrt{2}$, or indeed to any irrational complex number. Every irrational number is moved by some automorphism of the complex field. The irrational algebraic numbers can be permuted in their finite sets of indiscernible roots of their irreducible polynomial, and any two transcendental complex numbers (transcendental over $\Q$) are automorphic. For example, there is an automorphism of $\C$ moving $e+2i$ to $1+\sqrt{\pi}i$.

Finding a path out of that chaos, mathematicians like to conceive of $\C$ as a field extension of $\R$, in effect fixing the copy of $\R$ in $\C$. It is as though we are working in the structure $\langle\C,+,\cdot,0,1,\R\rangle$, where we have augmented the complex field structure with a predicate picking out the real numbers. So this isn’t just a field, but a field with an identified subfield. In this structure, $\sqrt{2}$ and $\sqrt[3]{5}$ and so on are definable, since one has identified the real numbers and within that subfield the order on the reals is definable, and so we can define every real algebraic number using this order. With the predicate for $\R$ picking out the reals, the structure has only the one nontrivial automorphism, complex conjugation, and to my way of thinking, this is the reason that the indiscernibility issue is usually considered more prominently with $i$ and $–i$.

The indiscernibility of $i$ and $–i$ in the complex field has been written on at length in the philosophical literature, since it seems to refute a certain philosophical account of structuralism that might otherwise have seemed appealing. Namely, the relevant view is a version of abstract structuralism, the view that what mathematical objects are is the structural role that they play in a mathematical system. On this view the natural number $2$ simply is the role that $2$ plays in Dedekind arithmetic, the role of being the successor of the successor of zero (Dedekind arithmetic is the categorical second-order axiomatization of $\langle\newcommand\N{\mathbb{N}}\N,0,S\rangle$). The view is that what mathematical structure is is the structural roles that objects play in any instance of the structure. The structural role is exactly what is preserved by isomorphism, and so it would seem to be an invariant for the isomorphism orbits of an indidvidual with respect to a structure.

The problem with this version of abstract structuralism is that it seems to be refuted by the example of $i$ and $–i$ in the complex field. Precisely because these numbers are automorphic, they would seem each to play exactly the same role in the complex field—the two numbers are isomorphic copies of one another via complex conjugation. Thus, they are distinct numbers, but play the same structural role, and so we cannot seem to identify the abstract number with the structural roles. This problem occurs, of course, in any mathematical structure that is not rigid.

The numbers $i$ and $–i$ are indiscernible in the field structure of $\C$, but of course we can distinguish them in contexts with additional structure. For example, if we use the Hamilton presentation of the complex numbers as pairs of real numbers, representing $a+bi$ with the pair $(a,b)$, then the number $i$ has coordinates $(0,1)$ and $–i$ has coordinates $(0,-1)$. The complex field equipped with this coordinate structure, perhaps given by the real and imaginary parts operators—let us call it the complex plane, as opposed to the complex field—is a rigid structure in which $i$ and $–i$ are discernible and indeed definable.

Finally, this brings me to the main point of this blog post. What I would like to do is to prove that it is relatively consistent with ZFC that we can definably construct a copy of the complex numbers $\C$ in such a way that not only are $i$ and $–i$ indiscernible in the field structure, but actually the particular set-theoretic objects $i$ and $–i$ are indiscernible in the set-theoretic background in which the construction is undertaken.

Goal. A definable copy of the complex field in which the two square roots of $–1$ are indiscernible not only in the field structure, but also in the set-theoretic background in which the construction of the field takes place.

These two aims are in tension, for we want the particular copy $\C$ to be definable (as a particular set-theoretic object, not just defined up to isomorphism), but the individual square roots of $–1$ to be set-theoretically indiscernible.

The goal is not always possible. For example, some models of ZFC are pointwise definable, meaning that every individual set is definable in them by some distinguishing set-theoretic property. More generally, if the V=HOD axiom holds, then there is a definable global well order of the set-theoretic universe, and with any such order we could define a linear order on $\{i,–i\}$ in any definable copy of $\C$, which would allow us to define each of the roots. For these reasons, in some models of ZFC, it is not possible to achieve the goal, and the most we can hope for a consistency result.

But indeed, the consistency goal is achievable.

Theorem. If ZFC is consistent, then there is a model of ZFC that has a definable complete ordered field $\R$ with a definable algebraic closure $\C$, such that the two square roots of $–1$ in $\C$ are set-theoretically indiscernible, even with ordinal parameters.

Proof. The proof makes use of what are known as Grozek-Laver pairs, definable pair sets having no ordinal-definable element. See M. Groszek & R. Laver, Finite Groups of OD-conjugates, Periodica Mathematica Hungarica, v. 18, pp. 87–97 (1987), for a very general version of this. This theorem also appears at theorem 4.6 in my paper Ehrenfeucht’s lemma in set theory, joint with Gunter Fuchs, Victoria Gitman, and myself. The arguments provide a model of set theory with a definable pair set $A=\{i,j\}$, such that neither element $i$ nor $j$ is definable from ordinal parameters. The pair set is definable, but neither element is definable.

To undertake the construction, we start with one of the standard definable constructions of the real field $\R$. For example, we could use Dedekind cuts in $\Q$, where $\Q$ is constructed explicitly as the quotient field of the integer ring $\mathbb{Z}$ in some canonical definable manner, and where the integers are definably constructed from a definable copy of the natural numbers $\mathbb{N}$, such as the finite von Neumann ordinals. So we have a definable complete ordered field, the real field $\R$.

Given this and the set $A$, we follow a suggestion of Timothy Gowers in the discussion of this problem on Twitter. Namely, we use the elements of $A$ as variables to form the polynomial ring $\R[A]$, meaning $\R[i,j]$, where $i$ and $j$ are the two elements of $A$. It is not necessary to distinguish the elements of $A$ to form this ring of polynomials, since we take all finite polynomial expressions using real coefficients and elements of $A$ raised to a power. (In particular, although I have referred to the elements as $i$ and $j$, there is to be no suggestion that I am somehow saying $i$ is the “real” $i$; I am not, for I could have called them $j$,$i$ or $j$,$k$ or $a$,$a’$, and so on.) Then we quotient by the ideal $(i^2+1,i+j)$, which is defined symmetrically in the elements of $A$, since it is the same ideal as $(j^2+1,j+i)$. Let $\C$ be the quotient $\C=\R[i,j]/(i^2+1,i+j)$, which will make both $i$ and $j$ the two square roots of $–1$, and so by the fundamental theorem of algebra this is a copy of the complex numbers.

Since $\R$ and $A$ were definable, and we didn’t need ever to choose a particular element of $A$ in the construction to define the polynomial ring or the ideal, this copy of $\C$ is definable without parameters. But since $i$ and $j$ are set-theoretically indiscernible in the model of set theory in which we are undertaking the construction, it follows that their equivalence classes in the quotient are also indiscernible. And so we have a definable copy of the complex field $\C$, extending a definable copy of $\R$, in which the two square roots of $–1$ are indiscernible not just in the field structure, but fully in the set-theoretic background in which the fields were constructed. $\Box$

In particular, in this model of set theory, there will be absolutely no way to distinguish the two roots by any further definable structure, whether using second-order or higher-order definitions of the field $\C$ or using any definable set-theoretic property whatsoever.

The analysis suggests a natural further inquiry. Namely,

Question. Is there a model of set theory with a definable copy of the complex field $\C$, such that the hierarchy of relative definability and indiscernibility in $\C$ matches the set-theoretic relative definability and indiscernibility of the objects?

That is, we would want to mimic the phenomenon of $i$ and $–i$ in the above construction with all complex numbers, so that $\sqrt{2}$ and $–\sqrt{2}$ were also indiscernible, not just in this copy of $\C$ but also in the set-theoretic background, and $\sqrt[4]{2}$ was set-theoretically indiscernible from the other new fourth-root of $2$, but can set-theoretically define both $\sqrt{2}$ and $–\sqrt{2}$. In other words, I want the set-theoretic definability hierarchy to match the complex-number-theoretic definability hierarchy. I may post this question on MathOverflow, when I formulate a version of it with which I am satisfied. I believe it will be answered by iterated Sacks forcing in a manner similar to that used in many papers by Marcia Groszek, and in particular, in my paper with her, The Implicitly constructible universe.

Pointwise definable and Leibnizian extensions of models of arithmetic and set theory, MOPA seminar CUNY, November 2022

 This will be an online talk for the MOPA Seminar at CUNY on 22 November 2022 1pm. Contact organizers for Zoom access.

Abstract. I shall introduce a flexible new method showing that every countable model of PA admits a pointwise definable end-extension, one in which every individual is definable without parameters. And similarly for models of set theory, in which one may also achieve the Barwise extension result—every countable model of ZF admits a pointwise definable end-extension to a model of ZFC+V=L, or indeed any theory arising in a suitable inner model. A generalization of the method shows that every model of arithmetic of size at most continuum admits a Leibnizian extension, and similarly in set theory. 

Pseudo-countable models

[bibtex key=”Hamkins:Pseudo-countable-models”]

Download pdf at arXiv:2210.04838

Abstract. Every mathematical structure has an elementary extension to a pseudo-countable structure, one that is seen as countable inside a suitable class model of set theory, even though it may actually be uncountable. This observation, proved easily with the Boolean ultrapower theorem, enables a sweeping generalization of results concerning countable models to a rich realm of uncountable models. The Barwise extension theorem, for example, holds amongst the pseudo-countable models—every pseudo-countable model of ZF admits an end extension to a model of ZFC+V=L. Indeed, the class of pseudo-countable models is a rich multiverse of set-theoretic worlds, containing elementary extensions of any given model of set theory and closed under forcing extensions and interpreted models, while simultaneously fulfilling the Barwise extension theorem, the Keisler-Morley theorem, the resurrection theorem, and the universal finite sequence theorem, among others.

Self-similar self-similarity, in The Language of Symmetry

A playful account of symmetry, contributed as a chapter to a larger work, The Language of Symmetry, edited by Benedict Rattigan, Denis Noble, and Afiq Hatta, a collection of essays on symmetry that were also the basis of an event at the British Museum, The Language of Symmetry.

[bibtex key=”Hamkins2023:Self-similar-self-similarity”]

Pre-order the book at: https://www.routledge.com/The-Language-of-Symmetry/Rattigan-Noble-Hatta/p/book/9781032303949

My essay is available here:

Abstract. Let me tell a mathematician’s tale about symmetry. We begin with playful curiosity about a concrete elementary case—the symmetries of the letters of the alphabet, for instance. Seeking the essence of symmetry, however, we are pushed toward abstraction, to other shapes and higher dimensions. Beyond the geometric figures, we consider the symmetries of an arbitrary mathematical structure—why not the symmetries of the symmetries? And then, of course, we shall have the symmetries of the symmetries of the symmetries, and so on, iterating transfinitely. Amazingly, this process culminates in a sublime self-similar group of symmetries that is its own symmetry group, a self-similar self-similarity.

Download my essay for more…or order the book for the complete set!

Pointwise definable and Leibnizian models of arithmetic and set theory, realized in end extensions of a given model, Notre Dame Logic Seminar, October 2022

This will be a talk for the Notre Dame logic seminar, 11 October 2022, 2pm in Hales-Healey Hall.

Abstract.  I shall present very new results on pointwise definable and Leibnizian end-extensions of models of arithmetic and set theory. Using the universal algorithm, I shall present a new flexible method showing that every countable model of PA admits a pointwise definable $\Sigma_n$-elementary end-extension. Also, any model of PA of size at most continuum admits an extension that is Leibnizian, meaning that any two distinct points are separated by some expressible property. Similar results hold in set theory, where one can also achieve V=L in the extension, or indeed any suitable theory holding in an inner model of the original model.

Every countable model of arithmetic or set theory has a pointwise definable end extension

[bibtex key=”Hamkins:Every-countable-model-of-arithmetic-or-set-theory-has-a-pointwise-definable-end-extension”]

arXiv:2209.12578

Abstract. 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 $\Sigma_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 $\text{ZFC}+V=L[\mu]$.

The sentence asserting its own non-forceability by nontrivial forcing

At the meeting here in Konstanz, Giorgo Venturi and I considered the sentence $\sigma$, which asserts its own non-forceability by nontrivial forcing. That is, $\sigma$ asserts that there is no nontrivial forcing notion forcing $\sigma$. $$\sigma\quad\iff\quad \neg\exists\mathbb{B}\ \Vdash_{\mathbb{B}}\sigma.$$ The sentence $\sigma$ would be a fixed-point of the predicate for not being nontrivially forceable.

In any model of set theory $V$ in which $\sigma$ is true, then in light of what it asserts, it would not be forceable by nontrivial forcing, and so it would be false in all nontrivial forcing extensions of that model $V[G]$. And in any model $W$ where it is false, then because of what it asserts, it would be nontrivially forceable, and so it would be true in some forcing extension of that model $W[G]$.

But this is a contradiction! It cannot ever be true, since if it were true in $V$, it would have to be false in all extensions $V[G]$, and therefore true in some subsequent extension $V[G][H]$. But that model is a forcing extension of $V$, contradicting the claim that it is false in all such extensions.

So it must always be false, but this can’t happen, since then in any given model, in light of what it asserts, it would have to be true. So it cannot ever be true or false.

Conclusion: there is no such sentence σ that asserts its own nontrivial forceability. This is no fixed-point for not being nontrivially forceable.

But doesn’t this contradict the fixed-point lemma? After all, the fixed-point lemma shows that we can produce fixed points for any expressible assertion.

The resolution of the conundrum is that although for any given assertion $\varphi$, we can express “$\varphi$ is forceable”, we cannot express “x is the Gödel code of a forceable sentence”, for reasons similar to those for Tarski’s theorem on the nondefinability of truth.

Therefore, we are not actually in a situation to apply the fixed-point lemma. And ultimately the argument shows that there can be no sentence $\sigma$ that asserts “$\sigma$ is not forceable by nontrivial forcing”.

Ultimately, I find the logic of this sentence $\sigma$, asserting its own non-nontrivial forceability, to be a set-theoretic forcing analogue of the Yablo paradox. The sentence holds in a model of set theory whenever it fails in all subsequent models obtained by forcing, and that relation is exactly what arises in the Yablo paradox.

Fregean abstraction in Zermelo-Fraenkel set theory: a deflationary account

Abstract. The standard treatment of sets and definable classes in first-order Zermelo-Fraenkel set theory accords in many respects with the Fregean foundational framework, such as the distinction between objects and concepts. Nevertheless, in set theory we may define an explicit association of definable classes with set objects $F\mapsto\varepsilon F$ in such a way, I shall prove, to realize Frege’s Basic Law V as a ZF theorem scheme, Russell notwithstanding. A similar analysis applies to the Cantor-Hume principle and to Fregean abstraction generally. Because these extension and abstraction operators are definable, they provide a deflationary account of Fregean abstraction, one expressible in and reducible to set theory—every assertion in the language of set theory allowing the extension and abstraction operators $\varepsilon F$, $\# G$, $\alpha H$ is equivalent to an assertion not using them. The analysis thus sidesteps Russell’s argument, which is revealed not as a refutation of Basic Law V as such, but rather as a version of Tarski’s theorem on the nondefinability of truth, showing that the proto-truth-predicate “$x$ falls under the concept of which $y$ is the extension” is not expressible.

[bibtex key=”Hamkins:Fregean-abstraction-deflationary-account”]

Full text available at arXiv:2209.07845

The math tea argument—must there be numbers we cannot describe or define? Pavia Logic Seminar

Home

This will be a talk for the Philosophy Seminar at the IUSS, Scuola Universitaria Superiore Pavia, 28 September 2022.

(Note: This seminar will be held the day before the related conference Philosophy of Mathematics: Foundations, Definitions and Axioms, Italian Network for the Philosophy of Mathematics, 29 September to 1 October 2022. I shall be speaking at that conference on the topic, Fregean abstraction in set theory, a deflationary account.)

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.

Workshop on the Set-theoretic Multiverse, Konstanz, September 2022

Masterclass of “The set-theoretic multiverse” ten years after

Focused on mathematical and philosophical aspects of the set-theoretic multiverse and the pluralist debate in the philosophy of set theory, this workshop will have a master class on potentialism, a series of several speakers, and a panel discussion. To be held 21-22 September 2022 at the University of Konstanz, Germany. (Contact organizers for Zoom access.)

I shall make several contributions to the meeting.

Master class tutorial on potentialism

I shall give a master class tutorial on potentialism, an introduction to the general theory of potentialism that has been emerging in recent work, often developed as a part of research on set-theoretic pluralism, but just as often branching out to a broader application. Although the debate between potentialism and actualism in the philosophy of mathematics goes back to Aristotle, recent work divorces the potentialist idea from its connection with infinity and undertakes a more general analysis of possible mathematical universes of any kind. Any collection of mathematical structures forms a potentialist system when equipped with an accessibility relation (refining the submodel relation), and one can define the modal operators of possibility $\Diamond\varphi$, true at a world when $\varphi$ is true in some larger world, and necessity $\Box\varphi$, true in a world when $\varphi$ is true in all larger worlds. The project is to understand the structures more deeply by understanding their modal nature in the context of a potentialist system. The rise of modal model theory investigates very general instances of potentialist system, for sets, graphs, fields, and so on. Potentialism for the models of arithmetic often connects with deeply philosophical ideas on ultrafinitism. And the spectrum of potentialist systems for the models of set theory reveals fundamentally different conceptions of set-theoretic pluralism and possibility.

The multiverse view on the axiom of constructibility

I shall give a talk on the multiverse perspective on the axiom of constructibility. Set theorists often look down upon the axiom of constructibility V=L as limiting, in light of the fact that all the stronger large cardinals are inconsistent with this axiom, and furthermore the axiom expresses a minimizing property, since $L$ is the smallest model of ZFC with its ordinals. Such views, I argue, stem from a conception of the ordinals as absolutely completed. A potentialist conception of the set-theoretic universe reveals a sense in which every set-theoretic universe might be extended (in part upward) to a model of V=L. In light of such a perspective, the limiting nature of the axiom of constructibility tends to fall away.

Panel discussion: The multiverse view—challenges for the next ten years

This will be a panel discussion on the set-theoretic multiverse, with panelists including myself, Carolin Antos-Kuby, Giorgio Venturi, and perhaps others.

Pointwise definable end-extensions of the universe, Sophia 2022, Salzburg

This will be an online talk for the Salzburg Conference for Young Analytical Philosophy, the SOPhiA 2022 Salzburgiense Concilium Omnibus Philosophis Analyticis, with a special workshop session Reflecting on ten years of the set-theoretic multiverse. The workshop will meet Thursday 8 September 2022 4:00pm – 7:30pm.

The name of the workshop (“Reflecting on ten years…”), I was amazed to learn, refers to the period since my 2012 paper, The set-theoretic multiverse, in the Review of Symbolic Logic, in which I had first introduced my arguments and views concerning set-theoretic pluralism. I am deeply honored by this workshop highlighting my work in this way and focussing on the developments growing out of it.

In this talk, I shall engage in that discussion by presenting some very new work connecting several topics that have been prominent in discussions of the set-theoretic multiverse, namely, set-theoretic potentialism and pointwise definability.

Abstract. Using the universal algorithm and its generalizations, I shall present new work on the possibility of end-extending any given countable model of arithmetic or set theory to a pointwise definable model, one in which every object is definable without parameters. Every countable model of Peano arithmetic, for example, admits an end-extension to a pointwise definable model. And similarly, every countable model of ZF set theory admits an end-extension to a pointwise definable model of ZFC+V=L, as well as to pointwise definable models of other sufficient theories, accommodating large cardinals. I shall discuss the philosophical significance of these results in the philosophy of set theory with a view to potentialism and the set-theoretic multiverse.

Nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength

[bibtex key=”Hamkins:Nonlinearity-in-the-hierarchy-of-large-cardinal-consistency-strength”]

arXiv:2208.07445

Abstract. Many set theorists point to the linearity phenomenon in the hierarchy of consistency strength, by which natural theories tend to be linearly ordered and indeed well ordered by consistency strength. Why should it be linear? In this paper I present counterexamples, natural instances of nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength, as natural or as nearly natural as I can make them. I present diverse cautious enumerations of ZFC and large cardinal set theories, which exhibit incomparability and illfoundedness in consistency strength, and yet, I argue, are natural. I consider the philosophical role played by “natural” in the linearity phenomenon, arguing ultimately that we should abandon empty naturality talk and aim instead to make precise the mathematical and logical features we had found desirable.

Quantifer elimination

A theory admits quantifier-elimination when every assertion is logically equivalent over the theory to a quantifier-free assertion. This is quite a remarkable property when it occurs, because it reveals a severe limitation on the range of concepts that can be expressed in the theory—a quantifier-free assertion, after all, is able to express only combinations of the immediate atomic facts at hand. As a result, we are generally able to prove quantifier-elimination results for a theory only when we already have a profound understanding of it and its models, and the quantifier-elimination result itself usually leads quickly to classification of the definable objects, sets, and relations in the theory and its models. In this way, quantifier-elimination results often showcase our mastery over a particular theory and its models. So let us present a few quantifier-elimination results, exhibiting our expertise over some natural theories.

Endless dense linear orders

$\def\<#1>{\left\langle#1\right\rangle}\newcommand\Q{\mathbb{Q}}\newcommand\R{\mathbb{R}}\newcommand\N{\mathbb{N}}\newcommand\bottom{\mathord{\perp}}\newcommand{\Th}{\mathop{\rm Th}}\newcommand{\unaryminus}{-}\newcommand\Z{\mathbb{Z}}\newcommand\divides{\mid}$Consider first the theory of an endless dense linear order, such as the rational order $\<\Q,<>$. In light of Cantor’s theorems on the universality of the rational line and the categoricity theorem for countable endless dense linear orders, we already have a fairly deep understanding of this theory and this particular model.

Consider any two rational numbers $x,y$ in the structure $\<\Q,<>$. What can one say about them? Well, we can certainly make the atomic assertions that $x$ to a Boolean combination of these assertions.

Theorem. The theory of the rational order $\<\Q,<>$ admits elimination of quantifiers—every assertion $\varphi(x,\ldots)$ is logically equivalent in the rational order to a quantifier-free assertion.

Proof. To see this, observe simply by Cantor’s categoricity theorem for countable dense linear orders that any pair $x<y$ in $\Q$ is automorphic to any other such pair $x'<y’$, and similarly for pairs with $x=y$ or $y<x$. Consequently, $\varphi(x,y)$ either holds of all pairs with $x<y$ or of none of them, of all pairs with $x=y$ or none, and of all pairs with $y<x$ or none. The assertion $\varphi(x,y)$ is therefore equivalent to the disjunction of the three atomic relations for which it is realized, including $\top$ as the disjunction of all three atomic possibilities and $\bottom$ as the empty disjunction.

More generally, a similar observation applies to assertions $\varphi(x_1,\ldots,x_n)$ with more free variables. By Cantor’s theorem, every $n$-tuple of points in $\Q$ is automorphic with any other such $n$-tuple of points having the same atomic order relations. Therefore any assertion holding of one such $n$-tuple holds of all $n$-tuples with that same atomic type, and consequently every assertion $\varphi(x_1,\ldots,x_n)$ is logically equivalent in $\<\Q,<>$ to a disjunction of those combinations of atomic relations amongst the variables $x_1,\ldots,x_n$ for which it holds. In particular, every assertion is equivalent in $\<\Q,<>$ to a quantifier-free assertion. In short, the theory of this model $\Th(\<\Q,<>)$ admits elimination of quantifiers. $\Box$

What about other endless dense linear orders? The argument we have given so far is about the theory of this particular model $\<\Q,<>$. In fact, the theory of the rational order is exactly the theory of endless dense linear orders, because this theory is complete, which one can see as an immediate consequence of the categoricity result of Cantor’s theorem and the downward Löwenheim-Skolem theorem. In my book, I have not yet proved the Löwenheim-Skolem theorem at this stage, however, and so let me give a direct proof of quantifier-elimination in the theory of endless dense linear orders, from which we can also derive the completeness of this theory.

Theorem. In the theory of endless dense linear orders, every statement is logically equivalent to a quantifier-free statement.

Proof. To clarify, the quantifier-free statement will have the same free variables as the original assertion, provided we allow $\bottom$ and $\top$ as logical constants. We argue by induction on formulas. The claim is of course already true for the atomic formulas, and it is clearly preserved under Boolean connectives. So it suffices inductively to eliminate the quantifier from $\exists x\, \varphi(x,\ldots)$, where $\varphi$ is itself quantifier-free. We can place $\varphi$ in disjunctive normal form, a disjunction of conjunction clauses, where each conjunction clause is a conjunction of literals, that is, atomic or negated atomic assertions. Since the atomic assertions $x<y$, $x=y$ and $y<x$ are mutually exclusive and exhaustive, the negation of any one of them is equivalent to the disjunction of the other two. Thus we may eliminate any need for negation. By redistributing conjunction over disjunction as much as possible, we reduce to the case of $\exists x\,\varphi$, where $\varphi$ is in disjunctive normal form without any negation. The existential quantifier distributes over disjunction, and so we reduce to the case $\varphi$ is a conjunction of atomic assertions. We may eliminate any instance of $x=x$ or $y=y$, since these impose no requirement. We may assume that the variable $x$ occurs in each conjunct, since otherwise that conjunct commutes outside the quantifier. If $x=y$ occurs in $\varphi$ for some variable $y$ not identical to $x$, then the existential claim is equivalent to $\varphi(y,\ldots)$, that is, by replacing every instance of $x$ with $y$, and we have thus eliminated the quantifier. If $x<x$ occurs as one of the conjuncts, this is not satisfiable and so the assertion is equivalent to $\bottom$. Thus we have reduced to the case where $\varphi$ is a conjunction of assertions of the form $x<y_i$ and $z_j<x$. If only one type of these occurs, then the assertion $\exists x\,\varphi$ is outright provable in the theory by the endless assumption and thus equivalent to $\top$. Otherwise, both types $x<y_i$ and $z_j<x$ occur, and in this case the existence of an $x$ obeying this conjunction of assertions is equivalent over the theory of endless dense linear orders to the quantifier-free conjunction $\bigwedge_{i,j}z_j<y_i$, since there will be an $x$ between them in this case and only in this case. Thus, we have eliminated the quantifier $\exists x$, and so by induction every formula is equivalent over this theory to a quantifier-free formula. $\Box$

Corollary. The theory of endless dense linear orders is complete.

Proof. If $\sigma$ is any sentence in this theory, then by theorem above, it is logically equivalent to a Boolean combination of quantifier-free assertions with the same variables. Since $\sigma$ is a sentence and there are no quantifier-free atomic sentences except $\bottom$ and $\top$, it follows that $\sigma$ is equivalent over the theory to a Boolean combination of $\bottom$ or $\top$. All such sentences are equivalent either to $\bottom$ or $\top$, and thus either $\sigma$ is entailed by the theory or $\neg\sigma$ is, and so the theory is complete. $\Box$

Corollary. In any endless dense linear order, the definable sets (allowing parameters) are precisely the finite unions of intervals.

Proof. By intervals we mean a generalized concept allowing either open or closed endpoints, as well as rays, in any of the forms:
$$(a,b)\qquad [a,b]\qquad [a,b)\qquad (a,b]\qquad (a,\infty)\qquad [a,\infty)\qquad (\unaryminus\infty,b)\qquad (\unaryminus\infty,b]$$
Of course any such interval is definable, since $(a,b)$ is defined by $(a<x)\wedge(x<b)$, taking the endpoints $a$ and $b$ as parameters, and $(-\infty,b]$ is defined by $(x<b)\vee (x=b)$, and so on. Thus, finite unions of intervals are also definable by taking a disjunction.

Conversely, any putative definition $\varphi(x,y_1,\ldots,y_n)$ is equivalent to a Boolean combination of atomic assertions concerning $x$ and the parameters $y_i$. Thus, whenever it is true for some $x$ between, above, or below the parameters $y_i$, it will be true of all $x$ in that same interval, and so the set that is defined will be a finite union of intervals having the parameters $y_i$ as endpoints, with the intervals being open or closed depending on whether the parameters themselves satisfy the formula or not. $\Box$

Theory of successor

Let us next consider the theory of a successor function, as realized for example in the Dedekind model, $\<\N,S,0>$, where $S$ is the successor
function $Sn=n+1$. The theory has the following three axioms:
$$\forall x\, (Sx\neq 0)$$

$$\forall x,y\, (Sx=Sy\implies x=y)$$

$$\forall x\, \bigl(x\neq 0\implies \exists y\,(Sy=x)\bigr).$$
In the Dedekind model, every individual is definable, since $x=n$ just in case $x=SS\cdots S0$, where we have $n$ iterative applications of $S$. So this is a pointwise definable model, and hence also Leibnizian. Note the interplay between the $n$ of the object theory and $n$ of the metatheory in the claim that every individual is definable.

What definable subsets of the Dedekind model can we think of? Of course, we can define any particular finite set, since the numbers are definable as individuals. For example, we can define the set ${1,5,8}$ by saying, “either $x$ has the defining property of $1$ or it has the defining property of $5$ or it has the defining property of $8$.” Thus any finite set is definable, and by negating such a formula, we see also that any cofinite set—the complement of a finite set—is definable. Are there any other definable sets? For example, can we define the set of even numbers? How could we prove that we cannot? The Dedekind structure has no automorphisms, since all the individuals are definable, and so we cannot expect to use automorphism to show that the even numbers are not definable as a set. We need a deeper understanding of definability and truth in this structure.

Theorem. The theory of a successor function admits elimination of quantifiers—every assertion is equivalent in this theory to a quantifier-free assertion.

Proof. By induction on formulas. The claim is already true for atomic assertions, since they have no quantifiers, and quantifier-free assertions are clearly closed under the Boolean connectives. So it suffices by induction to eliminate the quantifier from assertions of the form $\exists x\, \varphi(x,\ldots)$, where $\varphi$ is quantifier free. We may place $\varphi$ in disjunctive normal form, and since the quantifier distributes over disjunction, we reduce to the case that $\varphi$ is a conjunction of atomic and negated atomic assertions. We may assume that $x$ appears in each atomic conjunct, since otherwise we may bring that conjunct outside the quantifier. We may furthermore assume that $x$ appears on only one side of each atomic clause, since otherwise the statement is either trivially true as with $SSx=SSx$ or $Sx\neq SSx$, or trivially false as with $Sx=SSx$. Consider for example:
$$\exists x\,\bigl[(SSSx=y)\wedge (SSy=SSSz)\wedge (SSSSSx=SSSw)\wedge{}$$
$$\hskip1in{}\wedge (Sx\neq SSSSw)\wedge (SSSSy\neq SSSSSz)\bigr]$$
We can remove duplicated $S$s occurring on both sides of an equation. If $x=S^ky$ appears, we can get rid of $x$ and replace all occurrences with $S^ky$. If $S^nx=y$ appears, can add $S$’s everywhere and then replace any occurrence of $S^nx$ with $y$. If only inequalities appear, then the statement is simply true.

For example, since the third clause in the formula above is equivalent to $SSx=w$, we may use that to omit any need to refer to $x$, and the formula overall is equivalent to
$$(Sw=y)\wedge (y=Sz)\wedge (w\neq SSSSSw)\wedge (y\neq Sz),$$ which has no quantifiers.
Since the method is completely general, we have proved that the theory of successor admits elimination of quantifiers. $\Box$

It follows that the definable sets in the Dedekind model $\<\N,S,0>$, using only the first-order language of this structure, are precisely the finite and cofinite sets.

Corollary. The definable sets in $\<\N,S,0>$ are precisely the finite and cofinite sets

Proof. This is because an atomic formula defines a finite set, and the collection of finite or cofinite sets is closed under negation and Boolean combinations. Since every formula is equivalent to a quantifier-free formula, it follows that every formula is a Boolean combination of atomic formulas, and hence defines a finite or cofinite set. $\Box$

In particular, the concepts of being even or being odd are not definable from the successor operation in $\<\N,S,0>$, since the set of even numbers is neither finite nor cofinite.

Corollary. The theory of a successor function is complete—it is the theory of the standard model $\<\N,S,0>$.

Proof. If $\sigma$ is a sentence in the language of successor, then by the quantifier-elimination theorem it is equivalent to a quantifier-free assertion in the language with the successor function $S$ and constant symbol $0$. But the only quantifier-free sentences in this language are Boolean combinations of equations of the form $S^n0=S^k0$. Since all such equations are settled by the theory, the sentence itself is settled by the theory, and so the theory is complete. $\Box$

We saw that the three axioms displayed on the previous page were true in the Dedekind model $\<\N,S,0>$. Are there any other models of these axioms? Yes, there are. For example, we can add another $\Z$-chain of successors on the side, as with $\N+\Z$ or $\N\sqcup\Z$, although we shall see that the order is not definable. What are the definable elements in the enlarged structure? Still $0$ and all its finite successors are definable as before. But no elements of the $\Z$-chains can be definable, because we may perform an automorphism of the structure that translates elements within the $\Z$-chain by a fixed amount.

Let me prove next that the theory implies the induction axiom schema.

Corollary. The theory of successor (the three axioms) implies the induction axiom schema in the language of successor, that is, the following assertion for any assertion $\varphi(x)$:
$$\left[\varphi(0)\wedge\bigl(\forall x\,\bigl(\varphi(x)\implies\varphi(Sx)\bigr)\right]\implies\forall x\,\varphi(x)$$

Proof. Consider the set defined by $\varphi(x)$. By the earlier corollary, it must be eventually periodic in the standard model $\<\N,S,0>$. But by the induction assumption stated in the theorem, it must hold of every number in the standard model. So the standard model thinks that $\forall x\,\varphi(x)$. But the theory of the standard model is the theory of successor, which is complete. So the theory of successor entails that $\varphi$ is universal, as desired. $\Box$

In other words, in the trivial theory of successor–the three axioms—we get the corresponding induction axiom for free.

Presburger arithmetic

Presburger arithmetic is the theory of addition on the natural numbers, that is, the theory of the structure $\<\N,+,0,1>$. The numbers $0$ and $1$ are actually definable here from addition alone, since $0$ is the unique additive identity, and $1$ is the only number $u$ that is not expressible as a sum $x+y$ with both $x\neq u$ and $y\neq u$. So we may view this model if desired as a definitional expansion of $\<\N,+>$, with addition only. The number $2$ is similarly definable as $1+1$, and indeed any number $n$ is definable as $1+\cdots+1$, with $n$ summands, and so this is a pointwise definable model and hence also Leibnizian.

What are the definable subsets? We can define the even numbers, of course, since $x$ is even if and only if $\exists y\,(y+y=x)$. We can similarly define congruence modulo $2$ by $x\equiv_2 y\iff \exists z\,\bigl[(z+z+x=y)\vee (z+z+y=x)\bigr]$. More generally, we can express the relation of congruence modulo $n$ for any fixed $n$ as follows:
$$x\equiv_n y\quad\text{ if and only if }\exists z\,\bigl[(\overbrace{z+\cdots+z}^n+x=y)\vee(\overbrace{z+\cdots+z}^n+y=x)\bigr].$$
What I claim is that this exhausts what is expressible.

Theorem. Presburger arithmetic in the definitional expansion with all congruence relations, that is, the theory of the structure
$$\<\N,+,0,1,\equiv_2,\equiv_3,\equiv_4,\ldots>$$
admits elimination of quantifiers. In particular, every assertion in the language of $\<\N,+,0,1>$ is equivalent to a quantifer-free assertion in the language with the congruence relations.

Proof. We consider Presburger arithmetic in the language with addition $+$, with all the congruence relations $\equiv_n$ for every $n\geq 2$, and the constants $0$ and $1$. We prove quantifier-elimination in this language by induction on formulas. As before the claim already holds for atomic assertions and is preserved by Boolean connectives. So it suffices to eliminate the quantifier from assertions of the form $\exists x\,\varphi(x,\ldots)$, where $\varphi$ is quantifier-free. By placing $\varphi$ into disjunctive normal form and distributing the quantifier over the disjunction, we may assume that $\varphi$ is a conjunction of atomic and negated atomic assertions. Note that negated congruences are equivalent to a disjunction of positive congruences, such as in the case:
$$x\not\equiv_4 y\quad\text{ if and only if }\quad (x+1\equiv_4y)\vee(x+1+1\equiv_4y)\vee (x+1+1+1\equiv_4 y).$$
We may therefore assume there are no negated congruences in $\varphi$. By canceling like terms on each side of an equation or congruence, we may assume that $x$ occurs on only one side. We may assume that $x$ occurs nontrivially in every conjunct of $\varphi$, since otherwise this conjunct commutes outside the quantifier. Since subtraction modulo $n$ is the same as adding $n-1$ times, we may also assume that all congruences occurring in $\varphi$ have the form $kx\equiv_n t$, where $kx$ denotes the syntactic expression $x+\cdots+x$ occurring in the formula, with $k$ summands, and $t$ is a term not involving the variable $x$. Thus, $\varphi$ is a conjunction of expressions each having the form $kx\equiv_n t$, $ax+r=s$, or $bx+u\neq v$, where $ax$ and $bx$ similarly denote the iterated sums $x+\cdots+x$ and $r,s,u,v$ are terms not involving $x$.

If indeed there is a conjunct of the equality form $ax+r=s$ occurring in $\varphi$, then we may omit the quantifier as follows. Namely, in order to fulfill the existence assertion, we know that $x$ will have to solve $ax+r=s$, and so in particular $r\equiv_a s$, which ensures the existence of such an $x$, but also in this case any inequality $bx+u\neq v$ can be equivalently expressed as $abx+au\neq av$, which since $ax+r=s$ is equivalent to $bs+au\neq av+br$, and this does does not involve $x$; similarly, any congruence $kx\equiv_n t$ is equivalent to $akx\equiv_{an}at$, which is equivalent to $s\equiv_{an} r+at$, which again does not involve $x$. Thus, when there is an equality involving $x$ present in $\varphi$, then we can use that fact to express the whole formula in an equivalent manner not involving $x$.

So we have reduced to the case $\exists x\,\varphi$, where $\varphi$ is a conjunction of inequalities $bs+u\neq v$ and congruences $kx\equiv_n t$. We can now ignore the inequalities, since if the congruence system has a solution, then it will have infinitely many solutions, and so there will be an $x$ solving any finitely given inequalities. So we may assume that $\varphi$ is simply a list of congruences of the form $kx\equiv_n t$, and the assertion is that this system of congruences has a solution. But there are only finitely many congruences mentioned, and so by working modulo the least common multiple of the bases that occur, there are only finitely many possible values for $x$ to be checked. And so we can simply replace $\varphi$ with a disjunction over these finitely many values $i$, replacing $x$ in each conjunction with $1+\cdots+1$, using $i$ copies of $1$, for each $i$ up to the least common multiples of the bases that arise in the congruences appearing in $\varphi$. If there is an $x$ solving the system, then one of these values of $i$ will work, and conversely.

So we have ultimately succeeded in expressing $\exists x\,\varphi$ in a quantifier-free manner, and so by induction every assertion in Presburger arithmetic is equivalent to a quantifier-free assertion in the language allowing addition, congruences, and the constants $0$ and $1$. $\Box$

Corollary. The definable sets in $\<\N,+,0,1>$ are exactly the eventually periodic sets.

Proof. Every periodic set is definable, since one can specify the set up to the period $p$, and then express the invariance modulo $p$. Any finite deviation from a definable set also is definable, since every individual number is definable. So every eventually period set is definable. Conversely, every definable set is defined by a quantifier-free assertion in the language of $\<\N,+,0,1,\equiv_2,\equiv_3,\equiv_4,\ldots>$. We may place the definition in disjunctive normal form, and again replace negated congruences with a disjunction of positive congruences. For large enough values of $x$, the equalities and inequalities appearing in the definition become irrelevant, and so the definition eventually agrees with a finite union of solutions of congruence systems. Every such system is periodic with a period at most the least common multiple of the bases of the congruences appearing in it. And so every definable set is eventually periodic, as desired. $\Box$

Corollary. Multiplication is not definable in $\<\N,+,0,1>$. Indeed, the squaring operation is not definable, and neither is the divisibility relation $p\divides q$.

Proof. If we could define multiplication, or even the squaring operation, then we would be able to define the set of perfect squares, but this is not eventually periodic. Similarly, if we could define the divides relation $p\divides q$, then we could define the set of prime numbers, which is not eventually periodic. $\Box$

Real-closed field

Let us lastly consider the ordered real field $\<\R,+,\cdot,0,1,<>$. I want to mention (without proof) that a deep theorem of Tarski shows that this structure admits elimination of quantifiers: every assertion is equivalent in this structure to a quantifier-free assertion. In fact all that is need is that this is a real-closed field, an ordered field in which every odd-degree polynomial has a root and every positive number has a square root.

We can begin to gain insight to this fact by reaching into the depths of our high-school education. Presented with an equation $ax^2+bx+c=0$ in the integers, we know by the quadratic formula that the solution is $x=\left(-b\pm\sqrt{b^2-4ac}\right)/2a$, and in particular, there is a solution in the real numbers if and only if $b^2-4ac\geq 0$, since otherwise a negative discriminant means the solution is a complex number. In other words,
$$\exists x\,(ax^2+bx+c=0)\quad\text{ if and only if }\quad b^2-4ac\geq 0.$$
The key point is that this an elimination of quantifiers result, since we have eliminated the quantifier $\exists x$.

Tarski’s theorem proves more generally that every assertion in the language of ordered fields is equivalent in real-closed fields to a quantifier-free assertion. Furthermore, there is a computable procedure to find the quantifier-free equivalent, as well as a computable procedure to determine the truth of any quantifier-free assertion in the theory of real-closed fields.

What I find incredible is that it follows from this that there is a computable procedure to determine the truth of any first-order assertion of Cartesian plane geometry, since all such assertions are expressible in the language of $\<\R,+,\cdot,0,1,<>$. Amazing! I view this as an incredible culmination of two thousand years of mathematical investigation: we now have an algorithm to determine by rote procedure the truth of any statement in Cartesian geometry. Meanwhile, a counterpoint is that the decision procedure, unfortunately, is not computationally feasible, however, since it takes more than exponential time, and it is a topic of research to investigate the computational running time of the best algorithms.