I shall be on sabbatical from CUNY for the 2014 – 2015 academic year, under the CUNY Fellowship Leave program, devoting myself more fully to my research. I am looking forward to a productive year. For the latter half of my leave, I shall be Visiting Professor of Philosophy at New York University.
As a guest today in my daughter’s second-grade classroom, full of math-enthusiastic seven-and-eight-year-old girls, I led a mathematical investigation of graph coloring, chromatic numbers, map coloring and Eulerian paths and circuits. I brought in a pile of sample graphs I had prepared, and all the girls made up their own graphs and maps to challenge each other. By the end each child had compiled a mathematical “coloring book” containing the results of their explorations. Let me tell you a little about what we did.
We began with vertex coloring, where one colors the vertices of a graph in such a way that adjacent vertices get different colors. We started with some easy examples, and then moved on to more complicated graphs, which they attacked.
The aim is to use the fewest number of colors, and the chromatic number of a graph is the smallest number of colors that suffice for a coloring. The girls colored the graphs, and indicated the number of colors they used, and we talked as a group in several instances about why one needed to use that many colors.
Next, the girls paired off, each making a challenge graph for her partner, who colored it, and vice versa.
Map coloring, where one colors the countries on a map in such a way that adjacent countries get different colors, is of course closely related to graph coloring.
The girls made their own maps to challenge each other, and then undertook to color those maps. We discussed the remarkable fact that four colors suffice to color any map. 
Next, we considered Eulerian paths and circuits, where one traces through all the edges of a graph without lifting one’s pencil and without retracing any edge more than once. We started off with some easy examples, but then considered more difficult cases. 
An Eulerian circuit starts and ends at the same vertex, but an Eulerian path can start and end at different vertices.
We discussed the fact that some graphs have no Eulerian path or circuit. If there is a circuit, then every time you enter a vertex, you leave it on a fresh edge; and so there must be an even number of edges at each vertex. With an Eulerian path, the starting and ending vertices (if distinct) will have odd degree, while all the other vertices will have even degree.
It is a remarkable fact that amongst connected finite graphs, those necessary conditions are also sufficient. One can prove this by building up an Eulerian path or circuit (starting and ending at the two odd-degree nodes, if there are such); every time one enters a new vertex, there will be an edge to leave on, and so one will not get stuck. If some edges are missed, simply insert suitable detours to pick them up, and again it will all match up into a single path or circuit as desired. (But we didn’t dwell much on this proof in the second-grade class.)
Meanwhile, this was an excellent opportunity to talk about The Seven Bridges of Königsberg. Is it possible to tour the city, while crossing each bridge exactly once?
The final result: a booklet of fun graph problems!
The high point of the day occurred in the midst of our graph-coloring activity when one little girl came up to me and said, “I want to be a mathematician!” What a delight!
Andrej Bauer has helped me to make available a kit of my original uncolored pages (see also post at Google+), if anyone should want to use them to make their own booklets. Just print them out, copy double-sided (with correct orientation), and fold the pages to assemble into a booklet; a few staples can serve as a binding.
See also my followup question on MathOverflow, for the grown-ups, concerning the computational difficulty of producing hard-to-color maps and graphs.
Finally, check out my new book:
$\newcommand\image{\mathrel{{}^{\prime\prime}}}$This post answers a question that had come up some time ago with Arthur Apter, and more recently with Philipp Schlicht and Arthur Apter.
Definition. A cardinal $\kappa$ is uniformly ${\lt}\theta$-supercompact if there is an embedding $j:V\to M$ having critical point $\kappa$, with $j(\kappa)>\theta$ and $M^{\lt\theta}\subset M$.
(Note: This is typically stronger than merely asserting that $\kappa$ is $\gamma$-supercompact for every $\gamma<\theta$, a property which is commonly denoted ${\lt}\theta$-supercompact, so I use the adjective “uniformly” to highlight the distinction.)
Two easy observations are in order. First, if $\theta$ is singular, then $\kappa$ is uniformly ${\lt}\theta$-supercompact if and only if $\kappa$ is $\theta$-supercompact, since the embedding $j:V\to M$ will have $j\image\lambda\in M$ for every $\lambda<\theta$, and we may assemble $j\image\theta$ from this inside $M$, using a sequence of length $\text{cof}(\theta)$. Second, in the successor case, $\kappa$ is uniformly ${\lt}\lambda^+$-supercompact if and only if $\kappa$ is $\lambda$-supercompact, since if $j:V\to M$ has $M^\lambda\subset M$, then it also has $M^{{\lt}\lambda^+}\subset M$. So we are mainly interested in the concept of uniform ${\lt}\theta$-supercompactness when $\theta$ is weakly inaccessible.
Definition. Let us say of a cardinal $\kappa$ that $\langle\mu_\lambda\mid\lambda<\theta\rangle$ is a coherent $\theta$-system of normal fine measures, if each $\mu_\lambda$ is a normal fine measure on $P_\kappa\lambda$, which cohere in the sense that if $\lambda<\delta<\theta$, then $\mu_\lambda\leq_{RK}\mu_\delta$, and more specifically $X\in\mu_\lambda$ if and only if $\{ \sigma\in P_\kappa\delta\mid \sigma\cap\lambda\in X\}\in\mu_\delta$. In other words, $\mu_\lambda=f\ast\mu_\delta$, where $f:P_\kappa\delta\to P_\kappa\lambda$ is the function that chops off at $\lambda$, so that $f:\sigma\mapsto \sigma\cap\lambda$.
Theorem. The following are equivalent, for any regular cardinals $\kappa\leq\theta$.
1. The cardinal $\kappa$ is uniformly ${\lt}\theta$-supercompact.
2. There is a coherent $\theta$-system of normal fine measures for $\kappa$.
Proof. The forward implication is easy, since if $j:V\to M$ has $M^{{\lt}\theta}\subset M$, then we may let $\mu_\lambda$ be the normal fine measure on $P_\kappa\lambda$ generated by $j\image\lambda$ as a seed, so that $X\in\mu_\lambda\iff j\image\lambda\in j(X)$. Since the seeds $j\image\lambda$ cohere as initial segments, it follows that $\mu_\lambda\leq_{RK}\mu_\delta$ in the desired manner whenever $\lambda\lt\delta<\theta$.
Conversely, fix a coherent system $\langle\mu_\lambda\mid\lambda<\theta\rangle$ of normal fine measures. Let $j_\lambda:V\to M_\lambda$ be the ultrapower by $\mu_\lambda$. Every element of $M_\lambda$ has the form $j_\lambda(f)(j\image\lambda)$. Because of coherence, we have an elementary embedding $k_{\lambda,\delta}:M_\lambda\to M_\delta$ defined by $$k_{\lambda,\delta}: j_\lambda(f)(j\image\lambda)\mapsto j_\delta(f)(j\image\lambda).$$ It is not difficult to check that these embeddings altogether form a commutative diagram, and so we may let $j:V\to M$ be the direct limit of the system, with corresponding embeddings $k_{\lambda,\theta}:M_\lambda\to M$. The critical point of $k_{\lambda,\delta}$ and hence also $k_{\lambda,\theta}$ is larger than $\lambda$. This embedding has critical point $\kappa$, and I claim that $M^{\lt\theta}\subset M$. To see this, suppose that $z_\alpha\in M$ for each $\alpha<\beta$ where $\beta<\theta$. So $z_\alpha=k_{\lambda_\alpha,\theta}(z_\alpha^*)$ for some $z_\alpha^*\in M_{\lambda_\alpha}$. Since $\theta$ is regular, we may find $\lambda<\theta$ with $\lambda_\alpha\leq\lambda$ for all $\alpha<\beta$ and also $\beta\leq\lambda$, and so without loss we may assume $\lambda_\alpha=\lambda$ for all $\alpha<\beta$. Since $M_\lambda$ is closed under $\lambda$-sequences, it follows that $\vec z^*=\langle z_\alpha^*\mid\alpha<\beta\rangle\in M_\lambda$. Applying $k_{\lambda,\theta}$ to $\vec z^*$ gives precisely the desired sequence $\vec z=\langle z_\alpha\mid\alpha<\beta\rangle$ inside $M$, showing this instance of $M^{{\lt}\theta}\subset M$. QED
The theorem does not extend to singular $\theta$.
Theorem. If $\kappa$ is $\theta$-supercompact for a singular strong limit cardinal $\theta$ above $\kappa$, then there is a transitive inner model in which $\kappa$ has a coherent system $\langle\mu_\lambda\mid\lambda<\theta\rangle$ of normal fine measures, but $\kappa$ is not uniformly ${\lt}\theta$-supercompact.
Thus, the equivalence of the first theorem does not hold generally for singular $\theta$.
Proof. Suppose that $\kappa$ is $\theta$-supercompact, where $\theta$ is a singular strong limit cardinal. Let $j:V\to M$ be a witnessing embedding, for which $\kappa$ is not $\theta$-supercompact in $M$ (use a Mitchell-minimal measure). Since $\theta$ is singular, this means by the observation after the definition above that $\kappa$ is not uniformly ${\lt}\theta$-supercompact in $M$. But meanwhile, $\kappa$ does have a coherent system of normal fine ultrafilters in $M$, since the measures defined by $X\in\mu_\lambda\iff j\image\lambda\in j(X)$ form a coherent system just as in the theorem, and the sequence $\langle\mu_\lambda\mid\lambda<\theta\rangle$ is in $M$ by $\theta$-closure. QED
The point is that in the singular case, the argument shows only that the direct limit is ${\lt}\text{cof}(\theta)$-closed, which is not the same as ${\lt}\theta$-closed when $\theta$ is singular.
The example of singular $\theta$ also shows that $\kappa$ can be ${\lt}\theta$-supercompact without being uniformly ${\lt}\theta$-supercompact, since the latter would imply full $\theta$-supercompactness, when $\theta$ is singular, but the former does not. The same kind of reasoning separates uniform from non-uniform ${\lt}\theta$-supercompactness, even when $\theta$ is regular.
Theorem. If $\kappa$ is uniformly ${\lt}\theta$-supercompact for an inaccessible cardinal $\theta$, then there is a transitive inner model in which $\kappa$ is ${\lt}\theta$-supercompact, but not uniformly ${\lt}\theta$-supercompact.
Proof. Suppose that $\kappa$ is uniformly ${\lt}\theta$-supercompact, witnessed by embedding $j:V\to M$, with $M^{\lt\theta}\subset M$, and furthermore assume that $j(\kappa)$ is as small as possible among all such embeddings. It follows that there can be no coherent $\theta$-system of normal fine measures for $\kappa$ inside $M$, for if there were, the direct limit of the associated embedding would send $\kappa$ below $j(\kappa)$, which from the perspective of $M$ is a measurable cardinal far above $\kappa$ and $\theta$. But meanwhile, $\kappa$ is $\beta$-supercompact in $M$ for every $\beta<\theta$. Thus, $\kappa$ is ${\lt}\theta$-supercompact in $M$, but not uniformly ${\lt}\theta$-supercompact, and so the notions do not coincide. QED
Meanwhile, if $\theta$ is weakly compact, then the two notions do coincide. That is, if $\kappa$ is ${\lt}\theta$-supercompact (not necessarily uniformly), and $\theta$ is weakly compact, then in fact $\kappa$ is uniformly ${\lt}\theta$-supercompact, since one may consider a model $M$ of size $\theta$ with $\theta\in M$ and $V_\theta\subset M$, and apply a weak compactness embedding $j:M\to N$. The point is that in $N$, we get that $\kappa$ is actually $\theta$-supercompact in $N$, which provides a uniform sequence of measures below $\theta$.
$\newcommand\HOD{\text{HOD}}$
I’ve recently found two slick new proofs of some of my prior results on indestructibility, using the idea of an observation of Arthur Apter’s. What he had noted is:
Observation. (Apter [1]) If $\kappa$ is a Laver indestructible supercompact cardinal, then $V_\kappa\subset\HOD$. Indeed, $V_\kappa$ satisfies the continuum coding axiom CCA.
Proof. The continuum coding axiom asserts that every set of ordinals is coded into the GCH pattern (it follows that they are each coded unboundedly often). If $x\subset\kappa$ is any bounded set of ordinals, then let $\mathbb{Q}$ be the forcing to code $x$ into the GCH pattern at regular cardinals directly above $\kappa$. This forcing is ${\lt}\kappa$-directed closed, and so by our assumption, $\kappa$ remains supercompact and in particular $\Sigma_2$-reflecting in the extension $V[G]$. Since $x$ is coded into the GCH pattern of $V[G]$, it follows by reflection that $V_\kappa=V[G]_\kappa$ must also think that $x$ is coded, and so $V_\kappa\models\text{CCA}$. QED
First, what I noticed is that this immediately implies that small forcing ruins indestructibility:
Theorem. (Hamkins, Shelah [2], Hamkins [3]) After any nontrivial forcing of size less than $\kappa$, the cardinal $\kappa$ is no longer indestructibly supercompact, nor even indestructibly $\Sigma_2$-reflecting.
Proof. Nontrivial small forcing $V[g]$ will add a new set of ordinals below $\kappa$, which will not be coded unboundedly often into the continuum function of $V[g]$, and so $V[g]_\kappa$ will not satisfy the CCA. Hence, $\kappa$ will not be indestructibly $\Sigma_2$-reflecting there. QED
This argument can be seen as essentially related to Shelah’s 1998 argument, given in [2].
Second, I also noticed that a similar idea can be used to prove:
Theorem. (Bagaria, Hamkins, Tsaprounis, Usuba [4]) Superstrong and other large cardinals are never Laver indestructible.
Proof. Suppose the superstrongness of $\kappa$ is indestructible. It follows by the observation that $V_\kappa$ satisfies the continuum coding axiom. Now force to add a $V$-generic Cohen subset $G\subset\kappa$. If $\kappa$ were superstrong in $V[G]$, then there would be $j:V[G]\to M$ with $V[G]_{j(\kappa)}=M_{j(\kappa)}$. Since $G$ is not coded into the continuum function, $M_{j(\kappa)}$ does not satisfy the CCA. This contradicts the elementarity $V_\kappa=V[G]_\kappa\prec M_{j(\kappa)}$. QED
The argument shows that even the $\Sigma_3$-extendibility of $\kappa$ is never Laver indestructible.
I would note, however, that the slick proof does not achieve the stronger result of [4], which is that superstrongness is never indestructible even by $\text{Add}(\kappa,1)$, and that after forcing to add a Cohen subset to $\kappa$ (among any of many other common forcing notions), the cardinal $\kappa$ is never $\Sigma_3$-extendible (and hence not superstrong, not weakly superstrong, and so on). The slick proof above uses indestructibility by the coding forcing to get the CCA in $V_\kappa$, and it is not clear how one would argue that way to get these stronger results of [4].
[1] Arthur W. Apter and Shoshana Friedman. HOD-supercompactness, inestructibility, and level-by-level equivalence, to appear in Bulletin of the Polish Academy of Sciences (Mathematics).
[2] Joel David Hamkins, Saharon Shelah, Superdestructibility: A Dual to Laver’s Indestructibility, J. Symbolic Logic, Volume 63, Issue 2 (1998), 549-554.
[3] Joel David Hamkins, Small forcing makes any cardinal superdestructible, J. Symbolic Logic, 63 (1998).
[4] Joan Bagaria, Joel David Hamkins, Konstantinos Tsaprounis, Toshimichi Usuba, Superstrong and other large cardinals are never Laver indestructible, to appear in the Archive of Math Logic (special issue in memory of Richard Laver).
J. D. Hamkins, A new large-cardinal never-indestructibility phenomenon, PSC-CUNY Enhanced Research Award 45, funded for 2014-2015.
Abstract. Professor Hamkins proposes to undertake research in the area of logic and foundations known as set theory, focused on the interaction of forcing and large cardinals. In a first project, he will investigate a new large cardinal non-indestructibility phenomenon, recently discovered in his joint work with Bagaria, Tsaprounis and Usuba. In a second project, continuing joint work with Cody, Gitik and Schanker, he will investigate new instances of the identity-crises phenomenon between weak compactness and other much stronger large cardinal notions.
I have been invited to give a plenary General Public Lecture at the 95th annual meeting of the American Association for the Advancement of Science (Pacific Division), which will be held in Riverside, California, June 17-20, 2014. The talk is sponsored by the BEST conference, which is meeting as a symposium at the larger AAAS conference.
This is truly a rare opportunity to communicate with a much wider community of scholars, to explain some of the central ideas and methods of set theory and the foundations of mathematics to a wider group of nonspecialist but mathematics-interested researchers. I hope to explain a little about the exciting goings-on in the foundations of mathematics. Frankly, I feel deeply honored for the opportunity to represent my field in this way.
The talk will be aimed at a very general audience, the general public of the AAAS meeting, which is to say, mainly, scientists. I also expect, however, that there will be a set-theory contingent present of participants from the BEST conference, which is a symposium at the conference — but I shall not take a stand here on whether mathematics is a science; you’ll have to come to my talk for that!
Abstract. Let me tell you the story of infinity and what is going on in the foundations of mathematics. For over a century, mathematicians have explored the soaring transfinite tower of different infinity concepts. Yet, fundamental questions at the foundation of this tower remain unsettled. Indeed, researchers in set theory and the foundations of mathematics have uncovered a pervasive independence phenomenon, whereby foundational mathematical questions are often in principle neither provable nor refutable. Presented with what may be these inherent limitations on our mathematical reasoning, we now face difficult philosophical questions on the nature of mathematical truth and the meaning of mathematical existence. Does mathematics need new axioms? Some mathematicians point the way the way towards what they describe as an ultimate theory of mathematical truth. Some adopt a scientific attitude, judging new mathematical axioms and theories by their predictions and explanatory power. Others propose a multiverse mathematical foundation with pluralist truth. In this talk, I shall take you from the basic concept of infinity and some simple paradoxes up to the continuum hypothesis and on to the higher infinity of large cardinals and the raging philosophical debates.
Slides | AAAS PD 2014 | Schedule | BEST | My other BEST talk
I will speak at the BEST conference, which is held as a symposium in the much larger 95th Annual Meeting of the American Association for the Advancement of Science, at the University of California at Riverside, June 18-20, 2014.
This talk will be for specialists in the BEST symposium.
Abstract. I shall introduce several new large cardinal concepts, namely, the strongly uplifting cardinals, the superstrongly unfoldable cardinals and the almost-hugely unfoldable cardinals, and prove their tight connection with one another — actually, they are equivalent! — as well as their equiconsistency with several natural instances of the boldface resurrection axiom, such as the boldface resurrection axiom for proper forcing. This is joint work with Thomas A. Johnstone.
I am also scheduled to give a plenary General Pubic Lecture, entitled Higher infinity and the foundations of mathematics, as a part of the larger AAAS program, to which the general public is invited.
I shall give a tutorial lecture series on Boolean ultrapowers, two or three lectures, at the BLAST conference in Las Cruces, New Mexico, January 5-9, 2015. (The big AMS meeting in San Antonio, reportedly a quick flight, begins on the 10th.)
BLAST is a conference series focusing on
B = Boolean Algebras
L = Lattices, Algebraic and Quantum Logic
A = Universal Algebra
S = Set Theory
T = Set-theoretic and Point-free Topology
In this tutorial, I shall give a general introduction to the Boolean ultrapower construction.
Boolean ultrapowers generalize the classical ultrapower construction on a power-set algebra to the context of an ultrafilter on an arbitrary complete Boolean algebra. Introduced by Vopěnka as a means of undertaking forcing constructions internally to ZFC, the method has many connections with forcing. Nevertheless, the Boolean ultrapower construction stands on its own as a general model-theoretic construction technique, and historically, researchers have come to the Boolean ultrapower concept from both set theory and model theory. An emerging interest in Boolean ultrapowers arises from a focus on well-founded Boolean ultrapowers as large cardinal embeddings.
In this tutorial, we shall see that the Boolean ultrapower construction reveals that two central set-theoretic techniques–forcing and classical ultrapowers–are facets of a single underlying construction, namely, the Boolean ultrapower. I shall provide a thorough introduction to the Boolean ultrapower construction, assuming only an elementary graduate student-level familiarity with set theory and the classical ultrapower and forcing techniques.
Article | Tutorial lecture notes | Blast 2015 | BLAST 2013 | Boolean ultrapowers tutorial at YSTW Bonn, 2011
This will be a talk for the CUNY Logic Workshop on May 2, 2014.
Abstract. I shall introduce a natural strengthening of Kelley-Morse set theory KM to the theory we denote KM+, by including a certain class collection principle, which holds in all the natural models usually provided for KM, but which is not actually provable, we show, in KM alone. The absence of the class collection principle in KM reveals what can be seen as a fundamental weakness of this classical theory, showing it to be less robust than might have been supposed. For example, KM proves neither the Łoś theorem nor the Gaifman lemma for (internal) ultrapowers of the universe, and furthermore KM is not necessarily preserved, we show, by such ultrapowers. Nevertheless, these weaknesses are corrected by strengthening it to the theory KM+. The talk will include a general elementary introduction to the various second-order set theories, such as Gödel-Bernays set theory and Kelley-Morse set theory, including a proof of the folklore fact that KM implies Con(ZFC). This is joint work with Victoria Gitman and Thomas Johnstone.
I shall be very pleased to speak at the colloquium and workshop Infinity, computability, and metamathematics, celebrating the 60th birthdays of Peter Koepke and Philip Welch, held at the Hausdorff Center for Mathematics May 23-25, 2014 at the Universität Bonn. My talk will be the Friday colloquium talk, for a general mathematical audience.
Abstract. I shall give a general introduction to the theory of infinite games, using infinite chess—chess played on an infinite edgeless chessboard—as a central example. Since chess, when won, is won at a finite stage of play, infinite chess is an example of what is known technically as an open game, and such games admit the theory of transfinite ordinal game values. I shall exhibit several interesting positions in infinite chess with very high transfinite game values. The precise value of the omega one of chess is an open mathematical question.
Slides | Schedule | Transfinite game values in infinite chess | The mate-in-n problem of infinite chess is decidable
[bibtex key=HamkinsJohnstone2017:StronglyUpliftingCardinalsAndBoldfaceResurrection]
Abstract. We introduce the strongly uplifting cardinals, which are equivalently characterized, we prove, as the superstrongly unfoldable cardinals and also as the almost hugely unfoldable cardinals, and we show that their existence is equiconsistent over ZFC with natural instances of the boldface resurrection axiom, such as the boldface resurrection axiom for proper forcing.
The strongly uplifting cardinals, which we introduce in this article, are a boldface analogue of the uplifting cardinals introduced in our previous paper, Resurrection axioms and uplifting cardinals, and are equivalently characterized as the superstrongly unfoldable cardinals and also as the almost hugely unfoldable cardinals. In consistency strength, these new large cardinals lie strictly above the weakly compact, totally indescribable and strongly unfoldable cardinals and strictly below the subtle cardinals, which in turn are weaker in consistency than the existence of $0^\sharp$. The robust diversity of equivalent characterizations of this new large cardinal concept enables constructions and techniques from much larger large cardinal contexts, such as Laver functions and forcing iterations with applications to forcing axioms. Using such methods, we prove that the existence of a strongly uplifting cardinal (or equivalently, a superstrongly unfoldable or almost hugely unfoldable cardinal) is equiconsistent over ZFC with natural instances of the boldface resurrection axioms, including the boldface resurrection axiom for proper forcing, for semi-proper forcing, for c.c.c. forcing and others. Thus, whereas in our prior article we proved that the existence of a mere uplifting cardinal is equiconsistent with natural instances of the (lightface) resurrection axioms, here we adapt both of these notions to the boldface context.
Definitions.
Remarkably, these different-seeming large cardinal concepts turn out to be exactly equivalent to one another. A cardinal $\kappa$ is strongly uplifting if and only if it is superstrongly unfoldable, if and only if it is almost hugely unfoldable. Furthermore, we prove that the existence of such a cardinal is equiconsistent with several natural instances of the boldface resurrection axiom.
Theorem. The following theories are equiconsistent over ZFC.
I shall speak at the Rutgers Logic Seminar on April 21, 2014, 5:00-6:20 pm, Room 705, Hill Center, Busch Campus, Rutgers University.
Abstract. I will show that large cardinals, such as measurable, strong and supercompact cardinals, need not exhibit their large cardinal nature in HOD. Specifically, it is relatively consistent that a supercompact cardinal is not weakly compact in HOD, and one may construct models with a proper class of supercompact cardinals, none of them weakly compact in HOD. This is current joint work with Cheng Yong.
I should like to give a brief account of the argument that KM implies Con(ZFC) and much more. This argument is well-known classically, but unfortunately seems not to be covered in several of the common set-theoretic texts.
First, without giving a full formal axiomatization, let us review a little what KM is. (And please see Victoria Gitman’s post on variant axiomatizations of KM.) In contrast to Zermelo-Frankael (ZFC) set theory, which has a purely first-order axiomatization, both Kelley-Morse (KM) set theory and Gödel-Bernays (GBC) set theory are formalized in the second-order language of set theory, where we have two sorts of objects, namely sets and classes, in addition to the usual set membership relation $\in$. A model of KM will have the form $\langle M,{\in^M},S\rangle$, where $M$ is the collection of sets in the model, and $S$ is a collection of classes in the model; each class $A\in S$ is simply the subset of $M$. Both KM and GBC will imply that $\langle M,{\in^M}\rangle$ is a model of ZFC. Both GBC and KM assert the global choice principle, which asserts that there is a class that is a well-ordering of all the sets (or equivalently that there is a class bijection of all the sets with the class of ordinals). Beyond this, both GBC and KM have a class comprehension principle, asserting that for certain formulas $\varphi$, having finitely many set and class parameters, that $\{x \mid \varphi(x)\}$ forms a class. In the case of GBC, we have this axiom only for $\varphi$ having only set quantifiers, but in KM we also allow formulas $\varphi$ that have quantification over classes (which are interpreted in the model by quanfying over $S$). Both theories also assert that the intersection of a class with a set is a set (which amounts to the separation axiom, and this follows from replacement anyway). In addition, both GBC and KM have a replacement axiom, asserting that if $u$ is a set, and for every $a\in u$ there is a unique set $b$ for which $\varphi(a,b)$, where $\varphi$ has finitely many class and set parameters, then $\{ b\mid \exists a\in u\, \varphi(a,b)\}$ is a set. In the case of GBC, we have the replacement axiom only when all the quantifiers of $\varphi$ are first-order quantifiers only, quantifying only over sets, but in KM we allow $\varphi$ to have second-order quantifiers. Thus, both GBC and KM can be thought of as rather direct extensions of ZFC to the second-order class context, but KM goes a bit further by applying the ZFC axioms also in the case of the new second-order properties that become available in that context, while GBC does not.
The theorem I want to discuss is:
Theorem. KM proves Con(ZFC).
Indeed, ultimately we’ll show in KM that there is transitive model of ZFC, and furthermore that the universe $V$ is the union of an elementary chain of elementary rank initial segments $V_\theta\prec V$, each of which, in particular, is a transitive model of ZFC.
We’ll prove it in several steps, which will ultimately reveal stronger results and a general coherent method and idea.
KM has a truth predicate for first-order truth. The first step is to argue in KM that there is a truth predicate Tr for first-order truth, a class of pairs $(\varphi,a)$, where $\varphi$ is a first-order formula in the language of set theory and $a$ is an assignment of the free variabes of $\varphi$ to particular sets, such that the class Tr gets the right answer on the quantifier-free formulas and obeys the recursive Tarskian truth conditions for Boolean combinations and first-order quantification, that is, the conditions explaining how the truth of a formula is determined from the truth of its immediate subformulas.
To construct the truth predicate, begin with the observation that we may easily define, even in ZFC, a truth predicate for quantifier-free truth, and indeed, even first-order $\Sigma_n$ truth is $\Sigma_n$-definable, for any meta-theoretic natural number $n$. In KM, we may consider the set of natural numbers $n$ for which there is a partial truth predicate $T$, one which is defined only for first-order formulas of complexity at most $\Sigma_n$, but which gives the correct answers on the quantifier-free formulas and which obeys the Tarskian conditions up to complexity $\Sigma_n$. The set of such $n$ exists, by the separation axiom of KM, since we can define it by a property in the second-order language (this would not work in GBC, since there is a second-order quantifier asking for the existence of the partial truth predicate). But now we simply observe that the set contains $n=0$, and if it contains $n$, then it contains $n+1$, since from any $\Sigma_n$ partial truth predicate we can define one for $\Sigma_{n+1}$. So by induction, we must have such truth predicates for all natural numbers $n$. This inductive argument really used the power of KM, and cannot in general be carried out in GBC or in ZFC.
A similar argument shows by induction that all these truth predicates must agree with one another, since there can be no least complexity stage where they disagree, as the truth values at that stage are completely determined via the Tarski truth conditions from the earlier stage. So in KM, we have a unique truth predicate defined on all first-order assertions, which has the correct truth values for quantifier-free truth and which obeys the Tarskian truth conditions.
The truth predicate Tr agrees with actual truth on any particular assertion. Since the truth predicate Tr agrees with the actual truth of quantifier-free assertions and obeys the Tarskian truth conditions, it follows by induction in the meta-theory (and so this is a scheme of assertions) that the truth predicate that we have constructed agrees with actual truth for any meta-theoretically finite assertion.
The truth predicate Tr thinks that all the ZFC axioms are all true. Here, we refer not just to the truth of actual ZFC axioms (which Tr asserts as true by the previous paragraph), but to the possibly nonstandard formulas that exist inside our KM universe. We claim nevertheless that all such formulas the correspond to an axiom of ZFC are still decreed true by the predicate Tr. We get all the easy axioms by the previous paragraph, since those axioms are true under KM. It remains only to verify that Tr asserts as true all instances of the replacement axiom. For this, suppose that there is a set $u$, such that Tr thinks every $a\in u$ has a unique $b$ for which Tr thinks $\varphi(a,b)$. But now by KM (actually we need only GB here), we may apply the replacement axiom with Tr a predicate, to find that $\{ b\mid \exists a\in u\, \text{Tr thinks that} \varphi(a,b)\}$ is a set, whether or not $\varphi$ is an actual finite length formula in the metatheory. It follows that Tr will assert this instance of replacement, and so Tr will decree all instances of replacement as being true.
KM produces a closed unbounded tower of transitive models of ZFC. This is the semantic approach, which realizes the universe as the union of an elementary chain of elementary substructures $V_\theta$. Namely, by the reflection theorem, there is a closed unbounded class of ordinals $\theta$ such that $\langle V_\theta,{\in},\text{Tr}\cap V_\theta\rangle\prec_{\Sigma_1}\langle V,{\in},\text{Tr}\rangle$. (We could have used $\Sigma_2$ or $\Sigma_{17}$ here just as well.) It follows that $\text{Tr}\cap V_\theta$ fulfills the Tarskian truth conditions on the structure $\langle V_\theta,\in\rangle$, and therefore agrees with the satisfaction in that structure. It follows that $V_\theta\prec V$ for first-order truth, and since ZFC was part of what is asserted by Tr, we have produced here a transitive model of ZFC. More than this, what we have is a closed unbounded class of ordinals $\theta$, which form an elementary chain $$V_{\theta_0}\prec V_{\theta_1}\prec\cdots\prec V_\lambda\prec\cdots,$$ whose union is the entire universe. Each set in this chain is a transitive model of ZFC and much more.
An alternative syntactic approach. We could alternatively have reasoned directly with the truth predicate as follows. First, the truth predicate is complete, and contains no contradictions, simply because part of the Tarskian truth conditions are that $\neg\varphi$ is true according to Tr if and only if $\varphi$ is not true according to Tr, and this prevents explicit contradictions from ever becoming true in Tr, while also ensuring completeness. Secondly, the truth predicate is closed under deduction, by a simple induction on the length of the proof. One must verify that certain logical validities are decreed true by Tr, and then it follows easily from the truth conditions that Tr is closed under modus ponens. The conclusion is that the theory asserted by Tr contains ZFC and is consistent, so Con(ZFC) holds. Even though Tr is a proper class, the set of sentences it thinks are true is a complete consistent extension of ZFC, and so Con(ZFC) holds. QED
The argument already shows much more than merely Con(ZFC), for we have produced a proper class length elementary tower of transitive models of ZFC. But it generalizes even further, for example, by accommodating class parameters. For any class $A$, we can construct in the same way a truth predicate $\text{Tr}_A$ for truth in the first-order language of set theory augmented with a predicate for the class $A$.
In particular, KM proves that there is a truth predicate for truth-about-truth, that is, for truth-about-Tr, and for truth-about-truth-about-truth, and so on, iterating quite a long way. (Of course, this was also clear directly from the elementary tower of transitive models.)
The elementary tower of transitive elementary rank initial segments $V_\theta\prec V$ surely addresses what is often seen as an irritating limitation of the usual reflection theorem in ZFC, that one gets only $\Sigma_n$-reflection $V_\theta\prec_{\Sigma_n} V$ rather than this kind of full reflection, which is what one really wants in a reflection theorem. The point is that in KM we are able to refer to our first-order truth predicate Tr and overcome that restriction.
Doesn’t the existence of a truth predicate violate Tarski’s theorem on the non-definability of truth? No, not here, since the truth predicate Tr is not definable in the first-order language of set theory. Tarski’s theorem asserts that there can be no definable class (even definable with set parameters) that agrees with actual truth on quantifier-free assertions and which satisfies the recursive Tarskian truth conditions. But nothing prevents having some non-definable class that is such a truth predicate, and that is our situation here in KM.
Although the arguments here show that KM is strictly stronger than ZFC in consistency strength, it is not really very much stronger, since if $\kappa$ is an inaccessible cardinal, then it is not difficult to argue in ZFC that $\langle V_\kappa,\in,V_{\kappa+1}\rangle$ is a model of KM. Indeed, there will be many smaller models of KM, and so the consistency strength of KM lies strictly between that of ZFC, above much of the iterated consistency hierarchy, but below that of ZFC plus an inaccessible cardinal.
This will be a talk for the CUNY Set Theory Seminar, January 31, 2014, 10:00 am.
Abstract. I will demonstrate that a large cardinal need not exhibit its large cardinal nature in HOD. I will begin with the example of a measurable cardinal that is not measurable in HOD. After this, I will describe how to force a more extreme divergence. For example, among other possibilities, it is relatively consistent that there is a supercompact cardinal that is not weakly compact in HOD. This is very recent joint work with Cheng Yong.
This will be an invited talk at the ASL 2014 North American Annual Meeting (May 19-22, 2014) in the special session Set Theory in Honor of Rich Laver, organized by Bill Mitchell and Jean Larson.
Abstract. The large cardinal indestructibility phenomenon, discovered by Richard Laver with his seminal result on supercompact cardinals, is by now often seen as pervasive in the large cardinal hierarchy. Nevertheless, a new never-indestrucible phenomenon has emerged. Superstrong cardinals, for example, are never Laver indestructible. Similarly, almost huge cardinals, huge cardinals, superhuge cardinals, rank-into-rank cardinals, extendible cardinals, 1-extendible cardinals, 0-extendible cardinals, weakly superstrong cardinals, uplifting cardinals, pseudo-uplifting cardinals, superstrongly unfoldable cardinals, $\Sigma_n$-reflecting cardinals, $\Sigma_n$-correct cardinals and $\Sigma_n$-extendible cardinals (all for $n\geq 3$) are never Laver indestructible. The proof involves a detailed technical analysis of the complexity of the definition in Laver’s theorem on the definability of the ground model, thereby involving and extending results in set-theoretic geology. This is joint work between myself and Joan Bagaria, Kostas Tasprounis and Toshimichi Usuba.