# 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,” in Logic, Language, Information, and Computation: 24th International Workshop, WoLLIC 2017, London, UK, July 18-21, 2017, Proceedings, J. Kennedy and R. J. G. B. de Queiroz, Eds., Springer, 2017, pp. 140-152.
@Inbook{GodziszewskiHamkins2017:Computable-quotient-presentations-of-models-of-arithmetic-and-set-theory,
author="Godziszewski, Micha{\l} Tomasz and Hamkins, Joel David",
editor="Kennedy, Juliette and de Queiroz, Ruy J.G.B.",
title="Computable Quotient Presentations of Models of Arithmetic and Set Theory",
bookTitle="Logic, Language, Information, and Computation: 24th International Workshop, WoLLIC 2017, London, UK, July 18-21, 2017, Proceedings",
year="2017",
publisher="Springer",
pages="140--152",
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 {\$}{\$}{\backslash}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 {\$}{\$}{\backslash}{\{}+,{\backslash}cdot ,{\backslash}le {\backslash}{\}}{\$}{\$} 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.",
isbn="978-3-662-55386-2",
doi="10.1007/978-3-662-55386-2_10",
eprint = {1702.08350},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://wp.me/p5M0LV-1tW},
}

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$.

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. (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 = {under review},
abstract = {},
keywords = {under-review},
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$.

# The rearrangement number

• A. Blass, J. Brendle, W. Brian, J. D. Hamkins, M. Hardy, and P. B. Larson, “The rearrangement number,” ArXiv e-prints, 2016. (manuscript under review)
@ARTICLE{BlassBrendleBrianHamkinsHardyLarson:TheRearrangementNumber,
author = {Andreas Blass and Jörg Brendle and Will Brian and Joel David Hamkins and Michael Hardy and Paul B. Larson},
title = {The rearrangement number},
journal = {ArXiv e-prints},
year = {2016},
volume = {},
number = {},
pages = {},
month = {},
note = {manuscript under review},
url = {http://jdh.hamkins.org/the-rearrangement-number},
eprint = {1612.07830},
archivePrefix = {arXiv},
primaryClass = {math.LO},
abstract = {},
keywords = {under-review},
source = {},
}

Abstract.  How many permutations of the natural numbers are needed so that every conditionally convergent series of real numbers can be rearranged to no longer converge to the same sum? We show that the minimum number of permutations needed for this purpose, which we call the rearrangement number, is uncountable, but whether it equals the cardinal of the continuum is independent of the usual axioms of
set theory. We compare the rearrangement number with several natural variants, for example one obtained by requiring the rearranged series to still converge but to a new, finite limit. We also compare the rearrangement number with several well-studied
cardinal characteristics of the continuum. We present some new forcing constructions designed to add permutations that rearrange series from the ground model in particular ways, thereby obtaining consistency results going beyond those that follow from comparisons with familiar cardinal characteristics. Finally we deal briefly with some variants concerning rearrangements by a special sort of permutations and with rearranging some divergent series to become (conditionally) convergent.

This project started with Michael Hardy’s question on MathOverflow, How many rearrangements must fail to alter the value of a sum before you conclude that none do? I had proposed in my answer that we should think of the cardinal in question as a cardinal characteristic of the continuum, the rearrangement number, since we could prove that it was uncountable and that it was the continuum under MA, and had begun to separate it from other familiar cardinal characteristics. Eventually, the research effort grew into the collaboration of this paper. What a lot of fun!

Here are the lecture notes for an introductory talk on the topic I had given at the Vassar College Mathematics Colloquium

# Ord is not definably weakly compact

• A. Enayat and J. D. Hamkins, “ZFC proves that the class of ordinals is not weakly compact for definable classes,” J.~Symbolic Logic, vol. 83, iss. 1, pp. 146-164, 2018.
@ARTICLE{EnayatHamkins2018:Ord-is-not-definably-weakly-compact,
author = {Ali Enayat and Joel David Hamkins},
title = {{ZFC} proves that the class of ordinals is not weakly compact for definable classes},
journal = {J.~Symbolic Logic},
year = {2018},
volume = {83},
number = {1},
pages = {146--164},
month = {},
note = {},
abstract = {},
keywords = {},
source = {},
doi = {10.1017/jsl.2017.75},
eprint = {1610.02729},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://jdh.hamkins.org/ord-is-not-definably-weakly-compact},
}

In ZFC the class of all ordinals is very like a large cardinal.  Being closed under exponentiation, for example, Ord is a strong limit.  Indeed, it is a beth fixed point. And Ord is regular with respect to definable classes by the replacement axiom.  In this sense, ZFC therefore proves that Ord is definably inaccessible.  Which other large cardinal properties are exhibited by Ord? Perhaps you wouldn’t find it unreasonable for Ord to exhibit, at least consistently with ZFC, the definable proper class analogues of other much stronger large cardinal properties?

Meanwhile, the main results of this paper, joint between myself and Ali Enayat, show that such an expectation would be misplaced, even for comparatively small large cardinal properties. Specifically, in a result that surprised me, it turns out that the class of ordinals NEVER exhibits the definable proper class analogue of weak compactness in any model of ZFC.

Theorem. The class of ordinals is not definably weakly compact. In every model of ZFC:

1. The definable tree property fails; there is a definable Ord-tree with no definable cofinal branch.
2. The definable partition property fails; there is a definable 2-coloring of a definable proper class, with no homogeneous definable proper subclass.
3. The definable compactness property fails for $\mathcal{L}_{\mathrm{Ord,\omega}}$; there is a definable theory in this logic, all of whose set-sized subtheories are satisfiable, but the whole theory has no definable class model.

The proof uses methods from the model theory of set theory, including especially the fact that no model of ZFC has a conservative $\Sigma_3$-elementary end-extension.

Theorem. The definable $\Diamond _{\mathrm{Ord}}$ principle holds in a model of ZFC if and only if the model has a definable well-ordering.

We close the paper by proving that the theory of the spartan models of Gödel-Bernays set theory GB — those equipped with only their definable classes — is $\Pi^1_1$-complete.

Theorem. The set of sentences true in all spartan models of GB is $\Pi_{1}^{1}$-complete.

# The Vopěnka principle is inequivalent to but conservative over the Vopěnka scheme

• J. D. Hamkins, “The Vopěnka principle is inequivalent to but conservative over the Vopěnka scheme,” ArXiv e-prints, 2016. (under review)
@ARTICLE{Hamkins:The-Vopenka-principle-is-inequivalent-to-but-conservative-over-the-Vopenka-scheme,
author = {Joel David Hamkins},
title = {The {Vop\v{e}nka} principle is inequivalent to but conservative over the {Vop\v{e}nka} scheme},
journal = {ArXiv e-prints},
year = {2016},
volume = {},
number = {},
pages = {},
month = {},
note = {under review},
abstract = {},
keywords = {under-review},
source = {},
eprint = {1606.03778},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://wp.me/p5M0LV-1lV},
}

Abstract. The Vopěnka principle, which asserts that every proper class of first-order structures in a common language admits an elementary embedding between two of its members, is not equivalent over GBC to the first-order Vopěnka scheme, which makes the Vopěnka assertion only for the first-order definable classes of structures. Nevertheless, the two Vopěnka axioms are equiconsistent and they have exactly the same first-order consequences in the language of set theory. Specifically, GBC plus the Vopěnka principle is conservative over ZFC plus the Vopěnka scheme for first-order assertions in the language of set theory.

The Vopěnka principle is the assertion that for every proper class $\mathcal{M}$ of first-order $\mathcal{L}$-structures, for a set-sized language $\mathcal{L}$, there are distinct members of the class $M,N\in\mathcal{M}$ with an elementary embedding $j:M\to N$ between them. In quantifying over classes, this principle is a single assertion in the language of second-order set theory, and it makes sense to consider the Vopěnka principle in the context of a second-order set theory, such as Godel-Bernays set theory GBC, whose language allows one to quantify over classes. In this article, GBC includes the global axiom of choice.

In contrast, the first-order Vopěnka scheme makes the Vopěnka assertion only for the first-order definable classes $\mathcal{M}$ (allowing parameters). This theory can be expressed as a scheme of first-order statements, one for each possible definition of a class, and it makes sense to consider the Vopěnka scheme in Zermelo-Frankael ZFC set theory with the axiom of choice.

Because the Vopěnka principle is a second-order assertion, it does not make sense to refer to it in the context of ZFC set theory, whose first-order language does not allow quantification over classes; one typically retreats to the Vopěnka scheme in that context. The theme of this article is to investigate the precise meta-mathematical interactions between these two treatments of Vopěnka’s idea.

Main Theorems.

1. If ZFC and the Vopěnka scheme holds, then there is a class forcing extension, adding classes but no sets, in which GBC and the Vopěnka scheme holds, but the Vopěnka principle fails.
2. If ZFC and the Vopěnka scheme holds, then there is a class forcing extension, adding classes but no sets, in which GBC and the Vopěnka principle holds.

It follows that the Vopěnka principle VP and the Vopěnka scheme VS are not equivalent, but they are equiconsistent and indeed, they have the same first-order consequences.

Corollaries.

1. Over GBC, the Vopěnka principle and the Vopěnka scheme, if consistent, are not equivalent.
2. Nevertheless, the two Vopěnka axioms are equiconsistent over GBC.
3. Indeed, the two Vopěnka axioms have exactly the same first-order consequences in the language of set theory. Specifically, GBC plus the Vopěnka principle is conservative over ZFC plus the Vopěnka scheme for assertions in the first-order language of set theory. $$\text{GBC}+\text{VP}\vdash\phi\qquad\text{if and only if}\qquad\text{ZFC}+\text{VS}\vdash\phi$$

These results grew out of my my answer to a MathOverflow question of Mike Shulman, Can Vopěnka’s principle be violated definably?, inquiring whether there would always be a definable counterexample to the Vopěnka principle, whenever it should happen to fail. I interpret the question as asking whether the Vopěnka scheme is necessarily equivalent to the Vopěnka principle, and the answer is negative.

The proof of the main theorem involves the concept of a stretchable set $g\subset\kappa$ for an $A$-extendible cardinal, which has the property that for every cardinal $\lambda>\kappa$ and every extension $h\subset\lambda$ with $h\cap\kappa=g$, there is an elementary embedding $j:\langle V_\lambda,\in,A\cap V_\lambda\rangle\to\langle V_\theta,\in,A\cap V_\theta\rangle$ such that $j(g)\cap\lambda=h$. Thus, the set $g$ can be stretched by an $A$-extendibility embedding so as to agree with any given $h$.

# Set-theoretic mereology

• 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.
@ARTICLE{HamkinsKikuchi2016:Set-theoreticMereology,
author = {Joel David Hamkins and Makoto Kikuchi},
title = {Set-theoretic mereology},
journal = {Logic and Logical Philosophy, special issue Mereology and beyond, part II''},
editor = {A.~C.~Varzi and R.~Gruszczy{\'n}ski},
year = {2016},
volume = {25},
number = {3},
pages = {285--308},
month = {},
doi = {10.12775/LLP.2016.007},
note = {},
eprint = {1601.06593},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://jdh.hamkins.org/set-theoretic-mereology},
abstract = {},
keywords = {},
source = {},
ISSN = {1425-3305},
MRCLASS = {03A05 (03E70)},
MRNUMBER = {3546211},
}

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

In light of the comparative success of membership-based set theory in the foundations of mathematics, since the time of Cantor, Zermelo and Hilbert, a mathematical philosopher naturally wonders whether one might find a similar success for mereology, based upon a mathematical or set-theoretic parthood relation rather than the element-of relation $\in$. Can set-theoretic mereology serve as a foundation of mathematics? And what should be the central axioms of set-theoretic mereology?

We should like therefore to consider a mereological perspective in set theory, analyzing how well it might serve as a foundation while identifying the central axioms. Although set theory and mereology, of course, are often seen as being in conflict, what we take as the project here is to develop and investigate, within set theory, a set-theoretic interpretation of mereological ideas. Mereology, by placing its focus on the parthood relation, seems naturally interpreted in set theory by means of the inclusion relation $\of$, so that one set $x$ is a part of another $y$, just in case $x$ is a subset of $y$, written $x\of y$. This interpretation agrees with David Lewis’s Parts of Classes (1991) interpretation of set-theoretic mereology in the context of sets and classes, but we restrict our attention to the universe of sets. So in this article we shall consider the formulation of set-theoretic mereology as the study of the structure $\langle V,\of\rangle$, which we shall take as the canonical fundamental structure of set-theoretic mereology, where $V$ is the universe of all sets; this is in contrast to the structure $\langle V,{\in}\rangle$, usually taken as central in set theory. The questions are: How well does this mereological structure serve as a foundation of mathematics? Can we faithfully interpret the rest of mathematics as taking place in $\langle V,\of\rangle$ to the same extent that set theorists have argued (with whatever degree of success) that one may find faithful representations in $\langle V,{\in}\rangle$? Can we get by with merely the subset relation $\of$ in place of the membership relation $\in$?

Ultimately, we shall identify grounds supporting generally negative answers to these questions. On the basis of various mathematical results, our main philosophical thesis will be that the particular understanding of set-theoretic mereology via the inclusion relation $\of$ cannot adequately serve by itself as a foundation of mathematics. Specifically, the following theorem and corollary show that $\in$ is not definable from $\of$, and we take this to show that one may not interpret membership-based set theory itself within set-theoretic mereology in any straightforward, direct manner.

Theorem. In any universe of set theory $\langle V,{\in}\rangle$, there is a definable relation $\in^*$, different from $\in$, such that $\langle V,{\in^*}\rangle$ is a model of set theory, in fact isomorphic to the original universe $\langle V,{\in}\rangle$, for which the corresponding inclusion relation $$u\subseteq^* v\quad\longleftrightarrow\quad \forall a\, (a\in^* u\to a\in^* v)$$ is identical to the usual inclusion relation $u\subseteq v$.

Corollary. One cannot define $\in$ from $\subseteq$ in any model of set theory, even allowing parameters in the definition.

A counterpoint to this is provided by the following theorem, however, which identifies a weak sense in which $\of$ may identify $\in$ up to definable automorphism of the universe.

Theorem. Assume ZFC in the universe $\langle V,\in\rangle$. Suppose that $\in^*$ is a definable class relation in $\langle V,{\in}\rangle$ for which $\langle V,\in^*\rangle$ is a model of set theory (a weak set theory suffices), such that the corresponding inclusion relation $$u\subseteq^* v\quad\iff\quad\forall a\,(a\in^* u\to a\in^* v)$$is the same as the usual inclusion relation $u\subseteq v$. Then the two membership relations are isomorphic $$\langle V,\in\rangle\cong\langle V,\in^*\rangle.$$

That counterpoint is not decisive, however, in light of the question whether we really need $\in^*$ to be a class with respect to $\in$, a question resolved by the following theorem, which shows that set-theoretic mereology does not actually determine the $\in$-isomorphism class or even the $\in$-theory of the $\in$-model in which it arises.

Theorem. For any two consistent theories extending ZFC, there are models $\langle W,{\in}\rangle$ and $\langle W,{\in^*}\rangle$ of those theories, respectively, with the same underlying set $W$ and the same induced inclusion relation $\of=\of^*$.

For example, we cannot determine in $\of$-based set-theoretic mereology whether the continuum hypothesis holds or fails, whether the axiom of choice holds or fails or whether there are large cardinals or not. Initially, the following central theorem may appear to be a positive result for mereology, since it identifies precisely what are the principles of set-theoretic mereology, considered as the theory of $\langle V,{\of}\rangle$. Namely, $\of$ is an atomic unbounded relatively complemented distributive lattice, and this is a finitely axiomatizable complete theory. So in a sense, this theory simply is the theory of $\of$-based set-theoretic mereology.

Theorem. Set-theoretic mereology, considered as the theory of $\langle V,\of\rangle$, is precisely the theory of an atomic unbounded relatively complemented distributive lattice, and furthermore, this theory is finitely axiomatizable, complete and decidable.

But upon reflection, since every finitely axiomatizable complete theory is decidable, the result actually appears to be devastating for set-theoretic mereology as a foundation of mathematics, because a decidable theory is much too simple to serve as a foundational theory for all mathematics. The full spectrum and complexity of mathematics naturally includes all the instances of many undecidable decision problems and so cannot be founded upon a decidable theory. Finally, it follows as a corollary that the structure consisting of the hereditarily finite sets under inclusion forms an elementary substructure of the full set-theoretic mereological universe $$\langle \text{HF},\of\rangle\prec\langle V,\of\rangle.$$ Consequently set-theoretic mereology cannot properly treat or even express the various concepts of infinity that arise in mathematics.

Some previous posts on this blog:

# Upward closure and amalgamation in the generic multiverse of a countable model of set theory

• J. D. Hamkins, “Upward closure and amalgamation in the generic multiverse of a countable model of set theory,” RIMS Kyôkyûroku, pp. 17-31, 2016.
@ARTICLE{Hamkins2016:UpwardClosureAndAmalgamationInTheGenericMultiverse,
author = {Joel David Hamkins},
title = {Upward closure and amalgamation in the generic multiverse of a countable model of set theory},
journal = {RIMS {Ky\^oky\^uroku}},
year = {2016},
volume = {},
number = {},
pages = {17--31},
month = {},
newton = {ni15066},
url = {http://wp.me/p5M0LV-1cv},
eprint = {1511.01074},
archivePrefix = {arXiv},
primaryClass = {math.LO},
abstract = {},
keywords = {},
source = {},
issn = {1880-2818},
}

Abstract. I prove several theorems concerning upward closure and amalgamation in the generic multiverse of a countable transitive model of set theory. Every such model $W$ has forcing extensions $W[c]$ and $W[d]$ by adding a Cohen real, which cannot be amalgamated in any further extension, but some nontrivial forcing notions have all their extensions amalgamable. An increasing chain $W[G_0]\subseteq W[G_1]\subseteq\cdots$ has an upper bound $W[H]$ if and only if the forcing had uniformly bounded essential size in $W$. Every chain $W\subseteq W[c_0]\subseteq W[c_1]\subseteq \cdots$ of extensions adding Cohen reals is bounded above by $W[d]$ for some $W$-generic Cohen real $d$.

This article is based upon I talk I gave at the conference on Recent Developments in Axiomatic Set Theory at the Research Institute for Mathematical Sciences (RIMS) at Kyoto University, Japan in September, 2015, and I am extremely grateful to my Japanese hosts, especially Toshimichi Usuba, for supporting my research visit there and also at the CTFM conference at Tokyo Institute of Technology just preceding it. This article includes material adapted from section section 2 of Set-theoretic geology, joint with G. Fuchs, myself and J. Reitz, and also includes a theorem that was proved in a series of conversations I had with Giorgio Venturi at the Young Set Theory Workshop 2011 in Bonn and continuing at the London 2011 summer school on set theory at Birkbeck University London.

# A position in infinite chess with game value $\omega^4$

• C.~D.~A.~Evans, J. D. Hamkins, and N. L. Perlmutter, “A position in infinite chess with game value $\omega^4$,” Integers, vol. 17, p. Paper No.~G4, 22, 2017.
@ARTICLE{EvansHamkinsPerlmutter:APositionInInfiniteChessWithGameValueOmega^4,
author = {C.~D.~A.~Evans and Joel David Hamkins and Norman Lewis Perlmutter},
title = {A position in infinite chess with game value $\omega^4$},
journal = {Integers},
FJOURNAL = {Integers Electronic Journal of Combinatorial Number Theory},
year = {2017},
volume = {17},
number = {},
pages = {Paper No.~G4, 22},
eprint = {1510.08155},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://wp.me/p5M0LV-1c5},
month = {},
note = {},
abstract = {},
keywords = {},
source = {},
newton = {ni15065},
}

Abstract.  We present a position in infinite chess exhibiting an ordinal game value of $\omega^4$, thereby improving on the previously largest-known values of $\omega^3$ and $\omega^3\cdot 4$.

This is a joint work with Cory Evans and Norman Perlmutter, continuing the research program of my previous article with Evans, Transfinite game values in infinite chess, namely, the research program of finding positions in infinite chess with large transfinite ordinal game values. In the previous article, Cory and I presented a position with game value $\omega^3$. In the current paper, with Norman Perlmutter now having joined us accompanied by some outstanding ideas, we present a new position having game value $\omega^4$, breaking the previous record.

A position in infinite chess with value $\omega^4$

In the new position, above, the kings sit facing each other in the throne room, an uneasy détente, while white makes steady progress in the rook towers. Meanwhile, at every step black, doomed, mounts increasingly desperate bouts of long forced play using the bishop cannon battery, with bishops flying with force out of the cannons, and then each making a long series of forced-reply moves in the terminal gateways. Ultimately, white wins with value omega^4, which exceeds the previously largest known values of omega^3.

In the throne room, if either black or white places a bishop on the corresponding diagonal entryway, then checkmate is very close. A key feature is that for white to place a white-square white bishop on the diagonal marked in red, it is immediate checkmate, whereas if black places a black-square black bishop on the blue diagonal, then checkmate comes three moves later.  The bishop cannon battery arrangement works because black threatens to release a bishop into the free region, and if white does not reply to those threats, then black will be three steps ahead, but otherwise, only two.

The throne room

The rook towers are similar to the corresponding part of the previous $\omega^3$ position, and this is where white undertakes most of his main line progress towards checkmate.  Black will move the key bishop out as far as he likes on the first move, past $n$ rook towers, and the resulting position will have value $\omega^3\cdot n$.  These towers are each activated in turn, leading to a long series of play for white, interrupted at every opportunity by black causing a dramatic spectacle of forced-reply moves down in the bishop cannon battery.

The rook towers

At every opportunity, black mounts a long distraction down in the bishop cannon battery.  Shown here is one bishop cannon. The cannonballs fire out of the cannon with force, in the sense that when each green bishop fires out, then white must reply by moving the guard pawns into place.

Bishop cannon

Upon firing, each bishop will position itself so as to attack the entrance diagonal of a long bishop gateway terminal wing.  This wing is arranged so that black can make a series of forced-reply threats successively, by moving to the attack squares (marked with the blue squares). Black is threatening to exit through the gateway doorway (in brown), but white can answer the threat by moving the white bishop guards (red) into position. Thus, each bishop coming out of a cannon (with force) can position itself at a gateway terminal of length $g$, making $g$ forced-reply moves in succession.  Since black can initiate firing with an arbitrarily large cannon, this means that at any moment, black can cause a forced-reply delay with game value $\omega^2$. Since the rook tower also has value $\omega^2$ by itself, the overall position has value $\omega^4=\omega^2\cdot\omega^2$.

Bishop gateway terminal wing

With future developments in mind, we found that one can make a more compact arrangement of the bishop cannon battery, freeing up a quarter board for perhaps another arrangement that might lead to a higher ordinal values.

Alternative compact version of bishop cannon battery

Read more about it in the article, which is available at the arxiv (pdf).

# Open determinacy for class games

• V. Gitman and J. D. Hamkins, “Open determinacy for class games,” in Foundations of Mathematics, Logic at Harvard, Essays in Honor of Hugh Woodin’s 60th Birthday, A. E. Caicedo, J. Cummings, P. Koellner, and P. Larson, Eds., , 2016. (Newton Institute preprint ni15064)
@INCOLLECTION{GitmanHamkins2016:OpenDeterminacyForClassGames,
author = {Victoria Gitman and Joel David Hamkins},
title = {Open determinacy for class games},
booktitle = {Foundations of Mathematics, Logic at Harvard, Essays in Honor of Hugh Woodin's 60th Birthday},
publisher = {},
year = {2016},
editor = {Andr\'es E. Caicedo and James Cummings and Peter Koellner and Paul Larson},
volume = {},
number = {},
series = {AMS Contemporary Mathematics},
type = {},
chapter = {},
pages = {},
edition = {},
month = {},
note = {Newton Institute preprint ni15064},
url = {http://wp.me/p5M0LV-1af},
eprint = {1509.01099},
archivePrefix = {arXiv},
primaryClass = {math.LO},
abstract = {},
keywords = {},
}

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 Godel-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 transfinite recursion 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.

See my earlier posts on part of this material:

# A mathematician’s year in Japan

• J. D. Hamkins, A Mathematician’s Year in Japan, Amazon Kindle Direct Publishing, 2015. (\href{http://www.amazon.com/dp/B00U618LM2}{ASIN:B00U618LM2}, 156 pages)
@BOOK{Hamkins2015:AMathematiciansYearInJapan,
author = {Joel David Hamkins},
title = {A {Mathematician's} {Year} in {Japan}},
publisher = {Amazon Kindle Direct Publishing},
year = {2015},
month = {March},
keywords = {book},
url = {http://www.amazon.com/dp/B00U618LM2},
note = {\href{http://www.amazon.com/dp/B00U618LM2}{ASIN:B00U618LM2}, 156 pages},
}

Years ago, when I was still a junior professor, I had the pleasure to live for a year in Japan, working as a research fellow at Kobe University. During that formative year, I recorded brief moments of my Japanese experience, and every two weeks or so—this was well before the current blogging era—I sent my descriptive missives by email to friends back home. I have now collected together those vignettes of my life in Japan, each a morsel of my experience. The book is now out!

A Mathematician’s Year in Japan
Joel David Hamkins

Glimpse into the life of a professor of logic as he fumbles his way through Japan.

A Mathematician’s Year in Japan is a lighthearted, though at times emotional account of how one mathematician finds himself in a place where everything seems unfamiliar, except his beloved research on the nature of infinity, yet even with that he experiences a crisis.


We make our argument in part by proving that different models of set theory can have a structure identically in common, even the natural numbers, yet disagree on the theory of truth for that structure.

Theorem.

• Two models of set theory can have the same structure of arithmetic $$\langle\N,{+},{\cdot},0,1,{\lt}\rangle^{M_1}=\langle\N,{+},{\cdot},0,1,{\lt}\rangle^{M_2},$$yet disagree on the theory of arithmetic truth.
• Two models of set theory can have the same natural numbers and a computable linear order in common, yet disagree about whether it is a well-order.
• Two models of set theory that have the same natural numbers and the same reals, yet disagree on projective truth.
• Two models of set theory can have a transitive rank initial segment in common $$\langle V_\delta,{\in}\rangle^{M_1}=\langle V_\delta,{\in}\rangle^{M_2},$$yet disagree about whether it is a model of ZFC.

The proofs use only elementary classical methods, and might be considered to be a part of the folklore of the subject of models of arithmetic. The paper includes many further examples of the phenomenon, and concludes with a philosophical discussion of the issue of definiteness, concerning the question of whether one may deduce definiteness-of-truth from definiteness-of-objects and definiteness-of-structure.