Kaethe Lynn Bruesselbach Minden, PhD 2017, CUNY Graduate Center

Kaethe Lynn Bruesselbach Minden successfully defended her dissertation on April 7, 2017 at the CUNY Graduate Center, under the supervision of Professor Gunter Fuchs. I was a member of the dissertation committee, along with Arthur Apter.

Her defense was impressive!  She was a master of the entire research area, ready at hand with the technical details to support her account of any topic that arose.

Kaethe Minden + sloth

math blognylogic profilear$\chi$iv | math geneology

Kaethe Minden, “On Subcomplete Forcing,” Ph.D. dissertation for The Graduate Center of the City University of New York, May, 2017. (arxiv/1705.00386)

Abstract. I survey an array of topics in set theory and their interaction with, or in the context of, a novel class of forcing notions: subcomplete forcing. Subcomplete forcing notions satisfy some desirable qualities; for example they don’t add any new reals to the model, and they admit an iteration theorem. While it is straightforward to show that any forcing notion which is countably closed is also subcomplete, it turns out that other well-known, more subtle forcing notions like Prikry forcing and Namba forcing are also subcomplete. Subcompleteness was originally defined by Ronald Björn Jensen around 2009. Jensen’s writings make up the vast majority of the literature on the subject. Indeed, the definition in and of itself is daunting. I have attempted to make the subject more approachable to set theorists, while showing various properties of subcomplete forcing which one might desire of a forcing class.

It is well-known that countably closed forcings cannot add branches through $\omega_1$-trees. I look at the interaction between subcomplete forcing and $\omega_1$-trees. It turns out that sub-complete forcing also does not add cofinal branches to $\omega_1$-trees. I show that a myriad of other properties of trees of height $\omega_1$ as explored in [FH09] are preserved by subcomplete forcing; for example, I show that the unique branch property of Suslin trees is preserved by subcomplete forcing.

Another topic I explored is the Maximality Principle ($\text{MP}$). Following in the footsteps of Hamkins [Ham03], Leibman [Lei], and Fuchs [Fuc08], [Fuc09], I examine the subcomplete maximality principle. In order to elucidate the ways in which subcomplete forcing generalizes the notion of countably closed forcing, I compare the countably closed maximality principle ($\text{MP}_{<\omega_1\text{-closed}}$) to the subcomplete maximality principle ($\text{MP}_{sc}$). Again, since countably closed forcing is subcomplete, this is a natural question to ask. I was able to show that many of the results about $\text{MP}_{<\omega_1\text{-closed}}$ also hold for $\text{MP}_{sc}$; for example, the boldface appropriate notion of $\text{MP}_{sc}$ is equiconsistent with a fully reflecting cardinal. However, it is not the case that there are direct implications between the subcomplete and countably closed maximality principles.

Another forcing principle explored in my thesis is the Resurrection Axiom ($\text{RA}$). Hamkins and Johnstone [HJ14a] defined the resurrection axiom only relative to $H_{\mathfrak{c}}$, and focus mainly on the resurrection axiom for proper forcing. They also show the equiconsistency of various resurrection axioms with an uplifting cardinal. I argue that the subcomplete resurrection axiom should naturally be considered relative to $H_{\omega_2}$, and showed that the subcomplete resurrection axiom is equiconsistent with an uplifting cardinal.

A question reasonable to ask about any class of forcings is whether or not the resurrection axiom and the maximality principle can consistently both hold for that class. I originally had this question about the full principles, not restricted to any class, but in my thesis it was appropriate to look at the question for subcomplete forcing. I answer the question positively for subcomplete forcing using a strongly uplifting fully reflecting cardinal, which is a combination of the large cardinals needed to force the principles separately. I show that the boldface versions of $\text{MP}_{sc}+\text{RA}_{sc}$ both holding is equiconsistent with the existence of a strongly uplifting fully reflecting cardinal. While Jensen [Jen14] shows that Prikry forcing is subcomplete, I long suspected that many variants of Prikry forcing which have a kind of genericity criterion are also subcomplete. After much work I managed to show that a variant of Prikry forcing known as Diagonal Prikry Forcing is subcomplete, giving another example of subcomplete forcing to add to the list.

Kaethe Minden defense

Kaethe has taken up a faculty position at Marlboro College in Vermont.

Miha E. Habič, PhD 2017, CUNY Graduate Center

Miha E. Habič successfully defended his dissertation under my supervision at the CUNY Graduate Center on April 7th, 2017, earning his Ph.D. degree in May 2017.

It was truly a pleasure to work with Miha, who is an outstanding young mathematician with enormous promise. I shall look forward to seeing his continuing work.

Miha Habic

Cantor’s paradise | MathOverflow | MathSciNet  | NY Logic profilear$\chi$iv

Miha E. Habič, “Joint Laver diamonds and grounded forcing axioms,”  Ph.D. dissertation for The Graduate Center of the City University of New York, May, 2017 (arxiv:1705.04422).

Abstract. In chapter 1 a notion of independence for diamonds and Laver diamonds is investigated. A sequence of Laver diamonds for $\kappa$ is joint if for any sequence of targets there is a single elementary embedding $j$ with critical point $\kappa$ such that each Laver diamond guesses its respective target via $j$. In the case of measurable cardinals (with similar results holding for (partially) supercompact cardinals) I show that a single Laver diamond for $\kappa$ yields a joint sequence of length $\kappa$, and I give strict separation results for all larger lengths of joint sequences. Even though the principles get strictly stronger in terms of direct implication, I show that they are all equiconsistent. This is contrasted with the case of $\theta$-strong cardinals where, for certain $\theta$, the existence of even the shortest joint Laver sequences carries nontrivial consistency strength. I also formulate a notion of jointness for ordinary $\diamondsuit_\kappa$-sequences on any regular cardinal $\kappa$. The main result concerning these shows that there is no separation according to length and a single $\diamondsuit_\kappa$-sequence yields joint families of all possible lengths.

 

In chapter 2 the notion of a grounded forcing axiom is introduced and explored in the case of Martin’s axiom. This grounded Martin’s axiom, a weakening of the usual axiom, states that the universe is a ccc forcing extension of some inner model and the restriction of Martin’s axiom to the posets coming from that ground model holds. I place the new axiom in the hierarchy of fragments of Martin’s axiom and examine its effects on the cardinal characteristics of the continuum. I also show that the grounded version is quite a bit more robust under mild forcing than Martin’s axiom itself.

Miha Habic defenseMiha will shortly begin a post-doctoral research position at Charles University in Prague.

Models of set theory with the same reals and the same cardinals, but which disagree on the continuum hypothesis

Terry_Marks,_Nightmare_in_a_MirrorI’d like to describe a certain interesting and surprising situation that can happen with models of set theory.

Theorem. If $\newcommand\ZFC{\text{ZFC}}\ZFC$ set theory is consistent, then there are two models of $\ZFC$ set theory $M$ and $N$ for which

  • $M$ and $N$ have the same real numbers $$\newcommand\R{\mathbb{R}}\R^M=\R^N.$$
  • $M$ and $N$ have the ordinals and the same cardinals $$\forall\alpha\qquad \aleph_\alpha^M=\aleph_\alpha^N$$
  • But $M$ thinks that the continuum hypothesis $\newcommand\CH{\text{CH}}\CH$ is true, while $N$ thinks that $\CH$ is false.

This is a little strange, since the two models have the set $\R$ in common and they agree on the cardinal numbers, but $M$ thinks that $\R$ has size $\aleph_1$ and $N$ will think that $\R$ has size $\aleph_2$.  In particular, $M$ can well-order the reals in order type $\omega_1$ and $N$ can do so in order-type $\omega_2$, even though the two models have the same reals and they agree that these order types have different cardinalities.

Another abstract way to describe what is going on is that even if two models of set theory, even transitive models, agree on which ordinals are cardinals, they needn’t agree on which sets are equinumerous, for sets they have in common, even for the reals.

Let me emphasize that it is the requirement that the models have the same cardinals that makes the problem both subtle and surprising. If you drop that requirement, then the problem is an elementary exercise in forcing: start with any model $V$, and first force $\CH$ to fail in $V[H]$ by adding a lot of Cohen reals, then force to $V[G]$ by collapsing the continuum to $\aleph_1$. This second step adds no new reals and forces $\CH$, and so $V[G]$ and $V[H]$ will have the same reals, while $V[H]$ thinks $\CH$ is true and $V[G]$ thinks $\CH$ is false. The problem becomes nontrivial and interesting mainly when you insist that cardinals are not collapsed.

