Topological models of arithmetic

Posted on August 5, 2018 by Joel David Hamkins

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

Abstract. Ali Enayat had asked whether there is a nonstandard model of Peano arithmetic (PA) that can be represented as $⟨ ℚ, \oplus, \otimes ⟩$ , where $\oplus$ and $\otimes$ are continuous functions on the rationals $ℚ$ . 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 $ℝ$ , the reals in any finite dimension $ℝ 𝑛$ , 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.

The first author had inquired whether a nonstandard model of arithmetic could be continuously presented on the rational numbers.

Main Question. (Enayat, 2009) Are there continuous functions $\oplus$ and $\otimes$ on the rational numbers $ℚ$ , such that $⟨ ℚ, \oplus, \otimes ⟩$ is a nonstandard model of arithmetic?

By a model of arithmetic, what we mean here is a model of the first-order Peano axioms PA, although we also consider various weakenings of this theory. The theory PA asserts of a structure $⟨ 𝑀, +, \cdot ⟩$ that it is the non-negative part of a discretely ordered ring, plus the induction principle for assertions in the language of arithmetic. The natural numbers $⟨ ℕ, +, \cdot ⟩$ , for example, form what is known as the standard model of PA, but there are also many nonstandard models, including continuum many non-isomorphic countable models.

We answer the question affirmatively, and indeed, the main theorem shows that every countable model of PA is continuously presented on $ℚ$ . We define generally that a topological model of arithmetic is a topological space $𝑋$ equipped with continuous functions $\oplus$ and $\otimes$ , for which $⟨ 𝑋, \oplus, \otimes ⟩$ satisfies the desired arithmetic theory. In such a case, we shall say that the underlying space $𝑋$ continuously supports a model of arithmetic and that the model is continuously presented upon the space $𝑋$ .

Question. Which topological spaces support a topological model of arithmetic?

In the paper, we prove that the reals $ℝ$ , the reals in any finite dimension $ℝ 𝑛$ , the long line and Cantor space do not support a topological model of arithmetic, and neither does any Suslin line. Meanwhile, there are many other spaces that do support topological models, including many uncountable subspaces of the plane $ℝ 2$ . It remains an open question whether any uncountable Polish space, including the Baire space, can support a topological model of arithmetic.

Let me state the main theorem and briefly sketch the proof.

Main Theorem. Every countable model of PA has a continuous presentation on the rationals $ℚ$ .

Proof. We shall prove the theorem first for the standard model of arithmetic $⟨ ℕ, +, \cdot ⟩$ . Every school child knows that when computing integer sums and products by the usual algorithms, the final digits of the result $𝑥 + 𝑦$ or $𝑥 \cdot 𝑦$ are completely determined by the corresponding final digits of the inputs $𝑥$ and $𝑦$ . Presented with only final segments of the input, the child can nevertheless proceed to compute the corresponding final segments of the output.

$\dots 1261 \dots 1261 + \dots 153 ――――――― \times \dots 153 ――――――― \dots 414 \dots 3783 \dots 63053 \dots 126153 \dots \dots 253 ――――――― \dots 933$

This phenomenon amounts exactly to the continuity of addition and multiplication with respect to what we call the final-digits topology on $ℕ$ , which is the topology having basic open sets $𝑈 𝑠$ , the set of numbers whose binary representations ends with the digits $𝑠$ , for any finite binary string $𝑠$ . (One can do a similar thing with any base.) In the $𝑈 𝑠$ notation, we include the number that would arise by deleting initial $0$ s from $𝑠$ ; for example, $6 \in 𝑈 00110$ . Addition and multiplication are continuous in this topology, because if $𝑥 + 𝑦$ or $𝑥 \cdot 𝑦$ has final digits $𝑠$ , then by the school-child’s observation, this is ensured by corresponding final digits in $𝑥$ and $𝑦$ , and so $(𝑥, 𝑦)$ has an open neighborhood in the final-digits product space, whose image under the sum or product, respectively, is contained in $𝑈 𝑠$ .

Let us make several elementary observations about the topology. The sets $𝑈 𝑠$ do indeed form the basis of a topology, because $𝑈 𝑠 \cap 𝑈 𝑡$ is empty, if $𝑠$ and $𝑡$ disagree on some digit (comparing from the right), or else it is either $𝑈 𝑠$ or $𝑈 𝑡$ , depending on which sequence is longer. The topology is Hausdorff, because different numbers are distinguished by sufficiently long segments of final digits. There are no isolated points, because every basic open set $𝑈 𝑠$ has infinitely many elements. Every basic open set $𝑈 𝑠$ is clopen, since the complement of $𝑈 𝑠$ is the union of $𝑈 𝑡$ , where $𝑡$ conflicts on some digit with $𝑠$ . The topology is actually the same as the metric topology generated by the $2$ -adic valuation, which assigns the distance between two numbers as $2 - 𝑘$ , when $𝑘$ is largest such that $2 𝑘$ divides their difference; the set $𝑈 𝑠$ is an open ball in this metric, centered at the number represented by $𝑠$ . (One can also see that it is metric by the Urysohn metrization theorem, since it is a Hausdorff space with a countable clopen basis, and therefore regular.) By a theorem of Sierpinski, every countable metric space without isolated points is homeomorphic to the rational line $ℚ$ , and so we conclude that the final-digits topology on $ℕ$ is homeomorphic to $ℚ$ . We’ve therefore proved that the standard model of arithmetic $ℕ$ has a continuous presentation on $ℚ$ , as desired.

But let us belabor the argument somewhat, since we find it interesting to notice that the final-digits topology (or equivalently, the $2$ -adic metric topology on $ℕ$ ) is precisely the order topology of a certain definable order on $ℕ$ , what we call the final-digits order, an endless dense linear order, which is therefore order-isomorphic and thus also homeomorphic to the rational line $ℚ$ , as desired.

The final-digits order $◃$ on the natural numbers is determined by the left-to-right order of nodes and branches in a certain presentation of the binary tree, pictured in figure 1. Each node in the tree represents a natural number via the binary sequence of digits proceeding from that node down to the root, and the final-digits order is determined from the induced left-to-right order of these nodes. As one climbs the tree, successive bits are added as leading digits of the binary representations. Since leading digits of $0$ do not affect the number represented, these nodes move neither left nor right, but proceed straight up in the tree. Leading digits of $1$ , however, branch to the right at even stages in this tree and to the left at odd stages. One easily determines any instance of the final-digits order relation for natural numbers $𝑛 ◃ 𝑚$ by inspecting the right-most digit of disagreement in the binary representations of $𝑛$ and $𝑚$ (appending leading $0$ s if necessary), and considering whether this digit’s place is even or odd.

The basic open set $𝑈 𝑠$ of numbers having final digits $𝑠$ is an open set in this order, since any number ending with $𝑠$ is above a number with binary form $100 \dots 0 𝑠$ and below a number with binary form $11 \dots 1 𝑠$ in the final-digits order; so $𝑈 𝑠$ is a union of intervals in the final-digits order. Conversely, every interval in the final-digits order is open in the final-digits topology, because if $𝑛 ◃ 𝑥 ◃ 𝑚$ , then this is determined by some final segment of the digits of $𝑥$ (appending initial $0$ s if necessary), and so there is some $𝑈 𝑠$ containing $𝑥$ and contained in the interval between $𝑛$ and $𝑚$ . Thus, the final-digits topology is the precisely same as the order topology of the final-digits order, which is a definable endless dense linear order on $ℕ$ . Since this order is isomorphic and hence homeomorphic to the rational line $ℚ$ , we conclude again that $⟨ ℕ, +, \cdot ⟩$ admits a continuous presentation on $ℚ$ .

We now complete the proof by considering an arbitrary countable model $𝑀$ of PA. Let $◃ 𝑀$ be the final-digits order as defined inside $𝑀$ . Since the reasoning of the above paragraphs can be undertaken in PA, it follows that $𝑀$ can see that its addition and multiplication are continuous with respect to the order topology of its final-digits order. Since $𝑀$ is countable, the final-digits order of $𝑀$ makes it a countable endless dense linear order, which by Cantor’s theorem is therefore order-isomorphic and hence homeomorphic to $ℚ$ . Thus, $𝑀$ has a continuous presentation on the rational line $ℚ$ , as desired. $◻$

The executive summary of the proof is: the arithmetic of the standard model $ℕ$ is continuous with respect to the final-digits topology, which is the same as the $2$ -adic metric topology on $ℕ$ , and this is homeomorphic to the rational line, because it is the order topology of the final-digits order, a definable endless dense linear order; applied in a nonstandard model $𝑀$ , this observation means the arithmetic of $𝑀$ is continuous with respect to its rational line $ℚ 𝑀$ , which for countable models is isomorphic to the actual rational line $ℚ$ , and so such an $𝑀$ is continuously presentable upon $ℚ$ .

