Category Archives: Publications

Is the dream solution of the continuum hypothesis attainable?

Posted on by
3
  • J. D. Hamkins, “Is the dream solution of the continuum hypothesis attainable?,” , pp. 1-10. (submitted)  
    Citation arχiv 
    @ARTICLE{Hamkins:IsTheDreamSolutionToTheContinuumHypothesisAttainable,
AUTHOR = {Joel David Hamkins},
TITLE = {Is the dream solution of the continuum hypothesis attainable?},
JOURNAL = {},
YEAR = {},
volume = {},
number = {},
pages = {1--10},
month = {},
note = {submitted},
abstract = {},
keywords = {},
source = {},
eprint = {1203.4026},
url = {http://arxiv.org/abs/1203.4026},
}

Many set theorists yearn for a definitive solution of the continuum problem, what I call a  dream solution, one by which we settle the continuum hypothesis (CH) on the basis of a new fundamental principle of set theory, a missing axiom, widely regarded as true, which determines the truth value of CH.  In an earlier article, I have described the dream solution template as proceeding in two steps: first, one introduces the new set-theoretic principle, considered obviously true for sets in the same way that many mathematicians find the axiom of choice or the axiom of replacement to be true; and second, one proves the CH or its negation from this new axiom and the other axioms of set theory. Such a situation would resemble Zermelo’s proof of the ponderous well-order principle on the basis of the comparatively natural axiom of choice and the other Zermelo axioms. If achieved, a dream solution to the continuum problem would be remarkable, a cause for celebration.

In this article, however, I argue that a dream solution of CH has become impossible to achieve. Specifically, what I claim is that our extensive experience in the set-theoretic worlds in which CH is true and others in which CH is false prevents us from looking upon any statement settling CH as being obviously true. We simply have had too much experience by now with the contrary situation. Even if set theorists initially find a proposed new principle to be a natural, obvious truth, nevertheless once it is learned that the principle settles CH, then this preliminary judgement will evaporate in the face of deep experience with the contrary, and set-theorists will look upon the statement merely as an intriguing generalization or curious formulation of CH or $\neg$CH, rather than as a new fundamental truth. In short, success in the second step of the dream solution will inevitably undermine success in the first step.

This article is based upon an argument I gave during the course of a three-lecture tutorial on set-theoretic geology at the summer school Set Theory and Higher-Order Logic: Foundational Issues and Mathematical Development, at the University of London, Birkbeck in August 2011.  Much of the article is adapted from and expands upon the corresponding section of material in my article The set-theoretic multiverse.

The mate-in-n problem of infinite chess is decidable

Posted on by
5
  • D. Brumleve, J. D. Hamkins, and P. Schlicht, “The mate-in-$n$ problem of infinite chess is decidable,” to appear in LNCS Proceedings, pp. 1-10.  
    Citation arχiv 
    @ARTICLE{BrumleveHamkinsSchlicht:TheMateInNProblemOfInfiniteChessIsDecidable,
AUTHOR = {Dan Brumleve and Joel David Hamkins and Philipp Schlicht},
TITLE = {The mate-in-$n$ problem of infinite chess is decidable},
JOURNAL = {to appear in LNCS Proceedings},
YEAR = {},
volume = {},
number = {},
pages = {1--10},
month = {},
note = {},
eprint = {1201.5597},
url = {http://arxiv.org/abs/1201.5597},
abstract = {},
keywords = {},
source = {},
}

Infinite chess is chess played on an infinite edgeless chessboard. The familiar chess pieces move about according to their usual chess rules, and each player strives to place the opposing king into checkmate. The mate-in-$n$ problem of infinite chess is the problem of determining whether a designated player can force a win from a given finite position in at most $n$ moves. A naive formulation of this problem leads to assertions of high arithmetic complexity with $2n$ alternating quantifiers—*there is a move for white, such that for every black reply, there is a countermove for white*, and so on. In such a formulation, the problem does not appear to be decidable; and one cannot expect to search an infinitely branching game tree even to finite depth.

Nevertheless, the main theorem of this article, confirming a conjecture of the first author and C. D. A. Evans, establishes that the mate-in-$n$ problem of infinite chess is computably decidable, uniformly in the position and in $n$. Furthermore, there is a computable strategy for optimal play from such mate-in-$n$ positions. The proof proceeds by showing that the mate-in-$n$ problem is expressible in what we call the first-order structure of chess, which we prove (in the relevant fragment) is an automatic structure, whose theory is therefore decidable. Unfortunately, this resolution of the mate-in-$n$ problem does not appear to settle the decidability of the more general winning-position problem, the problem of determining whether a designated player has a winning strategy from a given position, since a position may admit a winning strategy without any bound on the number of moves required. This issue is connected with transfinite game values in infinite chess, and the exact value of the omega one of chess $\omega_1^{\rm chess}$ is not known.

Richard Stanley’s question on mathoverflow: Decidability of chess on infinite board?

Inner models with large cardinal features usually obtained by forcing

Posted on by
2
  • A. Apter, V. Gitman, and J. D. Hamkins, “Inner models with large cardinal features usually obtained by forcing,” Archive for Mathematical Logic, vol. 51, pp. 257-283, 2012. (10.1007/s00153-011-0264-5)  
    Journal Citation arχiv 
    @article {ApterGitmanHamkins2012:InnerModelsWithLargeCardinals,
author = {Apter, Arthur and Gitman, Victoria and Hamkins, Joel David},
affiliation = {Mathematics, The Graduate Center of the City University of New York, 365 Fifth Avenue, New York, NY 10016, USA},
title = {Inner models with large cardinal features usually obtained by forcing},
journal = {Archive for Mathematical Logic},
publisher = {Springer Berlin / Heidelberg},
issn = {0933-5846},
keyword = {Mathematics and Statistics},
pages = {257--283},
volume = {51},
issue = {3},
url = {http://jdh.hamkins.org/innermodelswithlargecardinals/},
eprint = {1111.0856},
doi = {10.1007/s00153-011-0264-5},
note = {10.1007/s00153-011-0264-5},
year = {2012}
}

We construct a variety of inner models exhibiting features usually obtained by forcing over universes with large cardinals. For example, if there is a supercompact cardinal, then there is an inner model with a Laver indestructible supercompact cardinal. If there is a supercompact cardinal, then there is an inner model with a supercompact cardinal $\kappa$ for which $2^\kappa=\kappa^+$, another for which $2^\kappa=\kappa^{++}$ and another in which the least strongly compact cardinal is supercompact. If there is a strongly compact cardinal, then there is an inner model with a strongly compact cardinal, for which the measurable cardinals are bounded below it and another inner model $W$ with a strongly compact cardinal $\kappa$, such that $H_{\kappa^+}^V\subseteq HOD^W$. Similar facts hold for supercompact, measurable and strongly Ramsey cardinals. If a cardinal is supercompact up to a weakly iterable cardinal, then there is an inner model of the Proper Forcing Axiom and another inner model with a supercompact cardinal in which GCH+V=HOD holds. Under the same hypothesis, there is an inner model with level by level equivalence between strong compactness and supercompactness, and indeed, another in which there is level by level inequivalence between strong compactness and supercompactness. If a cardinal is strongly compact up to a weakly iterable cardinal, then there is an inner model in which the least measurable cardinal is strongly compact. If there is a weakly iterable limit $\delta$ of ${\lt}\delta$-supercompact cardinals, then there is an inner model with a proper class of Laver-indestructible supercompact cardinals. We describe three general proof methods, which can be used to prove many similar results.

What is the theory ZFC without power set?

Posted on by
1
  • V. Gitman, J. D. Hamkins, and T. A. Johnstone, “What is the theory ZFC without Powerset?.” (submitted)  
    Citation arχiv 
    @ARTICLE{GitmanHamkinsJohnstone:WhatIsTheTheoryZFC-Powerset?,
AUTHOR = {Victoria Gitman and Joel David Hamkins and Thomas A. Johnstone},
TITLE = {What is the theory {ZFC} without {Powerset}?},
JOURNAL = {},
YEAR = {},
volume = {},
number = {},
pages = {},
month = {},
note = {submitted},
abstract = {},
keywords = {},
eprint = {1110.2430},
url = {http://arxiv.org/abs/1110.2430},
source = {},
}

This is joint work with Victoria Gitman and Thomas Johnstone.

We show that the theory ZFC-, consisting of the usual axioms of ZFC but with the power set axiom removed-specifically axiomatized by extensionality, foundation, pairing, union, infinity, separation, replacement and the assertion that every set can be well-ordered-is weaker than commonly supposed and is inadequate to establish several basic facts often desired in its context. For example, there are models of ZFC- in which $\omega_1$ is singular, in which every set of reals is countable, yet $\omega_1$ exists, in which there are sets of reals of every size $\aleph_n$, but none of size $\aleph_\omega$, and therefore, in which the collection axiom sceme fails; there are models of ZFC- for which the Los theorem fails, even when the ultrapower is well-founded and the measure exists inside the model; there are models of ZFC- for which the Gaifman theorem fails, in that there is an embedding $j:M\to N$ of ZFC- models that is $\Sigma_1$-elementary and cofinal, but not elementary; there are elementary embeddings $j:M\to N$ of ZFC- models whose cofinal restriction $j:M\to \bigcup j“M$ is not elementary. Moreover, the collection of formulas that are provably equivalent in ZFC- to a $\Sigma_1$-formula or a $\Pi_1$-formula is not closed under bounded quantification. Nevertheless, these deficits of ZFC- are completely repaired by strengthening it to the theory $\text{ZFC}^-$, obtained by using collection rather than replacement in the axiomatization above. These results extend prior work of Zarach.

See Victoria Gitman’s summary post on the article

The hierarchy of equivalence relations on the natural numbers under computable reducibility

Posted on by
3
  • S. Coskey, J. D. Hamkins, and R. Miller, “The hierarchy of equivalence relations on the natural numbers under computable reducibility,” , pp. 1-36. (submitted)  
    Citation arχiv 
    @ARTICLE{CoskeyHamkinsRussell:HierarchyOfEquivalenceRelationsOnN,
AUTHOR = {Samuel Coskey and Joel David Hamkins and Russell Miller},
TITLE = {The hierarchy of equivalence relations on the natural numbers under computable reducibility},
JOURNAL = {},
YEAR = {},
volume = {},
number = {},
pages = {1--36},
month = {},
note = {submitted},
url = {http://arxiv.org/abs/1109.3375},
eprint = {1109.3375},
abstract = {},
keywords = {},
source = {},
}

We define and elaborate upon the notion of computable reducibility between equivalence relations on the natural numbers, providing a natural computable analogue of Borel reducibility, and investigate the hierarchy to which it gives rise. The theory appears well suited for an analysis of equivalence relations on classes of c.e. structures, a rich context with many natural examples, such as the isomorphism relation on c.e. graphs or on computably presented groups. In this regard, our exposition extends earlier work in the literature concerning the classification of computable structures. An abundance of open questions remain.

See Sam’s post on this article

Set-theoretic geology

Posted on by
1
  • G. Fuchs, J. D. Hamkins, and J. Reitz, “Set-theoretic geology.” (submitted)  
    Citation arχiv 
    @ARTICLE{FuchsHamkinsReitz:Set-theoreticGeology,
AUTHOR = "Gunter Fuchs and Joel David Hamkins and Jonas Reitz",
TITLE = "Set-theoretic geology",
JOURNAL = "",
YEAR = "",
volume = "",
number = "",
pages = "",
month = "",
note = "submitted",
url = "http://arxiv.org/abs/1107.4776",
eprint = "1107.4776",
abstract = "",
keywords = "",
source = "",
file = F
}

The Inner Core

A ground of the universe V is a transitive proper class W subset V, such that W is a model of ZFC and V is obtained by set forcing over W, so that V = W[G] for some W-generic filter G subset P in W . The model V satisfies the ground axiom GA if there are no such W properly contained in V . The model W is a bedrock of V if W is a ground of V and satisfies the ground axiom. The mantle of V is the intersection of all grounds of V . The generic mantle of V is the intersection of all grounds of all set-forcing extensions of V . The generic HOD, written gHOD, is the intersection of all HODs of all set-forcing extensions. The generic HOD is always a model of ZFC, and the generic mantle is always a model of ZF. Every model of ZFC is the mantle and generic mantle of another model of ZFC. We prove this theorem while also controlling the HOD of the final model, as well as the generic HOD. Iteratively taking the mantle penetrates down through the inner mantles to what we call the outer core, what remains when all outer layers of forcing have been stripped away. Many fundamental questions remain open.

 

The rigid relation principle, a new weak choice principle

Posted on by
Reply
  • J. D. Hamkins and J. Palumbo, “The rigid relation principle, a new weak choice principle,” to appear in the Mathematical Logic Quarterly.  
    Citation arχiv 
    @ARTICLE{HamkinsPalumbo:TheRigidRelationPrincipleANewWeakACPrinciple,
AUTHOR = {Joel David Hamkins and Justin Palumbo},
TITLE = {The rigid relation principle, a new weak choice principle},
JOURNAL = {to appear in the Mathematical Logic Quarterly},
YEAR = {},
volume = {},
number = {},
pages = {},
month = {},
note = {},
url = {http://arxiv.org/abs/1106.4635},
eprint = {1106.4635},
abstract = {},
keywords = {},
source = {},
}

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

This paper arose out of my related mathoverflow question:  Does every set admit a rigid binary relation (and how is this related to the axiom of choice)?

Generalizations of the Kunen inconsistency

Posted on by
2
  • J. D. Hamkins, G. Kirmayer, and N. Perlmutter, “Generalizations of the Kunen inconsistency,” to appear in the Annals of Pure and Applied Logic.  
    Citation arχiv 
    @ARTICLE{HamkinsKirmayerPerlmutter:GeneralizationsOfKunenInconsistency,
AUTHOR = {Joel David Hamkins and Greg Kirmayer and Norman Perlmutter},
TITLE = {Generalizations of the {K}unen inconsistency},
JOURNAL = {to appear in the Annals of Pure and Applied Logic},
YEAR = {},
volume = {},
number = {},
pages = {},
month = {},
note = {},
url = {http://arxiv.org/abs/1106.1951},
eprint = {1106.1951},
abstract = {},
keywords = {},
source = {},
}

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

Pointwise definable models of set theory

Posted on by
3
  • J. D. Hamkins, D. Linetsky, and J. Reitz, “Pointwise definable models of set theory,” to appear in Journal of Symbolic Logic.  
    Citation arχiv 
    @ARTICLE{HamkinsLinetskyReitz:PointwiseDefinableModelsOfSetTheory,
AUTHOR = "Joel David Hamkins and David Linetsky and Jonas Reitz",
TITLE = "Pointwise definable models of set theory",
JOURNAL = "to appear in Journal of Symbolic Logic",
YEAR = "",
volume = "",
number = "",
pages = "",
month = "",
note = "",
url = "http://arxiv.org/abs/1105.4597",
abstract = "",
keywords = "",
source = "",
eprint = "1105.4597",
file = F
}

One occasionally hears the argument—let us call it the math-tea argument, for perhaps it is heard at a good math tea—that there must be real numbers that we cannot describe or define, because there are are only countably many definitions, but uncountably many reals.  Does it withstand scrutiny?

This article provides an answer.  The article has a dual nature, with the first part aimed at a more general audience, and the second part providing a proof of the main theorem:  every countable model of set theory has an extension in which every set and class is definable without parameters.  The existence of these models therefore exhibit the difficulties in formalizing the math tea argument, and show that robust violations of the math tea argument can occur in virtually any set-theoretic context.

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

Effective Mathemematics of the Uncountable

Posted on by
4
  • Effective mathemematics of the uncountable, N. Greenberg, J. D. Hamkins, D. R. Hirschfeldt, and R. G. Miller, Ed., ASL Lecture Notes in Logic, 2011. (to appear)  
    Citation 
    @BOOK{EMU,
AUTHOR = {},
editor = {N. Greenberg and J. D. Hamkins and D. R. Hirschfeldt and R. G. Miller},
TITLE = {Effective Mathemematics of the Uncountable},
PUBLISHER = {ASL Lecture Notes in Logic},
YEAR = {2011},
volume = {},
number = {},
series = {},
address = {},
edition = {},
month = {},
note = {to appear},
abstract = {},
isbn = {},
price = {},
keywords = {},
source = {},
}

Many of the authors whose work appears in this volume were also involved in the Effective Mathematics of the Uncountable conferences EMU 2008 and EMU 2009, held at the CUNY Graduate Center.