In fact, the situation described in the theorem can be forced over any given model of $\ZFC$.

Theorem. Every model of set theory $V\models\ZFC$ has two set-forcing extensions $V[G]$ and $V[H]$ for which

  • $V[G]$ and $V[H]$ have the same real numbers $$\newcommand\R{\mathbb{R}}\R^{V[G]}=\R^{V[H]}.$$
  • $V[G]$ and $V[H]$ have the same cardinals $$\forall\alpha\qquad \aleph_\alpha^{V[G]}=\aleph_\alpha^{V[H]}$$
  • But $V[G]$ thinks that the continuum hypothesis $\CH$ is true, while $V[H]$ thinks that $\CH$ is false.

Proof. Start in any model $V\models\ZFC$, and by forcing if necessary, let’s assume $\CH$ holds in $V$. Let $H\subset\text{Add}(\omega,\omega_2)$ be $V$-generic for the forcing to add $\omega_2$ many Cohen reals. So $V[H]$ satisfies $\neg\CH$ and has the same ordinals and cardinals as $V$.

Next, force over $V[H]$ using the forcing from $V$ to collapse $\omega_2$ to $\omega_1$, forming the extension $V[H][g]$, where $g$ is the generic bijection between those ordinals. Since we used the forcing in $V$, which is countably closed there, it makes sense to consider $V[g]$.  In this extension, the forcing $\text{Add}(\omega,\omega_1^V)$ and $\text{Add}(\omega,\omega_2^V)$ are isomorphic. Since $H$ is $V[g]$-generic for the latter, let $G=g\mathrel{“}H$ be the image of this filter in $\text{Add}(\omega,\omega_1)$, which is therefore $V[g]$-generic for the former. So $V[g][G]=V[g][H]$. Since the forcing $\text{Add}(\omega,\omega_1)$ is c.c.c., it follows that $V[G]$ also has the same cardinals as $V$ and hence also the same as in $V[H]$.

If we now view these extensions as $V[G][g]=V[H][g]$ and note that the coutable closure of $g$ in $V$ implies that $g$ adds no new reals over either $V[G]$ or $V[H]$, it follows that $\R^{V[G]}=\R^{V[H]}$. So the two models have the same reals and the same cardinals. But $V[G]$ has $\CH$ and $V[H]$ has $\neg\CH$, in light of the forcing, and so the proof is complete. QED

Let me prove the following surprising generalization.

Theorem. If $V$ is any model of $\ZFC$ and $V[G]$ is the forcing extension obtained by adding $\kappa$ many Cohen reals, for some uncountable $\kappa$, then for any other uncountable cardinal $\lambda$, there is another forcing extension $V[H]$ where $H$ is $V$-generic for the forcing to add $\lambda$ many Cohen reals, yet $\R^{V[G]}=\R^{V[H]}$.

Proof. Start in $V[G]$, and let $g$ be $V[G]$-generic to collapse $\lambda$ to $\kappa$, using the collapse forcing of the ground model $V$. This forcing is countably closed in $V$ and therefore does not add reals over $V[G]$. In $V[g]$, the two forcing notions $\text{Add}(\omega,\kappa)$ and $\text{Add}(\omega,\lambda)$ are isomorphic. Thus, since $G$ is $V[g]$-generic for the former poset, it follows that the image $H=g\mathrel{“}G$ is $V[g]$-generic for the latter poset. So $V[H]$ is generic over $V$ for adding $\lambda$ many Cohen reals. By construction, we have $V[G][g]=V[H][g]$, and since $g$ doesn’t add reals, it follows that $\R^{V[G]}=\R^{V[H]}$, as desired. QED

I have a vague recollection of having first heard of this problem many years ago, perhaps as a graduate student, although I don’t quite recall where it was or indeed what the construction was — the argument above is my reconstruction (which I have updated and extended from my initial post). If someone could provide a reference in the comments for due credit, I’d be appreciative.  The problem appeared a few years ago on MathOverflow.

A program that accepts exactly any desired finite set, in the right universe

One_small_step_(3598325560)Last year I made a post about the universal program, a Turing machine program $p$ that can in principle compute any desired function, if it is only run inside a suitable model of set theory or arithmetic.  Specifically, there is a program $p$, such that for any function $f:\newcommand\N{\mathbb{N}}\N\to\N$, there is a model $M\models\text{PA}$ — or of $\text{ZFC}$, whatever theory you like — inside of which program $p$ on input $n$ gives output $f(n)$.

This theorem is related to a very interesting theorem of W. Hugh Woodin’s, which says that there is a program $e$ such that $\newcommand\PA{\text{PA}}\PA$ proves $e$ accepts only finitely many inputs, but such that for any finite set $A\subset\N$, there is a model of $\PA$ inside of which program $e$ accepts exactly the elements of $A$. Actually, Woodin’s theorem is a bit stronger than this in a way that I shall explain.

Victoria Gitman gave a very nice talk today on both of these theorems at the special session on Computability theory: Pushing the Boundaries at the AMS sectional meeting here in New York, which happens to be meeting right here in my east midtown neighborhood, a few blocks from my home.

What I realized this morning, while walking over to Vika’s talk, is that there is a very simple proof of the version of Woodin’s theorem stated above.  The idea is closely related to an idea of Vadim Kosoy mentioned in my post last year. In hindsight, I see now that this idea is also essentially present in Woodin’s proof of his theorem, and indeed, I find it probable that Woodin had actually begun with this idea and then modified it in order to get the stronger version of his result that I shall discuss below.

But in the meantime, let me present the simple argument, since I find it to be very clear and the result still very surprising.

Theorem. There is a Turing machine program $e$, such that

  1. $\PA$ proves that $e$ accepts only finitely many inputs.
  2. For any particular finite set $A\subset\N$, there is a model $M\models\PA$ such that inside $M$, the program $e$ accepts all and only the elements of $A$.
  3. Indeed, for any set $A\subset\N$, including infinite sets, there is a model $M\models\PA$ such that inside $M$, program $e$ accepts $n$ if and only if $n\in A$.

Proof.  The program $e$ simply performs the following task:  on any input $n$, search for a proof from $\PA$ of a statement of the form “program $e$ does not accept exactly the elements of $\{n_1,n_2,\ldots,n_k\}$.” Accept nothing until such a proof is found. For the first such proof that is found, accept $n$ if and only if $n$ is one of those $n_i$’s.

In short, the program $e$ searches for a proof that $e$ doesn’t accept exactly a certain finite set, and when such a proof is found, it accepts exactly the elements of this set anyway.

Clearly, $\PA$ proves that program $e$ accepts only a finite set, since either no such proof is ever found, in which case $e$ accepts nothing (and the empty set is finite), or else such a proof is found, in which case $e$ accepts only that particular finite set. So $\PA$ proves that $e$ accepts only finitely many inputs.

But meanwhile, assuming $\PA$ is consistent, then you cannot refute the assertion that program $e$ accepts exactly the elements of some particular finite set $A$, since if you could prove that from $\PA$, then program $e$ actually would accept exactly that set (for the shortest such proof), in which case this would also be provable, contradicting the consistency of $\PA$.

Since you cannot refute any particular finite set as the accepting set for $e$, it follows that it is consistent with $\PA$ that $e$ accepts any particular finite set $A$ that you like. So there is a model of $\PA$ in which $e$ accepts exactly the elements of $A$. This establishes statement (2).

Statement (3) now follows by a simple compactness argument. Namely, for any $A\subset\N$, let $T$ be the theory of $\PA$ together with the assertions that program $e$ accepts $n$, for any particular $n\in A$, and the assertions that program $e$ does not accept $n$, for $n\notin A$. Any finite subtheory of this theory is consistent, by statement (2), and so the whole theory is consistent. Any model of this theory realizes statement (3). QED

One uses the Kleene recursion theorem to show the existence of the program $e$, which makes reference to $e$ in the description of what it does. Although this may look circular, it is a standard technique to use the recursion theorem to eliminate the circularity.

This theorem immediately implies the classical result of Mostowski and Kripke that there is an independent family of $\Pi^0_1$ assertions, since the assertions $n\notin W_e$ are exactly such a family.

The theorem also implies a strengthening of the universal program theorem that I proved last year. Indeed, the two theorems can be realized with the same program!