Let me mention the following order, which it seems many people expect to use instead of the final-digits order as we defined it above. With this order, one in effect takes missing initial digits of a number as $0$ , which is of course quite reasonable.

The problem with this order, however, is that the order topology is not actually the final-digits topology. For example, the set of all numbers having final digits $110$ in this order has a least element, the number $6$ , and so it is not open in the order topology. Worse, I claim that arithmetic is not continuous with respect to this order. For example, $1 + 1 = 2$ , and $2$ has an open neighborhood consisting entirely of even numbers, but every open neighborhood of $1$ has both odd and even numbers, whose sums therefore will not all be in the selected neighborhood of $2$ . Even the successor function $𝑥 \mapsto 𝑥 + 1$ is not continuous with respect to this order.

Finally, let me mention that a version of the main theorem also applies to the integers $ℤ$ , using the following order.

Go to the article to read more.

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

A question in set-theoretic geology: if $𝑀 [𝐺] [𝐾] = 𝑀 [𝐻] [𝐾],$ then can we conlude $𝑀 [𝐺] = 𝑀 [𝐻]$ ?

Posted on July 30, 2018 by Joel David Hamkins

I was recently asked this interesting question on set-theoretic geology by Iian Smythe, a set-theory post-doc at Rutgers University; the problem arose in the context of one of this current research projects.

Question. Assume that two product forcing extensions are the same $𝑀 [𝐺] [𝐾] = 𝑀 [𝐻] [𝐾],$ where $𝑀 [𝐺]$ and $𝑀 [𝐻]$ are forcing extensions of $𝑀$ by the same forcing notion $ℙ$ , and $𝐾 \subset ℚ \in 𝑀$ is both $𝑀 [𝐺]$ and $𝑀 [𝐻]$ -generic with respect to this further forcing $ℚ$ . Can we conclude that $𝑀 [𝐺] = 𝑀 [𝐻] ?$ Can we make this conclusion at least in the special case that $ℙ$ is adding a Cohen real and $ℚ$ is collapsing the continuum?

It seems natural to hope for a positive answer, because we are aware of many such situations that arise with forcing, where indeed $𝑀 [𝐺] = 𝑀 [𝐻]$ . Nevertheless, the answer is negative. Indeed, we cannot legitimately make this conclusion even when both steps of forcing are adding merely a Cohen real. And such a counterexample implies that there is a counterexample of the type mentioned in the question, simply by performing further collapse forcing.

Theorem. For any countable model $𝑀$ of set theory, there are $𝑀$ -generic Cohen reals $𝑐$ , $𝑑$ and $𝑒$ , such that

The Cohen reals $𝑐$ and $𝑒$ are mutually generic over $𝑀$ .
The Cohen reals $𝑑$ and $𝑒$ are mutually generic over $𝑀$ .
These two pairs produce the same forcing extension $𝑀 [𝑐] [𝑒] = 𝑀 [𝑑] [𝑒]$ .
But the intermediate models are different $𝑀 [𝑐] \neq 𝑀 [𝑑]$ .

Proof. Fix $𝑀$ , and let $𝑐$ and $𝑒$ be any two mutually generic Cohen reals over $𝑀$ . Let us view them as infinite binary sequences, that is, as elements of Cantor space. In the extension $𝑀 [𝑐] [𝑒]$ , let $𝑑 = 𝑐 + 𝑒 m o d 2$ , in each coordinate. That is, we get $𝑑$ from $𝑐$ by flipping bits, but only on coordinates that are $1$ in $𝑒$ . This is the same as applying a bit-flipping automorphism of the forcing, which is available in $𝑀 [𝑒]$ , but not in $𝑀$ . Since $𝑐$ is $𝑀 [𝑒]$ -generic by reversing the order of forcing, it follows that $𝑑$ also is $𝑀 [𝑒]$ -generic, since the automorphism is in $𝑀 [𝑒]$ . Thus, $𝑑$ and $𝑒$ are mutually generic over $𝑀$ . Further, $𝑀 [𝑐] [𝑒] = 𝑀 [𝑑] [𝑒]$ , because $𝑀 [𝑒] [𝑐] = 𝑀 [𝑒] [𝑑]$ , as $𝑐$ and $𝑑$ were isomorphic generic filters by an isomorphism in $𝑀 [𝑒]$ . But finally, $𝑀 [𝑐]$ and $𝑀 [𝑑]$ are not the same, because from $𝑐$ and $𝑑$ together we can construct $𝑒$ , because we can tell exactly which bits were flipped. $◻$

If one now follows the $𝑒$ forcing with collapse forcing, one achieves a counterexample model of the type mentioned in the question, namely, with $𝑀 [𝑐] [𝑒 * 𝐾] = 𝑀 [𝑑] [𝑒 * 𝐾]$ , but $𝑀 [𝑐] \neq 𝑀 [𝑑]$ .

I have a feeling that my co-authors on a current paper in progress, Set-theoretic blockchains, on the topic of non-amalgamation in the generic multiverse, will tell me that the argument above is an instance of some of the theorems we prove in the latter part of that paper. (Miha, please tell me in the comments, if you see this, or tell me where I have seen this argument before; I think I made this argument or perhaps seen it before.) The paper is [bibtex key=”HabicHamkinsKlausnerVernerWilliams2018:Set-theoretic-blockchains”].

A new proof of the Barwise extension theorem, without infinitary logic

Posted on July 27, 2018 by Joel David Hamkins

I have found a new proof of the Barwise extension theorem, that wonderful yet quirky result of classical admissible set theory, which says that every countable model of set theory can be extended to a model of $Z F C + 𝑉 = 𝐿$ .

Barwise Extension Theorem. (Barwise 1971) Every countable model of set theory $𝑀 ⊧ Z F$ has an end-extension to a model of $Z F C + 𝑉 = 𝐿$ .

The Barwise extension theorem is both (i) a technical culmination of the pioneering methods of Barwise in admissible set theory and infinitary logic, including the Barwise compactness and completeness theorems and the admissible cover, but also (ii) one of those rare mathematical theorems that is saturated with significance for the philosophy of mathematics and particularly the philosophy of set theory. I discussed the theorem and its philosophical significance at length in my paper, The multiverse perspective on the axiom of constructibility, where I argued that it can change how we look upon the axiom of constructibility and whether this axiom should be considered ‘restrictive,’ as it often is in set theory. Ultimately, the Barwise extension theorem shows how wrong a model of set theory can be, if we should entertain the idea that the set-theoretic universe continues growing beyond it.

Regarding my new proof, below, however, what I find especially interesting about it, if not surprising in light of (i) above, is that it makes no use of Barwise compactness or completeness and indeed, no use of infinitary logic at all! Instead, the new proof uses only classical methods of descriptive set theory concerning the representation of $Π 11$ sets with well-founded trees, the Levy and Shoenfield absoluteness theorems, the reflection theorem and the Keisler-Morley theorem on elementary extensions via definable ultrapowers. Like the Barwise proof, my proof splits into cases depending on whether the model $𝑀$ is standard or nonstandard, but another interesting thing about it is that with my proof, it is the $𝜔$ -nonstandard case that is easier, whereas with the Barwise proof, the transitive case was easiest, since one only needed to resort to the admissible cover when $𝑀$ was ill-founded. Barwise splits into cases on well-founded/ill-founded, whereas in my argument, the cases are $𝜔$ -standard/ $𝜔$ -nonstandard.

To clarify the terms, an end-extension of a model of set theory $⟨ 𝑀, \in 𝑀 ⟩$ is another model $⟨ 𝑁, \in 𝑁 ⟩$ , such that the first is a substructure of the second, so that $𝑀 \subseteq 𝑁$ and $\in 𝑀 = \in 𝑁 ↾ 𝑀$ , but further, the new model does not add new elements to sets in $𝑀$ . In other words, $𝑀$ is an $\in$ -initial segment of $𝑁$ , or more precisely: if $𝑎 \in 𝑁 𝑏 \in 𝑀$ , then $𝑎 \in 𝑀$ and hence $𝑎 \in 𝑀 𝑏$ .