Theorem. There is a Turing machine program $e$ with the following properties:

  1. $\PA$ proves that $e$ computes a finite function;
  2. For any particular finite partial function $f$ on $\N$, there is a model $M\models\PA$ inside of which program $e$ computes exactly $f$.
  3. For any partial function $f:\N\to\N$, finite or infinite, there is a model $M\models\PA$ inside of which program $e$ on input $n$ computes exactly $f(n)$, meaning that $e$ halts on $n$ if and only if $f(n)\downarrow$ and in this case $\varphi_e(n)=f(n)$.

Proof. The proof of statements (1) and (2) is just as in the earlier theorem. It is clear that $e$ computes a finite function, since either it computes the empty function, if no proof is found, or else it computes the finite function mentioned in the proof. And you cannot refute any particular finite function for $e$, since if you could, it would have exactly that behavior anyway, contradicting $\text{Con}(\PA)$. So statement (2) holds. But meanwhile, we can get statement (3) by a simple compactness argument. Namely, fix $f$ and let $T$ be the theory asserting $\PA$ plus all the assertions either that $\varphi_e(n)\uparrow$, if $n$ is not the domain of $f$, and $\varphi_e(n)=k$, if $f(n)=k$.  Every finite subtheory of this theory is consistent, by statement (2), and so the whole theory is consistent. But any model of this theory exactly fulfills statement (3). QED

Woodin’s proof is more difficult than the arguments I have presented, but I realize now that this extra difficulty is because he is proving an extremely interesting and stronger form of the theorem, as follows.

Theorem. (Woodin) There is a Turing machine program $e$ such that $\PA$ proves $e$ accepts at most a finite set, and for any finite set $A\subset\N$ there is a model $M\models\PA$ inside of which $e$ accepts exactly $A$. And furthermore, in any such $M$ and any finite $B\supset A$, there is an end-extension $M\subset_{end} N\models\PA$, such that in $N$, the program $e$ accepts exactly the elements of $B$.

This is a much more subtle claim, as well as philosophically interesting for the reasons that he dwells on.

The program I described above definitely does not achieve this stronger property, since my program $e$, once it finds the proof that $e$ does not accept exactly $A$, will accept exactly $A$, and this will continue to be true in all further end-extensions of the model, since that proof will continue to be the first one that is found.

Worldly cardinals are not always downwards absolute

 

UniversumI recently came to realize that worldly cardinals are not necessarily downward absolute to transitive inner models. That is, it can happen that a cardinal $\kappa$ is worldly in the full set-theoretic universe $V$, but not in some transitive inner model $W$, even when $W$ is itself a model of ZFC. The observation came out of some conversations I had with Alexander Block from Hamburg during his recent research visit to New York. Let me explain the argument.

A cardinal $\kappa$ is inaccessible, if it is an uncountable regular strong limit cardinal. The structure $V_\kappa$, consisting of the rank-initial segment of the set-theoretic universe up to $\kappa$, which can be generated from the empty set by applying the power set operation $\kappa$ many times, has many nice features. In particular, it is transitive model of $\newcommand\ZFC{\text{ZFC}}\ZFC$. The models $V_\kappa$ for $\kappa$ inaccessible are precisely the uncountable Grothendieck universes used in category theory.

Although the inaccessible cardinals are often viewed as the entryway to the large cardinal hierarchy, there is a useful large cardinal concept weaker than inaccessibility. Namely, a cardinal $\kappa$ is worldly, if $V_\kappa$ is a model of $\ZFC$. Every inaccessible cardinal is worldly, and in fact a limit of worldly cardinals, because if $\kappa$ is inaccessible, then there is an elementary chain of cardinals $\lambda<\kappa$ with $V_\lambda\prec V_\kappa$, and all such $\lambda$ are worldly. The regular worldly cardinals are precisely the inaccessible cardinals, but the least worldly cardinal is always singular of cofinality $\omega$.

The worldly cardinals can be seen as a kind of poor-man’s inaccessible cardinal, in that worldliness often suffices in place of inaccessibility in many arguments, and this sometimes allows one to weaken a large cardinal hypothesis. But meanwhile, they do have some significant strengths. For example, if $\kappa$ is worldly, then $V_\kappa$ satisfies the principle that every set is an element of a transitive model of $\ZFC$.

It is easy to see that inaccessibility is downward absolute, in the sense that if $\kappa$ is inaccessible in the full set-theoretic universe $V$ and $W\newcommand\of{\subseteq}\of V$ is a transitive inner model of $\ZFC$, then $\kappa$ is also inaccessible in $W$. The reason is that $\kappa$ cannot be singular in $W$, since any short cofinal sequence in $W$ would still exist in $V$; and it cannot fail to be a strong limit there, since if some $\delta<\kappa$ had $\kappa$-many distinct subsets in $W$, then this injection would still exist in $V$. So inaccessibility is downward absolute.

The various degrees of hyper-inaccessibility are also downwards absolute to inner models, so that if $\kappa$ is an inaccessible limit of inaccessible limits of inaccessible cardinals, for example, then this is also true in any inner model. This downward absoluteness extends all the way through the hyperinaccessibility hierarchy and up to the Mahlo cardinals and beyond. A cardinal $\kappa$ is Mahlo, if it is a strong limit and the regular cardinals below $\kappa$ form a stationary set. We have observed that being regular is downward absolute, and it is easy to see that every stationary set $S$ is stationary in every inner model, since otherwise there would be a club set $C$ disjoint from $S$ in the inner model, and this club would still be a club in $V$. Similarly, the various levels of hyper-Mahloness are also downward absolute.

So these smallish large cardinals are generally downward absolute. How about the worldly cardinals? Well, we can prove first off that worldliness is downward absolute to the constructible universe $L$.

Observation. If $\kappa$ is worldly, then it is worldly in $L$.

Proof. If $\kappa$ is worldly, then $V_\kappa\models\ZFC$. This implies that $\kappa$ is a beth-fixed point. The $L$ of $V_\kappa$, which is a model of $\ZFC$, is precisely $L_\kappa$, which is also the $V_\kappa$ of $L$, since $\kappa$ must also be a beth-fixed point in $L$. So $\kappa$ is worldly in $L$. QED

But meanwhile, in the general case, worldliness is not downward absolute.

Theorem. Worldliness is not necessarily downward absolute to all inner models. It is relatively consistent with $\ZFC$ that there is a worldly cardinal $\kappa$ and an inner model $W\of V$, such that $\kappa$ is not worldly in $W$.

Proof. Suppose that $\kappa$ is a singular worldly cardinal in $V$. And by forcing if necessary, let us assume the GCH holds in $V$. Let $V[G]$ be the forcing extension where we perform the Easton product forcing $\newcommand\P{\mathbb{P}}\P$, so as to force a violation of the GCH at every regular cardinal $\gamma$. So the stage $\gamma$ forcing is $\newcommand\Q{\mathbb{Q}}\Q_\gamma=\text{Add}(\gamma,\gamma^{++})$.

First, I shall prove that $\kappa$ is worldly in the forcing extension $V[G]$. Since every set of rank less than $\kappa$ is added by some stage less than $\kappa$, it follows that $V_\kappa^{V[G]}$ is precisely $\bigcup_{\gamma<\kappa} V_\kappa[G_\gamma]$. Most of the $\ZFC$ axioms hold easily in $V_\kappa^{V[G]}$; the only difficult case is the collection axiom. And for this, by considering the ranks of witnesses, it suffices to show for every $\gamma<\kappa$ that every function $f:\gamma\to\kappa$ that is definable from parameters in $V_\kappa^{V[G]}$ is bounded. Suppose we have such a function, defined by $f(\alpha)=\beta$ just in case $\varphi(\alpha,\beta,p)$ holds in $V_\kappa^{V[G]}$. Let $\delta<\kappa$ be larger than the rank of $p$. Now consider $V_\kappa[G_\delta]$, which is a set-forcing extension of $V_\kappa$ and therefore a model of $\ZFC$. The fail forcing, from stage $\delta$ up to $\kappa$, is homogeneous in this model. And therefore we know that $f(\alpha)=\beta$ just in case $1$ forces $\varphi(\check\alpha,\check\beta,\check p)$, since these arguments are all in the ground model $V_\kappa[G_\delta]$. So the function is already definable in $V_\kappa[G_\delta]$. Because this is a model of $\ZFC$, the function $f$ is bounded below $\kappa$. So we get the collection axiom in $V_\kappa^{V[G]}$ and hence all of $\ZFC$ there, and so $\kappa$ is worldly in $V[G]$.

For any $A\of\kappa$, let $\P_A$ be the restriction of the Easton product forcing to include only the stages in $A$, and let $G_A$ be the corresponding generic filter. The full forcing $\P$ factors as $\P_A\times\P_{\kappa\setminus A}$, and so $V[G_A]\of V[G]$ is a transitive inner model of $\ZFC$.

But if we pick $A\of\kappa$ to be a short cofinal set in $\kappa$, which is possible because $\kappa$ is singular, then $\kappa$ will not be worldly in the inner model $V[G_A]$, since in $V_\kappa[G_A]$ we will be able to identify that sequence as the places where the GCH fails. So $\kappa$ is not worldly in $V[G_A]$.

In summary, $\kappa$ was worldly in $V[G]$, but not in the transitive inner model $W=V[G_A]$, and so worldliness is not downward absolute. QED

The inclusion relations of the countable models of set theory are all isomorphic

  • J. D. Hamkins and M. Kikuchi, “The inclusion relations of the countable models of set theory are all isomorphic.” (manuscript under review)  
    @ARTICLE{HamkinsKikuchi:The-inclusion-relations-of-the-countable-models-of-set-theory-are-all-isomorphic,
    author = {Joel David Hamkins and Makoto Kikuchi},
    title = {The inclusion relations of the countable models of set theory are all isomorphic},
    journal = {},
    editor = {},
    year = {},
    volume = {},
    number = {},
    pages = {},
    month = {},
    doi = {},
    note = {manuscript under review},
    eprint = {1704.04480},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/inclusion-relations-are-all-isomorphic},
    abstract = {},
    keywords = {},
    source = {},
    }

mereology type

Abstract. The structures $\langle M,\newcommand\of{\subseteq}\of^M\rangle$ arising as the inclusion relation of a countable model of sufficient set theory $\langle M,\in^M\rangle$, whether well-founded or not, are all isomorphic. These structures $\langle M,\of^M\rangle$ are exactly the countable saturated models of the theory of set-theoretic mereology: an unbounded atomic relatively complemented distributive lattice. A very weak set theory suffices, even finite set theory, provided that one excludes the $\omega$-standard models with no infinite sets and the $\omega$-standard models of set theory with an amorphous set. Analogous results hold also for class theories such as Gödel-Bernays set theory and Kelley-Morse set theory.

Set-theoretic mereology is the study of the inclusion relation $\of$ as it arises within set theory. In any set-theoretic context, with the set membership relation $\in$, one may define the corresponding inclusion relation $\of$ and investigate its properties. Thus, every model of set theory $\langle M,\in^M\rangle$ gives rise to a corresponding model of set-theoretic mereology $\langle M,\of^M\rangle$, the reduct to the inclusion relation.

In our previous article,

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. 1-24, 2016.

we had identified exactly the complete theory of these mereological structures $\langle M,\of^M\rangle$. Namely, if $\langle M,\in^M\rangle$ is a model of set theory, even for extremely weak theories, including set theory without the infinity axiom, then the corresponding mereological reduct $\langle M,\of^M\rangle$ is an unbounded atomic relatively complemented distributive lattice. We call this the theory of set-theoretic mereology. By a quantifier-elimination argument that we give in our earlier paper, partaking of Tarski’s Boolean-algebra invariants and Ersov’s work on lattices, this theory is complete, finitely axiomatizable and decidable.  We had proved among other things that $\in$ is never definable from $\of$ in any model of set theory and furthermore, some models of set-theoretic mereology can arise as the inclusion relation of diverse models of set theory, with different theories. Furthermore, we proved that $\langle\text{HF},\subseteq\rangle\prec\langle V,\subseteq\rangle$.

After that work, we found it natural to inquire:

Question. Which models of set-theoretic mereology arise as the inclusion relation $\of$ of a model of set theory?

More precisely, given a model $\langle M,\newcommand\sqof{\sqsubseteq}\sqof\rangle$ of set-theoretic mereology, under what circumstances can we place a binary relation $\in^M$ on $M$ in such a way that $\langle M,\in^M\rangle$ is a model of set theory and the inclusion relation $\of$ defined in $\langle M,\in^M\rangle$ is precisely the given relation $\sqof$? One can view this question as seeking a kind of Stone-style representation of the mereological structure $\langle M,\sqof\rangle$, because such a model $M$ would provide a representation of $\langle M,\sqof\rangle$ as a relative field of sets via the model of set theory $\langle M,\in^M\rangle$.

A second natural question was to wonder how much of the theory of the original model of set theory can be recovered from the mereological reduct.

Question. If $\langle M,\of^M\rangle$ is the model of set-theoretic mereology arising as the inclusion relation $\of$ of a model of set theory $\langle M,\in^M\rangle$, what part of the theory of $\langle M,\in^M\rangle$ is determined by the structure $\langle M,\of^M\rangle$?

In the case of the countable models of ZFC, these questions are completely answered by our main theorems.

Main Theorems.

  1. All countable models of set theory $\langle M,\in^M\rangle\models\text{ZFC}$ have isomorphic reducts $\langle M,\of^M\rangle$ to the inclusion relation.
  2. The same holds for models of considerably weaker theories such as KP and even finite set theory, provided one excludes the $\omega$-standard models without infinite sets and the $\omega$-standard models having an amorphous set.
  3. These inclusion reducts $\langle M,\of^M\rangle$ are precisely the countable saturated models of set-theoretic mereology.
  4. Similar results hold for class theory: all countable models of Gödel-Bernays set theory have isomorphic reducts to the inclusion relation, and this reduct is precisely the countably infinite saturated atomic Boolean algebra.

Specifically, we show that the mereological reducts $\langle M,\of^M\rangle$ of the models of sufficient set theory are always $\omega$-saturated, and from this it follows on general model-theoretic grounds that they are all isomorphic, establishing statements (1) and (2). So a countable model $\langle M,\sqof\rangle$ of set-theoretic mereology arises as the inclusion relation of a model of sufficient set theory if and only if it is $\omega$-saturated, establishing (3) and answering the first question. Consequently, in addition, the mereological reducts $\langle M,\of^M\rangle$ of the countable models of sufficient set theory know essentially nothing of the theory of the structure $\langle M,\in^M\rangle$ from which they arose, since $\langle M,\of^M\rangle$ arises equally as the inclusion relation of other models $\langle M,\in^*\rangle$ with any desired sufficient alternative set theory, a fact which answers the second question. Our analysis works with very weak set theories, even finite set theory, provided one excludes the $\omega$-standard models with no infinite sets and the $\omega$-standard models with an amorphous set, since the inclusion reducts of these models are not $\omega$-saturated. We also prove that most of these results do not generalize to uncountable models, nor even to the $\omega_1$-like models.

Our results have some affinity with the classical results in models of arithmetic concerned with the additive reducts of models of PA. Restricting a model of set theory to the inclusion relation $\of$ is, after all, something like restricting a model of arithmetic to its additive part. Lipshitz and Nadel (1978) proved that a countable model of Presburger arithmetic (with $+$ only) can be expanded to a model of PA if and only if it is computably saturated. We had hoped at first to prove a corresponding result for the mereological reducts of the models of set theory. In arithmetic, the additive reducts are not all isomorphic, since the standard system of the PA model is fully captured by the additive reduct. Our main result for the countable models of set theory, however, turned out to be stronger than we had expected, since the inclusion reducts are not merely computably saturated, but fully $\omega$-saturated, and this is why they are all isomorphic. Meanwhile, Lipshitz and Nadel point out that their result does not generalize to uncountable models of arithmetic, and similarly ours also does not generalize to uncountable models of set theory.

The work leaves the following question open:

Question. Are the mereological reducts $\langle M,\of^M\rangle$ of all the countable models $\langle M,\in^M\rangle$ of ZF with an amorphous set all isomorphic?

We expect the answer to come from a deeper understanding of the Tarski-Ersov invariants for the mereological structures combined with knowledge of models of ZF with amorphous sets.

This is joint work with Makoto Kikuchi.

All countable models of set theory have the same inclusion relation up to isomorphism, CUNY Logic Workshop, April 2017

This will be a talk for the CUNY Logic Workshop, April 28, 2:00-3:30 in room 6417 at the CUNY Graduate Center.