Set theory, of course, overflows with instances of end-extensions. For example, the rank-initial segments $𝑉 𝛼$ end-extend to their higher instances $𝑉 𝛽$ , when $𝛼 < 𝛽$ ; similarly, the hierarchy of the constructible universe $𝐿 𝛼 \subseteq 𝐿 𝛽$ are end-extensions; indeed any transitive set end-extends to all its supersets. The set-theoretic universe $𝑉$ is an end-extension of the constructible universe $𝐿$ and every forcing extension $𝑀 [𝐺]$ is an end-extension of its ground model $𝑀$ , even when nonstandard. (In particular, one should not confuse end-extensions with rank-extensions, also known as top-extensions, where one insists that all the new sets have higher rank than any ordinal in the smaller model.)

Let’s get into the proof.

Proof. Suppose that $𝑀$ is a model of $Z F$ set theory. Consider first the case that $𝑀$ is $𝜔$ -nonstandard. For any particular standard natural number $𝑘$ , the reflection theorem ensures that there are arbitrarily high $𝐿 𝑀 𝛼$ satisfying $Z F C 𝑘 + 𝑉 = 𝐿$ , where $Z F C 𝑘$ refers to the first $𝑘$ axioms of $Z F C$ in a fixed computable enumeration by length. In particular, every countable transitive set $𝑚 \in 𝐿 𝑀$ has an end-extension to a model of $Z F C 𝑘 + 𝑉 = 𝐿$ . By overspill (that is, since the standard cut is not definable), there must be some nonstandard $𝑘$ for which $𝐿 𝑀$ thinks that every countable transitive set $𝑚$ has an end-extension to a model of $Z F C 𝑘 + 𝑉 = 𝐿$ , which we may assume is countable. This is a $Π 12$ statement about $𝑘$ , which will therefore also be true in $𝑀$ , by the Shoenfield absolutenss theorem. It will also be true in all the elementary extensions of $𝑀$ , as well as in their forcing extensions. And indeed, by the Keisler-Morley theorem, the model $𝑀$ has an elementary top extension $𝑀 +$ . Let $𝜃$ be a new ordinal on top of $𝑀$ , and let $𝑚 = 𝑉 𝑀 + 𝜃$ be the $𝜃$ -rank-initial segment of $𝑀 +$ , which is a top-extension of $𝑀$ . Let $𝑀 + [𝐺]$ be a forcing extension in which $𝑚$ has become countable. Since the $Π 12$ statement is true in $𝑀 + [𝐺]$ , there is an end-extension of $⟨ 𝑚, \in 𝑀 + ⟩$ to a model $⟨ 𝑁, \in 𝑁 ⟩$ that $𝑀 + [𝐺]$ thinks satisfies $Z F C 𝑘 + 𝑉 = 𝐿$ . Since $𝑘$ is nonstandard, this theory includes all the $Z F C$ axioms, and since $𝑚$ end-extends $𝑀$ , we have found an end-extension of $𝑀$ to a model of $Z F C + 𝑉 = 𝐿$ , as desired.

It remains to consider the case where $𝑀$ is $𝜔$ -standard. By the Keisler-Morley theorem, let $𝑀 +$ be an elementary top-extension of $𝑀$ . Let $𝜃$ be an ordinal of $𝑀 +$ above $𝑀$ , and consider the corresponding rank-initial segment $𝑚 = 𝑉 𝑀 + 𝜃$ , which is a transitive set in $𝑀 +$ that covers $𝑀$ . If $⟨ 𝑚, \in 𝑀 + ⟩$ has an end-extension to a model of $Z F C + 𝑉 = 𝐿$ , then we’re done, since such a model would also end-extend $𝑀$ . So assume toward contradiction that there is no such end-extension of $𝑚$ . Let $𝑀 + [𝐺]$ be a forcing extension in which $𝑚$ has become countable. The assertion that $𝑚$ has no end-extension to a model of $Z F C + 𝑉 = 𝐿$ is actually true and hence true in $𝑀 + [𝐺]$ . This is a $Π 11$ assertion there about the real coding $𝑚$ . Every such assertion has a canonically associated tree, which is well-founded exactly when the statement is true. Since the statement is true in $𝑀 + [𝐺]$ , this tree has some countable rank $𝜆$ there. Since these models have the standard $𝜔$ , the tree associated with the statement is the same for us as inside the model, and since the statement is actually true, the tree is actually well founded. So the rank $𝜆$ must come from the well-founded part of the model.

If $𝜆$ happens to be countable in $𝐿 𝑀 +$ , then consider the assertion, “there is a countable transitive set, such that the assertion that it has no end-extension to a model of $Z F C + 𝑉 = 𝐿$ has rank $𝜆$ .” This is a $Σ 1$ assertion, since it is witnessed by the countable transitive set and the ranking function of the tree associated with the non-extension assertion. Since the parameters are countable, it follows by Levy reflection that the statement is true in $𝐿 𝑀 +$ . So $𝐿 𝑀 +$ has a countable transitive set, such that the assertion that it has no end-extension to a model of $Z F C + 𝑉 = 𝐿$ has rank $𝜆$ . But since $𝜆$ is actually well-founded, the statement would have to be actually true; but it isn’t, since $𝐿 𝑀 +$ itself is such an extension, a contradiction.

So we may assume $𝜆$ is uncountable in $𝑀 +$ . In this case, since $𝜆$ was actually well-ordered, it follows that $𝐿 𝑀$ is well-founded beyond its $𝜔 1$ . Consider the statement “there is a countable transitive set having no end-extension to a model of $Z F C + 𝑉 = 𝐿$ .” This is a $Σ 12$ sentence, which is true in $𝑀 + [𝐺]$ by our assumption about $𝑚$ , and so by Shoenfield absoluteness, it is true in $𝐿 𝑀 +$ and hence also $𝐿 𝑀$ . So $𝐿 𝑀$ thinks there is a countable transitive set $𝑏$ having no end-extension to a model of $Z F C + 𝑉 = 𝐿$ . This is a $Π 11$ assertion about $𝑏$ , whose truth is witnessed in $𝐿 𝑀$ by a ranking of the associated tree. Since this rank would be countable in $𝐿 𝑀$ and this model is well-founded up to its $𝜔 1$ , the tree must be actually well-founded. But this is impossible, since it is not actually true that $𝑏$ has no such end-extension, since $𝐿 𝑀$ itself is such an end-extension of $𝑏$ . Contradiction. $◻$

One can prove a somewhat stronger version of the theorem, as follows.

Theorem. For any countable model $𝑀$ of $Z F$ , with an inner model $𝑊 ⊧ Z F C$ , and any statement $𝜙$ true in $𝑊$ , there is an end-extension of $𝑀$ to a model of $Z F C + 𝜙$ . Furthermore, one can arrange that every set of $𝑀$ is countable in the extension model.

In particular, one can find end-extensions of $Z F C + 𝑉 = 𝐿 + 𝜙$ , for any statement $𝜙$ true in $𝐿 𝑀$ .

Proof. Carry out the same proof as above, except in all the statements, ask for end-extensions of $Z F C + 𝜙$ , instead of end-extensions of $Z F C + 𝑉 = 𝐿$ , and also ask that the set in question become countable in that extension. The final contradictions are obtained by the fact that the countable transitive sets in $𝐿 𝑀$ do have end-extensions like that, in which they are countable, since $𝑊$ is such an end-extension. $◻$

For example, we can make the following further examples.

Corollaries.

Every countable model $𝑀$ of $Z F C$ with a measurable cardinal has an end-extension to a model $𝑁$ of $Z F C + 𝑉 = 𝐿 [𝜇]$ .
Every countable model $𝑀$ of $Z F C$ with extender-based large cardinals has an end-extension to a model $𝑁$ satisfying $Z F C + 𝑉 = 𝐿 [⃗ 𝐸]$ .
Every countable model $𝑀$ of $Z F C$ with infinitely many Woodin cardinals has an end-extension to a model $𝑁$ of $Z F + A D + 𝑉 = 𝐿 (ℝ)$ .

And in each case, we can furthermore arrange that every set of $𝑀$ is countable in the extension model $𝑁$ .

This proof grew out of a project on the $Σ 1$ -definable universal finite set, which I am currently undertaking with Kameryn Williams and Philip Welch.

Jon Barwise. Infinitary methods in the model theory of set theory. In Logic
Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969), pages
53–66. North-Holland, Amsterdam, 1971.

Plenary talk, 16th International Congress of Logic, Methodology and Philosophy of Science and Technology, CLMPST 2019, Prague

Posted on July 23, 2018 by Joel David Hamkins

I shall be giving a keynote plenary talk for the 16th International Congress of Logic, Methodology and Philosophy of Science and Technology (CLMPST 2019), to be held 5-10 August 2019 at the Institute of Philosophy of the Czech Academy of Sciences in the beautiful city of Prague . The CLMPST congress is held every four years, and the theme of the 2019 meeting is, “Bridging across academic cultures.”