mereology type

Abstract.  Take any countable model of set theory $\langle M,\in^M\rangle\models\text{ZFC}$, whether well-founded or not, and consider the corresponding inclusion relation $\langle M,\newcommand\of{\subseteq}\of^M\rangle$.  All such models, we prove, are isomorphic. Indeed, if $\langle M,\in^M\rangle$ is a countable model of set theory — a very weak theory suffices, including finite set theory, if one excludes the $\omega$-standard models with no infinite sets and the $\omega$-standard models with an amorphous set — then the corresponding inclusion reduct $\langle M,\of^M\rangle$ is an $\omega$-saturated model of the theory we have called set-theoretic mereology. Since this is a complete theory, it follows by the back-and-forth construction that all such countable saturated models are isomorphic. Thus, the inclusion relation $\langle M,\of^M\rangle$ knows essentially nothing about the theory of the set-theoretic structure $\langle M,\in^M\rangle$ from which it arose. Analogous results hold also for class theories such as Gödel-Bernays set theory and Kelley-Morse set theory.

This is joint work with Makoto Kikuchi, and our paper is available at

J. D. Hamkins and M. Kikuchi, The inclusion relations of the countable models of set theory are all isomorphic, manuscript under review.

Our previous work, upon which these results build, is available at:

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. 1-24, 2016.

The definable cut of a model of set theory can be changed by small forcing

Cupid carving his bow -- ParmigianinoIf $M$ is a model of ZFC set theory, let $I$ be the definable cut of its ordinals, the collection of ordinals that are below an ordinal $\delta$ of $M$ that is definable in $M$ without parameters. This would include all the ordinals of $M$, if the definable ordinals happen to be unbounded in $M$, but one can also construct examples where the definable cut is bounded in $M$.  Let $M_I$ be the corresponding definable cut of $M$ itself, the rank-initial segment of $M$ determined by $I$, or in other words, the collection of all sets $x$ in $M$ of rank below a definable ordinal of $M$. Equivalently, $$M_I=\bigcup_{\delta\in I} V_\delta^M.$$ It is not difficult to see that this is an elementary substructure $M_I\prec M$, because we can verify the Tarski-Vaught criterion as follows. If $M\models\exists y\ \varphi(x,y)$, where $x\in M_I$, then let $\delta$ be a definable ordinal above the rank of $x$. In this case, the ordinal $\theta$, which is the supremum over all $a\in V_\delta$ of the minimal rank of a set $y$ for which $\varphi(a,y)$, if there is such a $y$. This supremum $\theta$ is definable, and so since $x\in V_\delta$, the minimal rank of a $y$ such that $\varphi(x,y)$ is at most $\theta$. Consequently, since $\theta\in I$, such a $y$ can be found in $M_I$. So we have found the desired witness inside the substructure, and so it is elementary $M_I\prec M$. Note that in the general case, one does not necessarily know that $I$ has a least upper bound in $M$. Under suitable assumptions, it can happen that $I$ is unbounded in $M$, that $I$ is an ordinal of $M$, or that $I$ is bounded in $M$, but has no least upper bound.

What I am interested in for this post is how the definable cut might be affected by forcing. Of course, it is easy to see that if $M$ is definable in $M[G]$, then the definable cut of $M[G]$ is at least as high as the definable cut of $M$, simply because the definable ordinals of $M$ remain definable in $M[G]$.

A second easy observation is that if the definable cut of $M$ is bounded in $M$, then we could perform large collapse forcing, collapsing a cardinal above $I$ to $\omega$, which would of course make every cardinal of $I$ countable in the extension $M[G]$. In this case, since $\omega_1^{M[G]}$ is definable, it would change the definable cut. So this kind of very large forcing can change the definable cut, making it larger.

But what about small forcing? Suppose that the forcing notion $\newcommand\P{\mathbb{P}}\P$ we intend to forcing with is small in the sense that it is in the definable cut $M_I$. This would be true if $\P$ itself were definable, for example, but really we only require that $\P$ has rank less than some definable ordinal of $M$. Can this forcing change the definable cut?

Let me show at least that the definable cut can never go up after small forcing.

Theorem. If $G\subset\P$ is $M$-generic for forcing $\P$ in the definable cut of $M$, then the definable cut of $M[G]$ is below or the same in the ordinals as it was in $M$.

Proof. Suppose that $G\subset\P$ is $M$-generic, and we consider the forcing extension $M[G]$. We have already proved that $M_I\prec M$ is an elementary submodel. I claim that this relation lifts to the forcing extension $M_I[G]\prec M[G]$. Note first that since $\P\in M_I$ and $M_I$ is a rank initial segment of $M$, it follows that $M_I$ has all the subsets of $\P$ in $M$, and so $G$ is $M_I$-generic. So the extension $M_I[G]$ makes sense. Next, suppose that $M[G]\models\varphi(a)$ for some $a\in M_I[G]$. If $\dot a$ is a name for $a$ in $M_I$, then there is some condition $p\in G$ forcing $\varphi(\dot a)$ over $M$. Since $M_I\prec M$, this is also forced by $p$ over $M_I$, and thus $M_I[G]\models\varphi(a)$ as well, as desired. So $M_I[G]\prec M[G]$, and from this it follows that every definable ordinal of $M[G]$ is in the cut $I$. So the definable cut did not get higher. QED

But can it go down? Not if the model $M$ is definable in $M[G]$, by our earlier easy observation. Consequently,

Theorem. If $M$ is definable in $M[G]$, where $G\subset\P$ is $M$-generic for forcing $\P$ below the definable cut of $M$, then the definable cut of $M[G]$ is the same as the definable cut of $M$.

Proof. It didn’t go down, since $M$ is definable in $M[G]$; and it didn’t go up, since $\P$ was small. QED

What if $M$ is not definable in $M[G]$? Can we make the definable cut go down after small forcing? The answer is yes.

Theorem. If ZFC is consistent, then there is a model $M\models\text{ZFC}$ with a definable notion of forcing $\P$ (hence in the definable cut of $M$), such that if $G\subset\P$ is $M$-generic, then the definable cut of the forcing extension $M[G]$ is strictly shorter than the definable cut of $M[G]$.

Proof. Start with a model of $\text{ZFC}+V=L$, whose definable ordinals are bounded by a cardinal $\delta$. Let’s call it $L$, and let $I$ be the definable cut of $L$, which we assume is bounded by $\delta$. Let $M=L[G]$ be the forcing extension of $L$ obtained by performing an Easton product, adding a Cohen subset to every regular cardinal above $\delta$ in $L$. Since this forcing adds no sets below $\delta$, but adds a Cohen set at $\delta^+$, it follows that $\delta$ becomes definable in $L[G]$. In fact, since the forcing is homogeneous and definable from $\delta$, it follows that the definable ordinals of $L[G]$ are precisely the ordinals that are definable in $L$ with parameter $\delta$. These may be bounded or unbounded in $L[G]$. Now, let $\newcommand\Q{\mathbb{Q}}\Q$ be the Easton product forcing at the stages below $\delta$, and suppose that $G\subset\Q$ is $L[G]$-generic. Consider the model $L[G][H]$. Note that the forcing $\Q$ is definable in $L[G]$, since $\delta$ is definable there. This two-step forcing can be combined into one giant Easton product in $L$, the product that simply forces to add a Cohen subset to every regular cardinal. Since this version of the forcing is homogeneous and definable in $L$, it follows that the definable ordinals of $L[G][H]$ are precisely the definable ordinals of $L$, which are bounded by $I$. In summary, the definable cut of $L[G]$ is strictly above $\delta$, since $\delta$ is definable in $L[G]$, and the forcing $\Q$ has size and rank $\delta$; but the forcing extension $L[G][H]$ has definable cut $I$, which is strictly bounded by $\delta$. So the definable cut was made smaller by small forcing, as claimed. QED

This post is an account of some ideas that Alexander Block and I had noted today during the course of our mathematical investigation of another matter.

Games with the computable-play paradox

The_Chess_Game_-_Sofonisba_AnguissolaLet me tell you about a fascinating paradox arising in certain infinitary two-player games of perfect information. The paradox, namely, is that there are games for which our judgement of who has a winning strategy or not depends on whether we insist that the players play according to a deterministic computable procedure. In the the space of computable play for these games, one player has a winning strategy, but in the full space of all legal play, the other player can ensure a win.