Can set-theoretic mereology serve as a foundation of mathematics?

Abstract: Mereology, the study of the relation of part to whole, is often contrasted with set theory and its membership relation, the relation of element to set. Whereas set theory has found comparative success in the foundation of mathematics, since the time of Cantor, Zermelo and Hilbert, mereology is strangely absent. Can a set-theoretic mereology, based upon the set-theoretic inclusion relation ⊆ rather than the element-of relation ∈, serve as a foundation of mathematics? Can we faithfully interpret arbitrary mathematical structure in terms of the subset relation to the same extent that set theorists have done so in terms of the membership relation? At bottom, the question is: can we get by with merely ⊆ in place of ∈? Ultimately, I shall identify grounds supporting generally negative answers to these questions, concluding that set-theoretic mereology by itself cannot serve adequately as a foundational theory.

Please join me in Prague! See the Call for Papers, requesting contributed papers and contributed symposia on twenty different thematic sections, from mathematical and philosophical logic to the philosophy of science, philosophy of computing and many other areas. I am given to understand that this will be a large meeting, with about 800 participants expected.

Slides Download

J. D. Hamkins and M. Kikuchi, “Set-theoretic mereology,” Logic and Logical Philosophy, special issue “Mereology and beyond, part II”, vol. 25, iss. 3, pp. 285-308, 2016.
J. D. Hamkins and M. Kikuchi, “The inclusion relations of the countable models of set theory are all isomorphic,” ArXiv e-prints, 2017.

Open class determinacy is preserved by forcing

Posted on July 1, 2018 by Joel David Hamkins

[bibtex key=”HamkinsWoodin2018:Open-class-determinacy-is-preserved-by-forcing”]

Abstract. The principle of open class determinacy is preserved by pre-tame class forcing, and after such forcing, every new class well-order is isomorphic to a ground-model class well-order. Similarly, the principle of elementary transfinite recursion ETR $Γ$ for a fixed class well-order $Γ$ is preserved by pre-tame class forcing. The full principle ETR itself is preserved by countably strategically closed pre-tame class forcing, and after such forcing, every new class well-order is isomorphic to a ground-model class well-order. Meanwhile, it remains open whether ETR is preserved by all forcing, including the forcing merely to add a Cohen real.

The principle of elementary transfinite recursion ETR — according to which every first-order class recursion along any well-founded class relation has a solution — has emerged as a central organizing concept in the hierarchy of second-order set theories from Gödel-Bernays set theory GBC up to Kelley-Morse set theory KM and beyond. Many of the principles in the hierarchy can be seen as asserting that certain class recursions have solutions.

In addition, many of these principles, including ETR and its variants, are equivalently characterized as determinacy principles for certain kinds of class games. Thus, the hierarchy is also fruitfully unified and organized by determinacy ideas.

This hierarchy of theories is the main focus of study in the reverse mathematics of second-order set theory, an emerging subject aiming to discover the precise axiomatic principles required for various arguments and results in second-order set theory. The principle ETR itself, for example, is equivalent over GBC to the principle of clopen determinacy for class games and also to the existence of iterated elementary truth predicates (see Open determinacy for class games); since every clopen game is also an open game, the principle ETR is naturally strengthened by the principle of open determinacy for class games, and this is a strictly stronger principle (see Hachtman and Sato); the weaker principle ETR $O r d$ , meanwhile, asserting solutions to class recursions of length Ord, is equivalent to the class forcing theorem, which asserts that every class forcing notion admits a forcing relation, to the existence of set-complete Boolean completions of any class partial order, to the existence of Ord-iterated elementary truth predicates, to the determinacy of clopen games of rank at most Ord+1, and to other natural set-theoretic principles (see The exact strength of the class forcing theorem).

Since one naturally seeks in any subject to understand how one’s fundamental principles and tools interact, we should like in this article to consider how these second-order set-theoretic principles are affected by forcing. These questions originated in previous work of Victoria Gitman and myself, and question 1 also appears in the dissertation of Kameryn Williams, which was focused on the structure of models of second-order set theories.

It is well-known, of course, that ZFC, GBC, and KM are preserved by set forcing and by tame class forcing, and this is true for other theories in the hierarchy, such as GBC $+ Π 1 𝑛$ -comprehension and higher levels of the second-order comprehension axiom. The corresponding forcing preservation theorem for ETR and for open class determinacy, however, has not been known.

Question 1. Is ETR preserved by forcing?

Question 2. Is open class determinacy preserved by forcing?

We intend to ask in each case about class forcing as well as set forcing. Question 1 is closely connected with the question of whether forcing can create new class well-order order types, longer than any class well-order in the ground model. Specifically, Victoria Gitman and I had observed earlier that ETR $Γ$ for a specific class well-order $Γ$ is preserved by pre-tame class forcing, and this would imply that the full principle ETR would also be preserved, if no fundamentally new class well-orders are created by the forcing. In light of the fact that forcing over models of ZFC adds no new ordinals, that would seem reasonable, but proof is elusive, and the question remains open. Can forcing add new class well-orders, perhaps very tall ones that are not isomorphic to any ground model class well-order? Perhaps there are some very strange models of GBC that gain new class well-order order types in a forcing extension.

Question 3. Assume GBC. After forcing, must every new class well-order be isomorphic to a ground-model class well-order? Does ETR imply this?

The main theorem of this article provides a full affirmative answer to question 2, and partial affirmative answers to questions 2 and 3.

Main Theorem.

Open class determinacy is preserved by pre-tame class forcing. After such forcing, every new class well-order is isomorphic to a ground-model class well-order.
The principle ETR $Γ$ , for any fixed class well order $Γ$ , is preserved by pre-tame class forcing.
The full principle ETR is preserved by countably strategically closed pre-tame class forcing. After such forcing, every new class well-order is isomorphic to a ground-model class well-order.

We should like specifically to highlight the fact that questions 1 and 3 remain open even in the case of the forcing to add a Cohen real. Is ETR preserved by the forcing to add a Cohen real? After adding a Cohen real, is every new class well-order isomorphic to a ground-model class well-order? One naturally expects affirmative answers, especially in a model of ETR.

For more, click through the arxiv for a pdf of the full article.

[bibtex key=”HamkinsWoodin2018:Open-class-determinacy-is-preserved-by-forcing”]

Paul K. Gorbow, PhD 2018, University of Gothenburg

Posted on June 16, 2018 by Joel David Hamkins

Paul K. Gorbow successfully defended his dissertation, “Self-similarity in the foundations” on June 14, 2018 at the University of Gothenburg in the Department of Philosophy, Linguistics and Theory of Science, under the supervision of Ali Enayat, with Peter LeFanu Lumsdaine and Zachiri McKenzie serving as secondary supervisors. The defense opponent was Roman Kossak, with a dissertation committee consisting of Jon Henrik Forssell, Joel David Hamkins (myself) and Vera Koponen, chaired by Fredrik Engström. Congratulations!

University of Gothenburg profile | ar $𝜒$ iv | Research Gate

Paul K. Gorbow, “Self-similarity in the foundations,” PhD dissertation for the University of Gothenburg, Acta Philosophica Gothoburgensia 32, June 2018. (arxiv:1806.11310)

Abstract. This thesis concerns embeddings and self-embeddings of foundational structures in both set theory and category theory.

The first part of the work on models of set theory consists in establishing a refined version of Friedman’s theorem on the existence of embeddings between countable non-standard models of a fragment of ZF, and an analogue of a theorem of Gaifman to the effect that certain countable models of set theory can be elementarily end-extended to a model with many automorphisms whose sets of fixed points equal the original model. The second part of the work on set theory consists in combining these two results into a technical machinery, yielding several results about non-standard models of set theory relating such notions as self-embeddings, their sets of fixed points, strong rank-cuts, and set theories of different strengths.

The work in foundational category theory consists in the formulation of a novel algebraic set theory which is proved to be equiconsistent to New Foundations (NF), and which can be modulated to correspond to intuitionistic or classical NF, with or without atoms. A key axiom of this theory expresses that its structures have an endofunctor with natural properties.

In the Swedish style of dissertation defense, the opponent (in this case Roman Kossak) summarizes the dissertation, placing it in a broader context, and then challenges various parts of it, probing the candidate’s expertise in an extended discussion. What a pleasure it was to see this. After this, there is a broader discussion, in which the committee is also involved.

Math for kids: fun with orthoprojections!

Posted on May 27, 2018 by Joel David Hamkins