The fundamental theorem of finite games, proved in 1913 by Zermelo, is the assertion that in every finite two-player game of perfect information — finite in the sense that every play of the game ends in finitely many moves — one of the players has a winning strategy. This is generalized to the case of open games, games where every win for one of the players occurs at a finite stage, by the Gale-Stewart theorem 1953, which asserts that in every open game, one of the players has a winning strategy. Both of these theorems are easily adapted to the case of games with draws, where the conclusion is that one of the players has a winning strategy or both players have draw-or-better strategies.

Let us consider games with a computable game tree, so that we can compute whether or not a move is legal. Let us say that such a game is computably paradoxical, if our judgement of who has a winning strategy depends on whether we restrict to computable play or not. So for example, perhaps one player has a winning strategy in the space of all legal play, but the other player has a computable strategy defeating all computable strategies of the opponent. Or perhaps one player has a draw-or-better strategy in the space of all play, but the other player has a computable strategy defeating computable play.

Examples of paradoxical games occur in infinite chess. We described such a paradoxical position in my paper Transfinite games values in infinite chess by giving a computable infinite chess position with the property that both players had drawing strategies in the space of all possible legal play, but in the space of computable play, then white had a computable strategy defeating any particular computable strategy for black.

For a related non-chess example, let $T$ be a computable subtree of $2^{<\omega}$ having no computable infinite branch, and consider the game in which black simply climbs in this tree as white watches, with black losing whenever he is trapped in a terminal node, but winning if he should climb infinitely. This game is open for white, since if white wins, this is known at a finite stage of play. In the space of all possible play, Black has a winning strategy, which is simply to climb the tree along an infinite branch, which exists by König’s lemma. But there is no computable strategy to find such a branch, by the assumption on the tree, and so when black plays computably, white will inevitably win.

For another example, suppose that we have a computable linear order $\lhd$ on the natural numbers $\newcommand\N{\mathbb{N}}\N$, which is not a well order, but which has no computable infinite descending sequence. It is a nice exercise in computable model theory to show that such an order exists. If we play the count-down game in this order, with white trying to build a descending sequence and black watching. In the space of all play, white can succeed and therefore has a winning strategy, but since there is no computable descending sequence, white can have no computable winning strategy, and so black will win every computable play.

There are several proofs of open determinacy (and see my MathOverflow post outlining four different proofs of the fundamental theorem of finite games), but one of my favorite proofs of open determinacy uses the concept of transfinite game values, assigning an ordinal to some of the positions in the game tree. Suppose we have an open game between Alice and Bob, where the game is open for Alice. The ordinal values we define for positions in the game tree will measure in a sense the distance Alice is away from winning. Namely, her already-won positions have value $0$, and if it is Alice’s turn to play from a position $p$, then the value of $p$ is $\alpha+1$, if $\alpha$ is minimal such that she can play to a position of value $\alpha$; if it is Bob’s turn to play from $p$, and all the positions to which he can play have value, then the value of $p$ is the supremum of these values. Some positions may be left without value, and we can think of those positions as having value $\infty$, larger than any ordinal. The thing to notice is that if a position has a value, then Alice can always make it go down, and Bob cannot make it go up. So the value-reducing strategy is a winning strategy for Alice, from any position with value, while the value-maintaining strategy is winning for Bob, from any position without a value (maintaining value $\infty$). So the game is determined, depending on whether the initial position has value or not.

What is the computable analogue of the ordinal-game-value analysis in the computably paradoxical games? If a game is open for Alice and she has a computable strategy defeating all computable opposing strategies for Bob, but Bob has a non-computable winning strategy, then it cannot be that we can somehow assign computable ordinals to the positions for Alice and have her play the value-reducing strategy, since if those values were actual ordinals, then this would be a full honest winning strategy, even against non-computable play.

Nevertheless, I claim that the ordinal-game-value analysis does admit a computable analogue, in the following theorem. This came out of a discussion I had recently with Noah Schweber during his recent visit to the CUNY Graduate Center and Russell Miller. Let us define that a computable open game is an open game whose game tree is computable, so that we can tell whether a given move is legal from a given position (this is a bit weaker than being able to compute the entire set of possible moves from a position, even when this is finite). And let us define that an effective ordinal is a computable relation $\lhd$ on $\N$, for which there is no computable infinite descending sequence. Every computable ordinal is also an effective ordinal, but as we mentioned earlier, there are non-well-ordered effective ordinals. Let us call them computable pseudo-ordinals.

Theorem. The following are equivalent for any computable game, open for White.

  1. White has a computable strategy defeating any computable play by Black.
  2. There is an effective game-value assignment for white into an effective ordinal $\lhd$, giving the initial position a value. That is, there is a computable assignment of some positions of the game, including the first position, to values in the field of $\lhd$, such that from any valued position with White to play, she can play so as to reduce value, and with Black to play, he cannot increase the value.

Proof. ($2\to 1$) Given the computable values into an effective ordinal, then the value-reducing strategy for White is a computable strategy. If Black plays computably, then together they compute a descending sequence in the $\lhd$ order. Since there is no computable infinite descending sequence, it must be that the values hit zero and the game ends with a win for White. So White has a computable strategy defeating any computable play by Black.

($1\to 2$) Conversely, suppose that White has a computable strategy $\sigma$ defeating any computable play by Black. Let $\tau$ be the subtree of the game tree arising by insisting that White follow the strategy $\sigma$, and view this as a tree on $\N$, a subtree of $\N^{<\omega}$. Imagine the tree growing downwards, and let $\lhd$ be the Kleene-Brouwer order on this tree, which is the lexical order on incompatible positions, and otherwise longer positions are lower. This is a computable linear order on the tree. Since $\sigma$ is computably winning for White, the open player, it follows that every computable descending sequence in $\tau$ eventually reaches a terminal node. From this, it follows that there is no computable infinite descending sequence with respect to $\lhd$, and so this is an effective ordinal. We may now map every node in $\tau$, which includes the initial node, to itself in the $\lhd$ order. This is a game-value assignment, since on White’s turn, the value goes down, and it doesn’t go up on Black’s turn. QED

Corollary. A computable open game is computably paradoxical if and only if it admits an effective game value assignment for the open player, but only with computable pseudo-ordinals and not with computable ordinals.

Proof. If there is an effective game value assignment for the open player, then the value-reducing strategy arising from that assignment is a computable strategy defeating any computable strategy for the opponent. Conversely, if the game is paradoxical, there can be no such ordinal-assignment where the values are actually well-ordered, or else that strategy would work against all play by the opponent. QED

Let me make a few additional observations about these paradoxical games.

Theorem. In any open game, if the closed player has a strategy defeating all computable opposing strategies, then in fact this is a winning strategy also against non-computable play.

Proof. If the closed player has a strategy $\sigma$ defeating all computable strategies of the opponent, then in fact it defeats all strategies of the opponent, since any winning play by the open player against $\sigma$ wins in finitely many moves, and therefore there is a computable strategy giving rise to the same play. QED

Corollary. If an open game is computably paradoxical, it must be the open player who wins in the space of computable play and the closed player who wins in the space of all play.

Proof. The theorem shows that if the closed player wins in the space of computable play, then that player in fact wins in the space of all play. QED

Corollary. There are no computably paradoxical clopen games.

Proof. If the game is clopen, then both players are closed, but we just argued that any computable strategy for a closed player winning against all computable play is also winning against all play. QED

Buckets of fish!

Let me tell you about the game Buckets of fishReef_shark_beneath_a_school_of_jack_fish 4096

This is a two-player game played with finitely many buckets in a line on the beach, each containing a finite number of fish. There is also a large supply of additional fish available nearby, fresh off the boats.

Taking turns, each player selects a bucket and removes exactly one fish from it and then, if desired, adds any finite number of fish from the nearby supply to the buckets to the left.

For example, if we label the buckets from the left as 1, 2, 3 and so on, then a legal move would be to take one fish from bucket 4 and then add ten fish to bucket 1, no fish to bucket 2, and ninety-four fish to bucket 3. The winner is whoever takes the very last fish from the buckets, leaving them empty.

Since huge numbers of fish can often be added to the buckets during play, thereby prolonging the length of play, a skeptical reader may wonder whether the game will necessarily come to an end. Perhaps the players can prolong the game indefinitely? Or must it always come to an end?

Question. Does every play of the game Buckets of fish necessarily come to an end?

The answer is yes, every game must eventually come to a completion. I shall give several arguments.

Theorem. Every play of the game Buckets of fish ends in finitely many moves. All the fish in the buckets, including all the new fish that may have been added during play, will eventually run out by some finite stage during play.

That is, no matter how the players add fish to the buckets during play, even with an endless supply of fish from the boats, they will eventually run out of fish in the buckets and one of the players will take the last fish.

First proof. We prove the claim by (nested) induction on the number of buckets. If there is only one bucket, then there are no buckets to the left of it, and so there is no possibility in this case to add fish to the game. If the one bucket contains $k$ fish, then the game clearly ends in $k$ moves. Assume by induction that all plays using $n$ buckets end in finitely many moves, and suppose that we have a game situation with $n+1$ buckets, with $k$ fish in bucket $n+1$. We now prove by induction on $k$ that all such games terminate. This argument is therefore an instance of nested induction, since we are currently inside our proof by induction on $n$, in the induction step of that proof, and in order to complete it, we are undertaking a separate full induction on $k$. If $k=0$, then there are no fish in bucket $n+1$, and so the game amounts really to a game with only $n$ buckets, which terminates in finitely many steps by our induction hypothesis on $n$. So, let us assume that all plays with $k$ fish in bucket $n+1$ terminate in finitely many moves. Consider a situation where there are $k+1$ many fish in that bucket. I claim that eventually, one of those fish must be taken, since otherwise all the moves will be only on the first $n$ buckets, and all plays on only $n$ buckets terminate in finitely many moves. So at some point, one of the players will take a fish from bucket $n+1$, possibly adding additional fish to the earlier buckets. But this produces a situation with only $k$ fish in bucket $n+1$, which by our induction assumption on $k$ we know will terminate in finitely many steps. So we have proved that no matter how many fish are in bucket $n+1$, the game will end in finitely many moves, and so the original claim is true for $n+1$ buckets. Thus, the theorem is true for any finite number of buckets. QED

A second proof. Let me now give another proof, following an idea arising in a conversation with Miha Habič. We want to prove that there is no infinitely long play of the game Buckets of fish. Suppose toward contradiction that there is a way for the players to conspire to produce an infinite play, starting from some configuration of some finite number $n$ of buckets, each with finitely many fish in them. Fix the particular infinitely long play. Let $m$ be the right-most bucket from which a fish was taken infinitely often during that infinite course of play. It follows, for example, that $m<n$, since the top bucket can be used only finitely often, as it never gets replenished. Since bucket $m$ starts with only finitely many fish in it, and each time it is replenished, it is replenished with only finitely many fish, it follows that in order to have been used infinitely many times, it must also have been replenished infinitely often. But each time it was replenished, it was because there was some bucket further to the right that had been used. Since there are only finitely many buckets to the right of bucket $m$, it follows that one of them must have been used infinitely often. This contradicts the choice of $m$ as the right-most bucket that was used infinitely often. QED

A third proof. Let me now give a third proof, using ordinals. We shall associate with each Buckets-of-fish position a certain ordinal. With the position $$7\quad 2\quad 5\quad 24,$$ for example, we associate the ordinal $$\omega^3\cdot 24+\omega^2\cdot 5+\omega\cdot 2+7.$$ More generally, the number of fish in each bucket of a position becomes the coefficient of the corresponding power of $\omega$, using higher powers for the buckets further to the right. The key observation to make is that these associated ordinals strictly descend for every move of the game, since one is reducing a higher-power coefficient and increasing only lower-power coefficients. Since there is no infinite descending sequence of ordinals, it follows that there is no infinite play in the game Buckets of fish. This idea also shows that the ordinal game values of positions in this game are bounded above by $\omega^\omega$, and every ordinal less than $\omega^\omega$ is realized by some position. QED

OK, fine, so now we know that the game always ends. But how shall we play? What is the winning strategy? Say you are faced with buckets having fish in the amounts: $$4\quad 5\quad 2\quad 0\quad 7\quad 4$$ What is your winning move? Please give it some thought before reading further.

 

 

 

The winning strategy turns out to be simpler than you might have expected.

Theorem. The winning strategy in the game Buckets of fish is to play so as to ensure that every bucket has an even number of fish.

Proof. Notice first, as a warm-up, that in the case that there is only one bucket containing an even number of fish, then the second player will win, since the first player will necessarily make it odd, and then the second player will make it even again, and so on. So it will be the second player who will make it zero, winning the game. So with one bucket, the player who can make the bucket even will be the winner.

Next, notice that if you play so as to give your opponent an even number of fish in every bucket, then whatever move your opponent makes will result in an odd number of fish in the bucket from which he or she takes a fish (and possibly also an odd number of fish in some of the earlier buckets as well, if they happen to add an odd number of fish to some of them). So if you give your opponent an all-even position, then they cannot give you back an all-even position.

Finally, notice that if you are faced with a position that is not all-even, then you can simply take a fish from the right-most odd bucket, thereby making it even, and add fish if necessary to the earlier buckets so as to make them all even. In this way, you can turn any position that is not all-even into an all-even position in one move.

By following this strategy, a player will ensure that he or she will take the last fish, since the winning move is to make the all-zero position, which is an all-even position, and the opponent cannot produce an all-even position. QED

In the particular position of the game mentioned before the theorem, therefore, the winning move is to take a fish from the bucket with 7 fish and add an odd number of fish to the bucket with 5 fish, thereby producing an all-even position.

Finally, let’s consider a few variations of the game. It is clear that the all-even strategy works in the versions of the game where one is limited to add at most one fish to each of the earlier buckets, and this version of the game is actually playable, since the number of fish does not grow too much. A similar variation arises where one can either or add or remove any number of fish (or just at most one) from any of the earlier buckets, or where one can, say, add either 5 or 6 fish only to each of the earlier buckets. What is important in the argument is simply that one should be able to ensure the all-even nature of the buckets.

For a more interesting variation, consider what I call the Take 3 version of the game, where one can take either one, two or three fish from any bucket and then add any number of fish to the earlier buckets. The game must still eventually end, but what is the winning strategy?

Question. What is your strategy in the Take 3 variation of Buckets of fish?

Please post your answers in the comments, and I’ll post an answer later. One can generalize this to the Take $n$ variation, where on each turn, the player is allowed to take between 1 and $n$ fish from any bucket, and add as many fish as desired to the earlier buckets.

Another puzzling variation is where each player can take any number of fish from a bucket, and then add any number of fish to earlier buckets. Can you find a strategy for this version of the game? Please post in the comments.

Computable quotient presentations of models of arithmetic and set theory

  • M. T. Godziszewski and J. D. Hamkins, “Computable quotient presentations of models of arithmetic and set theory.”  
    @ARTICLE{GodziszewskiHamkins:Computable-quotient-presentations-of-models-of-arithmetic-and-set-theory,
    author = {Michał Tomasz Godziszewski and Joel David Hamkins},
    title = {Computable quotient presentations of models of arithmetic and set theory},
    journal = {},
    year = {},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {},
    abstract = {},
    keywords = {},
    source = {},
    doi = {},
    eprint = {1702.08350},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/computable-quotient-presentations-of-models-of-arithmetic-and-set-theory},
    }

Abstract. We prove various extensions of the Tennenbaum phenomenon to the case of computable quotient presentations of models of arithmetic and set theory. Specifically, no nonstandard model of arithmetic has a computable quotient presentation by a c.e. equivalence relation. No $\Sigma_1$-sound nonstandard model of arithmetic has a computable quotient presentation by a co-c.e. equivalence relation. No nonstandard model of arithmetic in the language $\{+,\cdot,\leq\}$ has a computably enumerable quotient presentation by any equivalence relation of any complexity. No model of ZFC or even much weaker set theories has a computable quotient presentation by any equivalence relation of any complexity. And similarly no nonstandard model of finite set theory has a computable quotient presentation. 

A computable quotient presentation of a mathematical structure $\mathcal A$ consists of a computable structure on the natural numbers $\langle\newcommand\N{\mathbb{N}}\N,\star,\ast,\dots\rangle$, meaning that the operations and relations of the structure are computable, and an equivalence relation $E$ on $\N$, not necessarily computable but which is a congruence with respect to this structure, such that the quotient $\langle\N,\star,\ast,\dots\rangle/E$ is isomorphic to $\mathcal A$. Thus, one may consider computable quotient presentations of graphs, groups, orders, rings and so on, for any kind of mathematical structure. In a language with relations, it is also natural to relax the concept somewhat by considering the computably enumerable quotient presentations, which allow the pre-quotient relations to be merely computably enumerable, rather than insisting that they must be computable.