I had the pleasure a few weeks ago to visit my daughter’s math class at her school and undertake some fun math activities with the sixth graders (11-12 years old, all girls). What a fun time we had!

The topic was orthoprojection and the problem of gaining insight about a three-dimensional object or arrangement by considering its various orthogonal projections.

I had prepared a collection of puzzles, which I hoped would challenge the students in spatial reasoning and abstract visualization. (The puzzle booklet is available at bottom.)

The puzzles involved orthogonal projections of arrangements of unit blocks.

Unit blocks are a certain kind of wooden block toy, which exhibit precise dimensions in the ratio $1 \times 2 \times 4$ . Thus, two blocks oriented the shortest way combine to the same thickness as one block oriented another way, or half the long length. Thus, unit blocks can be flexibly combined in a huge variety of combinations, often leading to aesthetically pleasing and structurally sound creations. Furthermore, they are thought to help develop a child’s intuition for fractions in a completely natural and meaningful way, for often the child needs to build a support exactly $1 / 4$ unit or $1 / 2$ unit taller, or what have you, and in this way they are lead to see how the fractional units combine into wholes.

Unit blocks are commonly found in American elementary schools and kindergartens, and woodworkers will recognize that one can make a set of unit blocks from standard $2 \times 4$ lumber, available at most hardware stores. You can also buy unit block sets online, and my opinion is that one hardly needs any other toy than a good unit block set for any child aged 2 to 102. Note: you do NOT need any of the fancy extra blocks, not following the unit block standard, that are sometimes available with these sets; the quality of play is best with just the unit blocks and half-units, thin units, double units and so on.

For the school visit, I brought sufficient blocks for all the girls, and explained that we were going to play with blocks the way that a mathematician or engineer might play with blocks. And I had prepared a puzzle booklets, one per child (available below).

For each puzzle, one sees the front view, top view and right side view of an arrangement of blocks, and the challenge is to assemble the blocks so as to realize those views. (In these puzzles, I had chosen not to show any hidden lines and edges, to make them slightly more challenging, although it would also make sense to me to show hidden lines; it would be customary to do so with a dashed line.)

Here are a few more easy examples with solutions.

It happens that these front/top/side projection view problems inspire some deep feelings in me, for they remind me of my father, who was a mechanical engineer. In my childhood, he would often bring home and show me blueprints of the machines or machine parts that he was designing or working with, and those blueprints were filled with front/top/side projection views of the various parts. In pre-computer design days, engineers would specify their machine parts by providing the various othogonal views. (Nowadays, of course, computers are used and one can compute orthogonal and perspective views from any angle.)

In my daughter’s classroom, the students took up the puzzles with a seriousness that shocked me. Once we had passed out the puzzle booklets and distributed the blocks, the girls just steamed through the puzzles, one after the other, totally absorbed. They didn’t want any hints or advice or help of any kind; they just went from each puzzle to the next, solving them one after another. There were a sufficient number of blocks for them all to work on the smaller puzzles on their own, but for the larger puzzles, they formed groups and combined blocks. It was a big success!

Without further ado, here are your puzzles. I’ve also included some photos below, out of order, and some puzzles do not match a photo and vice versa, but you can look at the photos if you need a hint.

After these puzzles, we moved on to the inverse problem. The girls made their own arrangement of blocks and then drew all six orthogonal projections: front, top, right, left, back, bottom. You can draw them on the net of a cube, so that you can imagine folding the cube so as to realize the projections.

And after this, we moved beyond unit blocks to more general shapes. Can you solve the following projection puzzles?

The most challenging puzzle was the following. Can you imagine a solid that appears as a square from the front, a circle from the top and a triangle from the right side?

The complete puzzle booklet is available here: Fun with orthoprojections!

(And here is an alternative version of the puzzles made by David Butler for use with Jenga blocks, which have the dimensional ratios $3 \times 5 \times 15$ rather than $1 \times 2 \times 4$ : Jenga Views; see also this Twitter thread.)

Although I made the puzzles with six-graders in mind, the puzzles are interesting for people of any age, and I have proof: a picture of some of my CUNY math-major college students solving the puzzles in my office.

And here are videos of some fascinating sculptures playing with orthoprojections:

https://youtu.be/pn74pSlznj8

Oxford University, Professor of Logic & Sir Peter Strawson Fellow, University College Oxford

Posted on May 17, 2018 by Joel David Hamkins

In September 2018, I took up a new position in Oxford:

Professor of Logic in the Faculty of Philosophy at Oxford University, and
Sir Peter Strawson Fellow in Philosophy, University College, Oxford.

I am looking forward to starting this new chapter in my life and academic career.

Wish me luck!

Set-theoretic potentialism and the universal finite set, Scandinavian Logic Symposium, June 2018

Posted on April 22, 2018 by Joel David Hamkins

This will be an invited talk at the Scandinavian Logic Symposium SLS 2018, held at the University of Gothenburg in Sweden, June 11-13, 2018.

Abstract. Providing a set-theoretic analogue of the universal algorithm, I shall define a certain finite set in set theory
${𝑥 ∣ 𝜑 (𝑥)}$
and prove that it exhibits a universal extension property: it can be any desired particular finite set in the right set-theoretic universe and it can become successively any desired larger finite set in top-extensions of that universe. Specifically, ZFC proves the set is finite; the definition $𝜑$ has complexity $Σ 2$ and therefore any instance of it $𝜑 (𝑥)$ is locally verifiable inside any sufficiently large $𝑉 𝜃$ ; the set is empty in any transitive model; and if $𝜑$ defines the set $𝑦$ in some countable model $𝑀$ of ZFC and $𝑦 \subset 𝑧$ for some finite set $𝑧$ in $𝑀$ , then there is a top-extension of $𝑀$ to a model $𝑁$ of ZFC in which $𝜑$ defines the new set $𝑧$ . I shall draw out consequences of the universal finite set for set-theoretic potentialism and discuss several issues it raises in the philosophy of set theory.

The talk will include joint work with W. Hugh Woodin, Øystein Linnebo and others.

Slides: Set-theoretic potentialism and universal finite set SLS 2018

Infinite Sudoku and the Sudoku game

Posted on April 16, 2018 by Joel David Hamkins

Consider what I call the Sudoku game, recently introduced in the MathOverflow question Who wins two-player Sudoku? posted by Christopher King (user PyRulez). Two players take turns placing numbers on a Sudoku board, obeying the rule that they must never explicitly violate the Sudoku condition: the numbers on any row, column or sub-board square must never repeat. The first player who cannot continue legal play loses. Who wins the game? What is the winning strategy?

The game is not about building a global Sudoku solution, since a move can be legal in this game even when it is not part of any global Sudoku solution, provided only that it doesn’t yet explicitly violate the Sudoku condition. Rather, the Sudoku game is about trying to trap your opponent in a maximal such position, a position which does not yet explicitly violate the Sudoku condition but which cannot be further extended.

In my answer to the question on MathOverflow, I followed an idea suggested to me by my daughter Hypatia, namely that on even-sized boards $𝑛 2 \times 𝑛 2$ where $𝑛$ is even, then the second player can win with a mirroring strategy: simply copy the opponent’s moves in reflected mirror image through the center of the board. In this way, the second player ensures that the position on the board is always symmetric after her play, and so if the previous move was safe, then her move also will be safe by symmetry. This is therefore a winning strategy for the second player, since any violation of the Sudoku condition will arise on the opponent’s play.

Second player simply copies moves at reflected location

This argument works on even-sized boards precisely because the reflection of every row, column and sub-board square is a totally different row, column and sub-board square, and so any new violation of the Sudoku conditions would reflect to a violation that was already there. The mirror strategy definitely does not work on the odd-sized boards, including the main $9 \times 9$ case, since if the opponent plays on the central row, copying directly would immediately introduce a Sudoku violation.

After posting that answer, Orson Peters (user orlp) pointed out that one can modify it to form a winning strategy for the first player on odd-sized boards, including the main $9 \times 9$ case. In this case, let the first player begin by playing $5$ in the center square, and then afterwards copy the opponent’s moves, but with the ten’s complement at the reflected location. So if the opponent plays $𝑥$ , then the first player plays $10 - 𝑥$ at the reflected location. In this way, the first player can ensure that the board is ten’s complement symmetric after her moves. The point is that again this is sufficient to know that she will never introduce a violation, since if her $10 - 𝑥$ appears twice in some row, column or sub-board square, then $𝑥$ must have already appeared twice in the reflected row, column or sub-board square before that move.

Start with 5 at center, and then copy with ten's complement at reflected location

This idea is fully general for odd-sized Sudoku boards $𝑛 2 \times 𝑛 2$ , where $𝑛$ is odd. If $𝑛 = 2 𝑘 - 1$ , then the first player starts with $𝑘$ in the very center and afterward plays the $2 𝑘$ -complement of her opponent’s move at the reflected location.

Conclusion.

On even-sized Sudoku boards, the second player wins the Sudoku game by the mirror copying strategy.
On odd-sized Sudoku boards, the first players wins the Sudoku game by the complement-mirror copying strategy.

Note that on the even boards, the second player could also play complement mirror copying just as successfully.

What I really want to tell you about, however, is the infinite Sudoku game (following a suggestion of Sam Hopkins). Suppose that we try to play the Sudoku game on a board whose subboard squares are $ℤ \times ℤ$ , so that the full board is a $ℤ \times ℤ$ array of those squares, making $ℤ 2 \times ℤ 2$ altogether. (Or perhaps you might prefer the board $ℕ 2 \times ℕ 2$ ?)

Each sub-board is a fully infinite Z x Z board, and we have Z x Z many of them altogether, Z = { ... -2, -1, 0, 1, 2, ... }

One thing to notice is that on an infinite board, it is no longer possible to get trapped at a finite stage of play, since every finite position can be extended simply by playing a totally new label from the set of labels; such a move would never lead to a new violation of the explicit Sudoku condition.

For this reason, I should like to introduce the Sudoku Solver-Spoiler game variation as follows. There are two players: the Sudoku Solver and the Sudoku Spoiler. The Solver is trying to build a global Sudoku solution on the board, while the Spoiler is trying to prevent this. Both players must obey the Sudoku condition that labels are never to be explicitly repeated in any row, column or sub-board square. On an infinite board, the game proceeds transfinitely, until the board is filled or there are no legal moves. The Solver wins a play of the game, if she successfully builds a global Sudoku solution, which means not only that every location has a label and there are no repetitions in any row, column or sub-board square, but also that every label in fact appears in every row, column and sub-board square. That is, to count as a solution, the labels on any row, column and sub-board square must be a bijection with the set of labels. (On infinite boards, this is a stronger requirement than merely insisting on no repetitions.)

The Solver-Spoiler game makes sense in complete generality on any set $𝑆$ , whether finite or infinite. The sub-boards are $𝑆 2 = 𝑆 \times 𝑆$ , and one has an $𝑆 \times 𝑆$ array of them, so $𝑆 2 \times 𝑆 2$ for the whole board. Every row and column has the same size as the sub-board square $𝑆 2$ , and the set of labels should also have this size.

Upon reflection, one realizes that what matters about $𝑆$ is just its cardinality, and we really have for every cardinal $𝜅$ the $𝜅$ -Sudoku Solver-Spoiler game, whose board is $𝜅 2 \times 𝜅 2$ , a $𝜅 \times 𝜅$ array of $𝜅 \times 𝜅$ sub-boards. In particular, the game $ℤ 2 \times ℤ 2$ is actually isomorphic to the game $ℕ 2 \times ℕ 2$ , despite what might feel initially like a very different board geometry.

What I claim is that the Solver has a winning strategy in the all the infinite Sudoku Solver-Spoiler games, in a very general and robust manner.

Theorem. For every infinite cardinal $𝜅$ , the Solver has a winning strategy to win the $𝜅$ -Sudoku Solver-Spoiler game.

The strategy will win in $𝜅$ many moves, producing a full Sudoku solution.
The Solver can win whether she goes first or second, starting from any legal position of size less than $𝜅$ .
The Solver can win even when the Spoiler is allowed to play finitely many labels at once on each turn, or fewer than $𝜅$ many moves (if $𝜅$ is regular), even if the Solver is only allowed one move each turn.
In the countably infinite Sudoku game, the Solver can win even if the Spoiler is allowed to make infinitely many moves at once, provided only that the resulting position can in principle be extended to a full solution.

Proof. Consider first the countably infinite Sudoku game, and assume the initial position is finite and that the Spoiler will make finitely many moves on each turn. Consider what it means for the Solver to win at the limit. It means, first of all, that there are no explicit repetitions in any row, column or sub-board. This requirement will be ensured since it is part of the rules for legal play not to violate it. Next, the Solver wants to ensure that every square has a label on it and that every label appears at least once in every row, every column and every sub-board. If we think of these as individual specific requirements, we have countably many requirements in all, and I claim that we can arrange that the Solver will simply satisfy the $𝑛 𝑡 ℎ$ requirement on her $𝑛 𝑡 ℎ$ play. Given any finite position, she can always find something to place in any given square, using a totally new label if need be. Given any finite position, any row and any particular label $𝑘$ , since can always find a place on that row to place the label, which has no conflict with any column or sub-board, since there are infinitely many to choose from and only finitely many conflicts. Similarly with columns and sub-boards. So each of the requirements can always be fulfilled one-at-a-time, and so in $𝜔$ many moves she can produce a full solution.

The argument works equally well no matter who goes first or if the Spoiler makes arbitrary finite play, or indeed even infinite play, provided that the play is part of some global solution (perhaps a different one each time), since on each move the Solve can simply meet the requirement by using that solution at that stage.