At the 2016 conference Mathematical Logic and its Applications at the Research Institute for Mathematical Sciences (RIMS) in Kyoto, Bakhadyr Khoussainov outlined a sweeping vision for the use of computable quotient presentations as a fruitful alternative approach to the subject of computable model theory. In his talk (see his slides), he outlined a program of guiding questions and results in this emerging area. Part of this program concerns the investigation, for a fixed equivalence relation $E$ or type of equivalence relation, which kind of computable quotient presentations are possible with respect to quotients modulo $E$.

In this article, we engage specifically with two conjectures that Khoussainov had made at the meeting.

Conjecture. (Khoussainov)

  1. No nonstandard model of arithmetic admits a computable quotient presentation by a computably enumerable equivalence relation on the natural numbers.
  2. Some nonstandard model of arithmetic admits a computable quotient presentation by a co-c.e.~equivalence relation.

We prove the first conjecture and refute several natural variations of the second conjecture, although a further natural variation, perhaps the central case, remains open. In addition, we consider and settle the natural analogues of the conjectures for models of set theory.

The implicitly constructible universe

  • M. J.~Groszek and J. D. Hamkins, “The implicitly constructible universe,” ArXiv e-prints, 2017. (manuscript under review)  
    @ARTICLE{GroszekHamkins:The-implicitly-constructible-universe,
    author = {Marcia J.~Groszek and Joel David Hamkins},
    title = {The implicitly constructible universe},
    journal = {ArXiv e-prints},
    year = 2017,
    month = feb,
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {manuscript under review},
    abstract = {},
    keywords = {},
    source = {},
    doi = {},
    eprint = {1702.07947},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/the-implicitly-constructible-universe},
    }

Abstract. We answer several questions posed by Hamkins and Leahy concerning the implicitly constructible universe $\newcommand\Imp{\text{Imp}}\Imp$, which they introduced in their paper, Algebraicity and implicit definability in set theory. Specifically, we show that it is relatively consistent with ZFC that $\Imp \models \neg \text{CH}$, that $\Imp \neq \text{HOD}$, and that $\Imp \models V \neq \Imp$, or in other words, that $(\Imp)^{\Imp} \neq \Imp$.

Open and clopen determinacy for proper class games, VCU MAMLS April 2017

This will be a talk for the Mid-Atlantic Mathematical Logic Seminar at Virginia Commonwealth University, a conference to be held April 1-2, 2017.

Richmond A line train bridge

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

Lewis ChessmenThis is joint work with Victoria Gitman. See our article, Open determinacy for class games.

Slides

 

 

 

VCU MAMLS 2017

 

Computable quotient presentations of models of arithmetic and set theory, CUNY set theory seminar, March 2017

This will be a talk for the CUNY Set Theory Seminar on March 10, 2017, 10:00 am in room 6417 at the CUNY Graduate Center.

CUNY GC

Abstract.  I shall prove various extensions of the Tennenbaum phenomenon to the case of computable quotient presentations of models of arithmetic and set theory. Specifically, no nonstandard model of arithmetic has a computable quotient presentation by a c.e. equivalence relation. No $\Sigma_1$-sound nonstandard model of arithmetic has a computable quotient presentation by a co-c.e. equivalence relation. No nonstandard model of arithmetic in the language $\{+,\cdot,\leq\}$ has a computably enumerable quotient presentation by any equivalence relation of any complexity. No model of ZFC or even much weaker set theories has a computable quotient presentation by any equivalence relation of any complexity. And similarly no nonstandard model of finite set theory has a computable quotient presentation. This is joint work with Michał Tomasz Godziszewski.

A computable quotient presentation of a mathematical structure $\mathcal A$ consists of a computable structure on the natural numbers $\langle\newcommand\N{\mathbb{N}}\N,\star,\ast,\dots\rangle$, meaning that the operations and relations of the structure are computable, and an equivalence relation $E$ on $\N$, not necessarily computable but which is a congruence with respect to this structure, such that the quotient $\langle\N,\star,\ast,\dots\rangle/E$ is isomorphic to $\mathcal A$. Thus, one may consider computable quotient presentations of graphs, groups, orders, rings and so on, for any kind of mathematical structure. In a language with relations, it is also natural to relax the concept somewhat by considering the computably enumerable quotient presentations, which allow the pre-quotient relations to be merely computably enumerable, rather than insisting that they must be computable.

At the 2016 conference Mathematical Logic and its Applications at the Research Institute for Mathematical Sciences (RIMS) in Kyoto, Bakhadyr Khoussainov outlined a sweeping vision for the use of computable quotient presentations as a fruitful alternative approach to the subject of computable model theory. In his talk (see his slides), he outlined a program of guiding questions and results in this emerging area. Part of this program concerns the investigation, for a fixed equivalence relation $E$ or type of equivalence relation, which kind of computable quotient presentations are possible with respect to quotients modulo $E$.

In my talk, I shall engage specifically with two conjectures that Khoussainov had made at the meeting.

Conjecture. (Khoussainov)

  1. No nonstandard model of arithmetic admits a computable quotient presentation by a computably enumerable equivalence relation on the natural numbers.
  2. Some nonstandard model of arithmetic admits a computable quotient presentation by a co-c.e.~equivalence relation.

We prove the first conjecture and refute several natural variations of the second conjecture, although a further natural variation, perhaps the central case, remains open. In addition, we consider and settle the natural analogues of the conjectures for models of set theory.

All triangles are isosceles

Let me share a mathematical gem with you, the following paradoxical “theorem.”

Theorem. Every triangle is isosceles.

Proof. Consider an arbitrary triangle $\triangle ABC$. Let $Q$ be the intersection of the angle bisector (blue) at $\angle A$ and the perpendicular bisector (green) of $BC$ at midpoint $P$.

Isosceles triangle

Drop perpendiculars from $Q$ to $AB$ at $R$ and to $AC$ at $S$. Because $P$ is the midpoint of $BC$ and $PQ$ is perpendicular, we deduce $BQ\cong CQ$ by the Pythagorean theorem. Since $AQ$ is the angle bisector of $\angle A$, the triangles $AQR$ and $AQS$ are similar, and since they share a hypotenuse, they are congruent. It follows that $AR\cong AS$ and also $QR\cong QS$. Therefore $\triangle BQR$ is congruent to $\triangle CQS$ by the hypotenuse-leg congruence theorem. So $RB\cong SC$. And therefore,
$$AB\cong AR+RB\cong AS+SC\cong AC,$$
and so the triangle is isosceles, as desired. QED

Corollary.  Every triangle is equilateral.

Proof. The previous argument proceeded from an arbitrary vertex of the triangle, and so any pair of adjacent sides in the triangle are congruent. So all three are congruent, and therefore it is equilateral. QED

Perhaps you object to my figure, because depending on the triangle, perhaps the angle bisector of $A$ passes on the other side of the midpoint $P$ of $BC$, which would make the point $Q$ lie outside the triangle, as in the following figure.

Isosceles triangle 2

Nevertheless, essentially the same argument works also in this case. Namely, we again let $Q$ be the intersection of the angle bisector at $\angle A$ with the perpendicular bisector of $BC$ at midpoint $P$, and again drop the perpendiculars from $Q$ to $R$ and $S$. Again, we get $BQ\cong CQ$ by the Pythagorean theorem, using the green triangles. And again, we get $\triangle ARQ\cong\triangle ASQ$ since these are similar triangles with the same hypotenuse. So again, we conclude $\triangle BQR\cong\triangle CQS$ by hypotenuse-leg. So we deduce $AB\cong AR-BR\cong AS-CS\cong AC$, by subtracting rather than adding as before, and so the triangle is isosceles.

Question. What is wrong with these arguments?

Please post your answers in the comments below.

The argument is evidently due to E. A. Maxwell, Fallacies in Mathematics, 1959. I first heard it years ago, when I was in graduate school.  Shortly afterward, my advisor W. Hugh Woodin happened to be a little late to seminar, and so I leaped to the chalkboard and gave this proof, leaving the distinguished audience, including R. Solovay, scratching their heads for a while. Woodin arrived, but Solovay wouldn’t let him start the seminar, since he wanted to resolve the triangle argument. What fun!