An essentially similar argument works when $𝜅$ is uncountable, although now the play will proceed for $𝜅$ many steps. Assuming $𝜅 2 = 𝜅$ , a consequence of the axiom of choice, there are $𝜅$ many requirements to meet, and the Solve can meet requirement $𝛼$ on the $𝛼 𝑡 ℎ$ move. If $𝜅$ is regular, we can again allow the Spoiler to make arbitrary size-less-than- $𝜅$ size moves, so that at any stage of play before $𝜅$ the position will still be size less than $𝜅$ . (If $𝜅$ is singular, one can allow Spoiler to make finitely many moves at once or indeed even some uniform bounded size $𝛿 < 𝜅$ many moves at once. $◻$

I find it interesting to draw out the following aspect of the argument:

Observation. Every finite labeling of an infinite Sudoku board that does not yet explicitly violate the Sudoku condition can be extended to a global solution.

Similarly, any size less than $𝜅$ labeling that does not yet explicitly violate the Sudoku condition can be extended to a global solution of the $𝜅$ -Sudoku board for any infinite cardinal $𝜅$ .

What about asymmetric boards? It has come to my attention that people sometimes look at asymmetric Sudoku boards, whose sub-boards are not square, such as in the six-by-six Sudoku case. In general, one could take Sudoku boards to consist of a $𝜆 \times 𝜅$ array of sub-boards of size $𝜅 \times 𝜆$ , where $𝜅$ and $𝜆$ are cardinals, not necessarily the same size and not necessarily both infinite or both finite. How does this affect the arguments I’ve given?

In the finite $(𝑛 \times 𝑚) \times (𝑚 \times 𝑛)$ case, if one of the numbers is even, then it seems to me that the reflection through the origin strategy works for the second player just as before. And if both are odd, then the first player can again play in the center square and use the mirror-complement strategy to trap the opponent. So that analysis will work fine.

In the case $(𝜅 \times 𝜆) \times (𝜆 \times 𝜅)$ where $𝜆 \leq 𝜅$ and $𝜅 = 𝜆 𝜅$ is infinite, then the proof of the theorem seems to break, since if $𝜆 < 𝜅$ , then with only $𝜆$ many moves, say putting a common symbol in each of the $𝜆$ many rectangles across a row, we can rule out that symbol in a fixed row. So this is a configuration of size less than $𝜅$ that cannot be extended to a full solution. For this reason, it seems likely to me that the Spoiler can win the Sudoko Solver-Spoiler game in the infinite asymmetric case.

Finally, let’s consider the Sudoku Solver-Spoiler game in the purely finite case, which actually is a very natural game, perhaps more natural than what I called the Sudoku game above. It seems to me that the Spoiler should be able to win the Solver-Spoiler game on any nontrivial finite board. But I don’t yet have an argument proving this. I asked a question on MathOverflow: The Sudoku game: Solver-Spoiler variation.

Kameryn J. Williams, PhD 2018, CUNY Graduate Center

Posted on April 8, 2018 by Joel David Hamkins

Kameryn J. Williams successfully defended his dissertation under my supervision at the CUNY Graduate Center on April 6th, 2018, earning his Ph.D. degree in May 2018. He has accepted a position in mathematics at the University of Hawaii, to begin Fall 2018.

What a pleasure it was to work with Kameryn, an extremely talented mathematician with wide interests and huge promise.

Kameryn J Williams | MathOverflow | ar $𝜒$ iv

Kameryn J. Williams, The Structure of Models of Second-order Set Theories, Ph.D. dissertation for The Graduate Center of the City University of New York, May, 2018. arXiv:1804.09526.

Abstract. This dissertation is a contribution to the project of second-order set theory, which has seen a revival in recent years. The approach is to understand second-order set theory by studying the structure of models of second-order set theories. The main results are the following, organized by chapter. First, I investigate the poset of T-realizations of a fixed countable model of ZFC, where T is a reasonable second-order set theory such as GBC or KM, showing that it has a rich structure. In particular, every countable partial order embeds into this structure. Moreover, we can arrange so that these embedding preserve the existence/nonexistence of upper bounds, at least for finite partial orders. Second I generalize some constructions of Marek and Mostowski from KM to weaker theories. They showed that every model of KM plus the Class Collection schema “unrolls” to a model of ZFC− with a largest cardinal. I calculate the theories of the unrolling for a variety of second-order set theories, going as weak as GBC + ETR. I also show that being T-realizable goes down to submodels for a broad selection of second-order set theories T. Third, I show that there is a hierarchy of transfinite recursion principles ranging in strength from GBC to KM. This hierarchy is ordered first by the complexity of the properties allowed in the recursions and second by the allowed heights of the recurions. Fourth, I investigate the question of which second-order set theories have least models. I show that strong theories—such as KM or $Π 11$ -CA—do not have least transitive models, while weaker theories—from GBC to GBC + ETR $O r d$ —do have least transitive models.

In addition to his dissertation work and the research currently arising out of it, Kameryn has undertaken a number of collaborations with various international research efforts, including the following:

He is a co-author on The exact strength of the class forcing theorem. [bibtex key=”GitmanHamkinsHolySchlichtWilliams:The-exact-strength-of-the-class-forcing-theorem”]
He is co-author on a current joint project with Miha Habič, myself, Daniel Klausner and Jonathan Verner concerning the nonamalgamation phenomenon in the generic multiverse of a countable model of set theory.
He is co-author on a current joint project with myself and Philip Welch concerning the universal $Σ 1$ -definable finite sequence, an analogue of the universal finite set, but for the constructible universe.

Different set theories are never bi-interpretable

Posted on March 27, 2018 by Joel David Hamkins

I was fascinated recently to discover something I hadn’t realized about relative interpretability in set theory, and I’d like to share it here. Namely,

Different set theories extending ZF are never bi-interpretable!

For example, ZF and ZFC are not bi-interpretable, and neither are ZFC and ZFC+CH, nor ZFC and ZFC+ $\neg$ CH, despite the fact that all these theories are equiconsistent. The basic fact is that there are no nontrivial instances of bi-interpretation amongst the models of ZF set theory. This is surprising, and could even be seen as shocking, in light of the philosophical remarks one sometimes hears asserted in the philosophy of set theory that what is going on with the various set-theoretic translations from large cardinals to determinacy to inner model theory, to mention a central example, is that we can interpret between these theories and consequently it doesn’t much matter which context is taken as fundamental, since we can translate from one context to another without loss.

The bi-interpretation result shows that these interpretations do not and cannot rise to the level of bi-interpretations of theories — the most robust form of mutual relative interpretability — and consequently, the translations inevitably must involve a loss of information.

To be sure, set theorists classify the various set-theoretic principles and theories into a hierarchy, often organized by consistency strength or by other notions of interpretative power, using forcing or definable inner models. From any model of ZF, for example, we can construct a model of ZFC, and from any model of ZFC, we can construct models of ZFC+CH or ZFC+ $\neg$ CH and so on. From models with sufficient large cardinals we can construct models with determinacy or inner-model-theoretic fine structure and vice versa. And while we have relative consistency results and equiconsistencies and even mutual interpretations, we will have no nontrivial bi-interpretations.

(I had proved the theorem a few weeks ago in joint work with Alfredo Roque Freire, who is visiting me in New York this year. We subsequently learned, however, that this was a rediscovery of results that have evidently been proved independently by various authors. Albert Visser proves the case of PA in his paper, “Categories of theories and interpretations,” Logic in Tehran, 284–341, Lect. Notes Log., 26, Assoc. Symbol. Logic, La Jolla, CA, 2006, (pdf, see pp. 52-55). Ali Enayat gave a nice model-theoretic argument for showing specifically that ZF and ZFC are not bi-interpretable, using the fact that ZFC models can have no involutions in their automorphism groups, but ZF models can; and he proved the general version of the theorem, for ZF, second-order arithmetic $𝑍 2$ and second-order set theory KM in his 2016 article, A. Enayat, “Variations on a Visserian theme,” in Liber Amicorum Alberti : a tribute to Albert Visser / Jan van Eijck, Rosalie Iemhoff and Joost J. Joosten (eds.) Pages, 99-110. ISBN, 978-1848902046. College Publications, London. The ZF version was apparently also observed independently by Harvey Friedman, Visser and Fedor Pakhomov.)

Meanwhile, let me explain our argument. Recall from model theory that one theory $𝑆$ is interpreted in another theory $𝑇$ , if in any model of the latter theory $𝑀 ⊧ 𝑇$ , we can define (and uniformly so in any such model) a certain domain $𝑁 \subset 𝑀 𝑘$ and relations and functions on that domain so as to make $𝑁$ a model of $𝑆$ . For example, the theory of algebraically closed fields of characteristic zero is interpreted in the theory of real-closed fields, since in any real-closed field $𝑅$ , we can consider pairs $(𝑎, 𝑏)$ , thinking of them as $𝑎 + 𝑏 𝑖$ , and define addition and multiplication on those pairs in such a way so as to construct an algebraically closed field of characteristic zero.

Two theories are thus mutually interpretable, if each of them is interpretable in the other. Such theories are necessarily equiconsistent, since from any model of one of them we can produce a model of the other.

Note that mutual interpretability, however, does not insist that the two translations are inverse to each other, even up to isomorphism. One can start with a model of the first theory $𝑀 ⊧ 𝑇$ and define the interpreted model $𝑁 ⊧ 𝑆$ of the second theory, which has a subsequent model of the first theory again $¯ 𝑀 ⊧ 𝑇$ inside it. But the definition does not insist on any particular connection between $𝑀$ and $¯ 𝑀$ , and these models need not be isomorphic nor even elementarily equivalent in general.

By addressing this, one arrives at a stronger and more robust form of mutual interpretability. Namely, two theories $𝑆$ and $𝑇$ are bi-interpretable, if they are mutually interpretable in such a way that the models can see that the interpretations are inverse. That is, for any model $𝑀$ of the theory $𝑇$ , if one defines the interpreted model $𝑁 ⊧ 𝑆$ inside it, and then defines the interpreted model $¯ 𝑀$ of $𝑇$ inside $𝑁$ , then $𝑀$ is isomorphic to $¯ 𝑀$ by a definable isomorphism in $𝑀$ , and uniformly so (and the same with the theories in the other direction). Thus, every model of one of the theories can see exactly how it itself arises definably in the interpreted model of the other theory.

For example, the theory of linear orders $\leq$ is bi-interpretable with the theory of strict linear order $<$ , since from any linear order $\leq$ we can define the corresponding strict linear order $<$ on the same domain, and from any strict linear order $<$ we can define the corresponding linear order $\leq$ , and doing it twice brings us back again to the same order.

For a richer example, the theory PA is bi-interpretable with the finite set theory $Z F \neg \infty$ , where one drops the infinity axiom from ZF and replaces it with the negation of infinity, and where one has the $\in$ -induction scheme in place of the foundation axiom. The interpretation is via the Ackerman encoding of hereditary finite sets in arithmetic, so that $𝑛 𝐸 𝑚$ just in case the $𝑛 𝑡 ℎ$ binary digit of $𝑚$ is $1$ . If one starts with the standard model $ℕ$ , then the resulting structure $⟨ ℕ, 𝐸 ⟩$ is isomorphic to the set $⟨ H F, \in ⟩$ of hereditarily finite sets. More generally, by carrying out the Ackermann encoding in any model of PA, one thereby defines a model of $Z F \neg \infty$ , whose natural numbers are isomorphic to the original model of PA, and these translations make a bi-interpretation.

We are now ready to prove that this bi-interpretation situation does not occur with different set theories extending ZF.

Theorem. Distinct set theories extending ZF are never bi-interpretable. Indeed, there is not a single model-theoretic instance of bi-interpretation occurring with models of different set theories extending ZF.

Proof. I mean “distinct” here in the sense that the two theories are not logically equivalent; they do not have all the same theorems. Suppose that we have a bi-interpretation instance of the theories $𝑆$ and $𝑇$ extending ZF. That is, suppose we have a model $⟨ 𝑀, \in ⟩ ⊧ 𝑇$ of the one theory, and inside $𝑀$ , we can define an interpreted model of the other theory $⟨ 𝑁, \in 𝑁 ⟩ ⊧ 𝑆$ , so the domain of $𝑁$ is a definable class in $𝑀$ and the membership relation $\in 𝑁$ is a definable relation on that class in $𝑀$ ; and furthermore, inside $⟨ 𝑁, \in 𝑁 ⟩$ , we have a definable structure $⟨ ¯ 𝑀, \in ¯ 𝑀 ⟩$ which is a model of $𝑇$ again and isomorphic to $⟨ 𝑀, \in 𝑀 ⟩$ by an isomorphism that is definable in $⟨ 𝑀, \in 𝑀 ⟩$ . So $𝑀$ can define the map $𝑎 \mapsto ¯ 𝑎$ that forms an isomorphism of $⟨ 𝑀, \in 𝑀 ⟩$ with $⟨ ¯ 𝑀, \in ¯ 𝑀 ⟩$ . Our argument will work whether we allow parameters in any of these definitions or not.

I claim that $𝑁$ must think the ordinals of $¯ 𝑀$ are well-founded, for otherwise it would have some bounded cut $𝐴$ in the ordinals of $¯ 𝑀$ with no least upper bound, and this set $𝐴$ when pulled back pointwise by the isomorphism of $𝑀$ with $¯ 𝑀$ would mean that $𝑀$ has a cut in its own ordinals with no least upper bound; but this cannot happen in ZF.

If the ordinals of $𝑁$ and $¯ 𝑀$ are isomorphic in $𝑁$ , then all three models have isomorphic ordinals in $𝑀$ , and in this case, $⟨ 𝑀, \in 𝑀 ⟩$ thinks that $⟨ 𝑁, \in 𝑁 ⟩$ is a well-founded extensional relation of rank $O r d$ . Such a relation must be set-like (since there can be no least instance where the predecessors form a proper class), and so $𝑀$ can perform the Mostowski collapse of $\in 𝑁$ , thereby realizing $𝑁$ as a transitive class $𝑁 \subseteq 𝑀$ with $\in 𝑁 = \in 𝑀 ↾ 𝑁$ . Similarly, by collapsing we may assume $¯ 𝑀 \subseteq 𝑁$ and $\in ¯ 𝑀 = \in 𝑀 ↾ ¯ 𝑀$ . So the situation consists of inner models $¯ 𝑀 \subseteq 𝑁 \subseteq 𝑀$ and $⟨ ¯ 𝑀, \in 𝑀 ⟩$ is isomorphic to $⟨ 𝑀, \in 𝑀 ⟩$ in $𝑀$ . This is impossible unless all three models are identical, since a simple $\in 𝑀$ -induction shows that $𝜋 (𝑦) = 𝑦$ for all $𝑦$ , because if this is true for the elements of $𝑦$ , then $𝜋 (𝑦) = {𝜋 (𝑥) ∣ 𝑥 \in 𝑦} = {𝑥 ∣ 𝑥 \in 𝑦} = 𝑦$ . So $¯ 𝑀 = 𝑁 = 𝑀$ and so $𝑁$ and $𝑀$ satisfy the same theory, contrary to assumption.

If the ordinals of $¯ 𝑀$ are isomorphic to a proper initial segment of the ordinals of $𝑁$ , then a similar Mostowski collapse argument would show that $⟨ ¯ 𝑀, \in ¯ 𝑀 ⟩$ is isomorphic in $𝑁$ to a transitive set in $𝑁$ . Since this structure in $𝑁$ would have a truth predicate in $𝑁$ , we would be able to pull this back via the isomorphism to define (from parameters) a truth predicate for $𝑀$ in $𝑀$ , contrary to Tarski’s theorem on the non-definability of truth.

The remaining case occurs when the ordinals of $𝑁$ are isomorphic in $𝑁$ to an initial segment of the ordinals of $¯ 𝑀$ . But this would mean that from the perspective of $𝑀$ , the model $⟨ 𝑁, \in 𝑁 ⟩$ has some ordinal rank height, which would mean by the Mostowski collapse argument that $𝑀$ thinks $⟨ 𝑁, \in 𝑁 ⟩$ is isomorphic to a transitive set. But this contradicts the fact that $𝑀$ has an injection of $𝑀$ into $𝑁$ . $◻$

It follows that although ZF and ZFC are equiconsistent, they are not bi-interpretable. Similarly, ZFC and ZFC+CH and ZFC+ $\neg$ CH are equiconsistent, but no pair of them is bi-interpretable. And again with all the various equiconsistency results concerning large cardinals.

A similar argument works with PA to show that different extensions of PA are never bi-interpretable.

The universal finite set, Rutgers Logic Seminar, April 2018

Posted on March 19, 2018 by Joel David Hamkins

This will be a talk for the Rutgers Logic Seminar, April 2, 2018. Hill Center, Busch campus.

Abstract. I shall define a certain finite set in set theory ${𝑥 ∣ 𝜑 (𝑥)}$ and prove that it exhibits a universal extension property: it can be any desired particular finite set in the right set-theoretic universe and it can become successively any desired larger finite set in top-extensions of that universe. Specifically, ZFC proves the set is finite; the definition $𝜑$ has complexity $Σ 2$ and therefore any instance of it $𝜑 (𝑥)$ is locally verifiable inside any sufficient $𝑉 𝜃$ ; the set is empty in any transitive model and others; and if $𝜑$ defines the set $𝑦$ in some countable model $𝑀$ of ZFC and $𝑦 \subset 𝑧$ for some finite set $𝑧$ in $𝑀$ , then there is a top-extension of $𝑀$ to a model $𝑁$ in which $𝜑$ defines the new set $𝑧$ . The definition can be thought of as an idealized diamond sequence, and there are consequences for the philosophical theory of set-theoretic top-extensional potentialism.

This is joint work with W. Hugh Woodin.

Determinacy for open class games is preserved by forcing, CUNY Set Theory Seminar, April 2018

Posted on March 6, 2018 by Joel David Hamkins

This will be a talk for the CUNY Set Theory Seminar, April 27, 2018, GC Room 6417, 10-11:45am (please note corrected date).

Abstract. Open class determinacy is the principle of second order set theory asserting of every two-player game of perfect information, with plays coming from a (possibly proper) class $𝑋$ and the winning condition determined by an open subclass of $𝑋 𝜔$ , that one of the players has a winning strategy. This principle finds itself about midway up the hierarchy of second-order set theories between Gödel-Bernays set theory and Kelley-Morse, a bit stronger than the principle of elementary transfinite recursion ETR, which is equivalent to clopen determinacy, but weaker than GBC+ $Π 11$ -comprehension. In this talk, I’ll given an account of my recent joint work with W. Hugh Woodin, proving that open class determinacy is preserved by forcing. A central part of the proof is to show that in any forcing extension of a model of open class determinacy, every well-founded class relation in the extension is ranked by a ground model well-order relation. This work therefore fits into the emerging focus in set theory on the interaction of fundamental principles of second-order set theory with fundamental set theoretic tools, such as forcing. It remains open whether clopen determinacy or equivalently ETR is preserved by set forcing, even in the case of the forcing merely to add a Cohen real.

Nonamalgamation in the Cohen generic multiverse, CUNY Logic Workshop, March 2018

Posted on March 6, 2018 by Joel David Hamkins

This will be a talk for the CUNY Logic Workshop on March 23, 2018, GC 6417 2-3:30pm.

Abstract. Consider a countable model of set theory $𝑀$ in the context of all its successive forcing extensions and grounds. This generic multiverse has long been known to exhibit instances of nonamalgamation: one can have two extensions $𝑀 [𝑐]$ and $𝑀 [𝑑]$ , both adding a merely a generic Cohen real, which have no further extension in common. In this talk, I shall describe new joint work that illuminates the extent of non-amalgamation: every finite partial order (and more) embeds into the generic multiverse over any given model in a way that preserves amalgamability and non-amalgamability. The proof uses the set-theoretic blockchain argument (pictured above), which has affinities with constructions in computability theory in the Turing degrees. Other arguments, which also resemble counterparts in computability theory, show that the generic multiverse exhibits the exact pair phenonemon for increasing chains. This is joint work with Miha Habič, myself, Lukas Daniel Klausner and Jonathan Verner. The paper will be available this Spring.

https://plus.google.com/u/0/+JoelDavidHamkins1/posts/NJp2N7bkkrR

Share:

Share:

Share:

Can set-theoretic mereology serve as a foundation of mathematics?

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share:

Share: