The theory of infinite games: how to play infinite chess and win, VCU Math Colloquium, November 2014

Releasing the hordesI shall speak at the Virginia Commonwealth University Math Colloquium on November 21, 2014.

Abstract. I shall give a general introduction to the theory of infinite games, using infinite chess—chess played on an infinite chessboard stretching without bound in every direction—as a central example. Since chess, when won, is always 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, which provide a measure in a position of the distance remaining to victory. I shall exhibit several interesting positions in infinite chess with very high transfinite ordinal game values. Some of these positions involve large numbers of pieces, and the talk will include animations of infinite chess in play, with hundreds of pieces (or infinitely many) making coordinated attacks on the board. Meanwhile, the precise ordinal value of the omega one of chess is an open mathematical question.

The slides from the talk will be posted here after the talk is given.

Slides | Transfinite game values in infinite chess | The mate-in-n problem of infinite chess is decidable

The span of infinity, roundtable discussion at The Helix Center, October 2014

I shall be a panelist at The Span of Infinity, a roundtable discussion held at The Helix Center, at the New York Psychoanalytic Society & Institute, 247 E 82nd Street, on October 25, 2014, 2:30 – 4:30 pm.

The Helix Center describes the discussion topic as:

Perhaps no thing conceived in the mind has enjoyed a greater confluence of cosmological, mathematical, philosophical, psychological, and theological inquiry than the notion of the infinite. The epistemological tension between the concrete and the ideal, between the phenomenological and the ontological, is nowhere clearer in outline yet more obscure in content. These inherent paradoxes limn the vital, eternal questions we will explore about humankind’s place in the universe and the comprehensibility of existence.

The Helix Center Roundtable Series is described by:

Our roundtable format is designated the Theaetetus Table, an extempore discussion among five participants, all leaders in their respective fields, and named for the classical Greek mathematician and eponym for the Platonic dialogue investigating the nature of knowledge, who proved that there are five regular convex polyhedra, or Platonic solids. Each Theaetetus Table aspires to emulate the dialogue’s unhurried search for wisdom; and, like the five Platonic solids held to be the fundamental building blocks of the classical elements, the contributions of our five participants become the fundamental constituents of interdisciplinary insights emerging in the alchemy of the roundtable, insights that, in turn, transform the elemental thinking of those participants. The gathering of five discussants also symbolizes the five interrelated qualities of mind our interdisciplinary forums are intended to facilitate in our participants, and inculcate in our audience: curiosity, playfulness, inspiration, reflection, and wonder.

The pluralist perspective on the axiom of constructibility, MidWest PhilMath Workshop, Notre Dame, October 2014

University of Notre DameThis will be a featured talk at the Midwest PhilMath Workshop 15, held at Notre Dame University October 18-19, 2014.  W. Hugh Woodin and I will each give one-hour talks in a session on Perspectives on the foundations of set theory, followed by a one-hour discussion of our talks.

Abstract. I shall argue that the commonly held $V\neq L$ via maximize position, which rejects the axiom of constructibility V = L on the basis that it is restrictive, implicitly takes a stand in the pluralist debate in the philosophy of set theory by presuming an absolute background concept of ordinal. The argument appears to lose its force, in contrast, on an upwardly extensible concept of set, in light of the various facts showing that models of set theory generally have extensions to models of V = L inside larger set-theoretic universes.

Set-theorists often argue against the axiom of constructibility V=L on the grounds that it is restrictive, that we have no reason to suppose that every set should be constructible and that it places an artificial limitation on set-theoretic possibility to suppose that every set is constructible. Penelope Maddy, in her work on naturalism in mathematics, sought to explain this perspective by means of the MAXIMIZE principle, and further to give substance to the concept of what it means for a theory to be restrictive, as a purely formal property of the theory. In this talk, I shall criticize Maddy’s proposal, pointing out that neither the fairly-interpreted-in relation nor the (strongly) maximizes-over relation is transitive, and furthermore, the theory ZFC + `there is a proper class of inaccessible cardinals’ is formally restrictive on Maddy’s account, contrary to what had been desired. Ultimately, I shall argue that the V≠L via maximize position loses its force on a multiverse conception of set theory with an upwardly extensible concept of set, in light of the classical facts that models of set theory can generally be extended to models of V=L. I shall conclude the talk by explaining various senses in which V=L remains compatible with strength in set theory.

This talk will be based on my paper, A multiverse perspective on the axiom of constructibility.

Large cardinals need not be large in HOD

  • Y. Cheng, S. Friedman, and J. D. Hamkins, “Large cardinals need not be large in HOD.” (under review)  
    @ARTICLE{ChengFriedmanHamkins:LargeCardinalsNeedNotBeLargeInHOD,
    author = {Yong Cheng and Sy-David Friedman and Joel David Hamkins},
    title = {Large cardinals need not be large in {HOD}},
    journal = {},
    year = {},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {under review},
    eprint = {1407.6335},
    url = {\url{http://jdh.hamkins.org/large-cardinals-need-not-be-large-in-hod}},
    abstract = {},
    keywords = {},
    source = {},
    }

Abstract. We prove that large cardinals need not generally exhibit their large cardinal nature in HOD. For example, a supercompact cardinal $\kappa$ need not be weakly compact in HOD, and there can be a proper class of supercompact cardinals in $V$, none of them weakly compact in HOD, with no supercompact cardinals in HOD. Similar results hold for many other types of large cardinals, such as measurable and strong cardinals.

In this article, we prove that large cardinals need not generally exhibit their large cardinal nature in HOD, the inner model of hereditarily ordinal-definable sets, and there can be a divergence in strength between the large cardinals of the ambient set-theoretic universe $V$ and those of HOD. Our general theme concerns the questions:

Questions.

1. To what extent must a large cardinal in $V$ exhibit its large cardinal properties in HOD?

2. To what extent does the existence of large cardinals in $V$ imply the existence of large cardinals in HOD?

For large cardinal concepts beyond the weakest notions, we prove, the answers are generally negative. In Theorem 4, for example, we construct a model with a supercompact cardinal that is not weakly compact in HOD, and Theorem 9 extends this to a proper class of supercompact cardinals, none of which is weakly compact in HOD, thereby providing some strongly negative instances of (1). The same model has a proper class of supercompact cardinals, but no supercompact cardinals in HOD, providing a negative instance of (2). The natural common strengthening of these situations would be a model with a proper class of supercompact cardinals, but no weakly compact cardinals in HOD. We were not able to arrange that situation, however, and furthermore it would be ruled out by Conjecture 13, an intriguing positive instance of (2) recently proposed by W. Hugh Woodin, namely, that if there is a supercompact cardinal, then there is a measurable cardinal in HOD. Many other natural possibilities, such as a proper class of measurable cardinals with no weakly compact cardinals in HOD, remain as open questions.

CUNY talkRutgers talk | Luminy talk

A common forcing extension obtained via different forcing notions

I’d like to write about the situation that occurs in set theory when a forcing extension $V[G]=V[H]$ arises over a ground model $V$ in two different ways simultaneously, using generic filters over two different forcing notions $G\subset\mathbb{B}$ and $H\subset\mathbb{C}$. The general fact, stated in theorem 1, is that in this case, the two forcing notions are actually isomorphic on a cone $\mathbb{B}\upharpoonright b\cong\mathbb{C}\upharpoonright c$, with the isomorphism carrying the one generic filter to the other. In other words, below these respective conditions $b$ and $c$, the forcing notions and the respective generic filters are not actually different.

I have always assumed that this fact was part of the classical forcing folklore results, but it doesn’t seem to be mentioned explicitly in the usual forcing literature (it appears as lemma 25.5 in Jech’s book), and so I am writing an account of it here. Victoria Gitman and I have need of it in a current joint project. (Bob Solovay mentions in the comments below that the result is due to him, and provides a possible 1975 reference.)

Theorem 1. If $V[G]=V[H]$, where $G\subset \mathbb{B}$ and $H\subset\mathbb{C}$ are $V$-generic filters on the complete Boolean algebras $\mathbb{B}$ and $\mathbb{C}$, respectively, then there are conditions $b\in\mathbb{B}$ and $c\in\mathbb{C}$ such that $\mathbb{B}\upharpoonright b$ is isomorphic to $\mathbb{C}\upharpoonright c$ by an isomorphism carrying $G$ to $H$.

The proof will also establish the following related result, concerning the situation where one extension is merely contained in the other.

Theorem 2. If $V[H]\subset V[G]$, where $G\subset\mathbb{B}$ and $H\subset\mathbb{C}$ are $V$-generic filters on the complete Boolean algebras $\mathbb{B}$ and $\mathbb{C}$, respectively, then there are conditions $b\in\mathbb{B}$ and $c\in\mathbb{C}$ such that $\mathbb{C}\upharpoonright c$ is isomorphic to a complete subalgebra of $\mathbb{B}\upharpoonright b$.

By $\mathbb{B}\upharpoonright b$, where $b$ is a condition in $\mathbb{B}$ (that is, a nonzero element of $\mathbb{B}$), what I mean is the Boolean algebra consisting of the interval $[0,b]$ in $\mathbb{B}$, using relative complement $b-a$ as the negation of $a$. This is the complete Boolean algebra that arises when forcing with the conditions in $\mathbb{B}$ below $b$.

Proof: In order to prove theorem 2, let me assume at first only that $V[H]\subset V[G]$. It follows that $H=\dot H_G$ for some $\mathbb{B}$-name $\dot H$, and we may choose a condition $b\in G$ forcing that $\dot H$ is a $\check V$-generic filter on $\check{\mathbb{C}}$.

I claim that there is some $c\in H$ such that every $d\leq c$ has $b\wedge [\![\check d\in\dot H]\!]^{\mathbb{B}}\neq 0$. Note that every $d\in H$ has $[\![\check d\in\dot H]\!]\in G$ by the truth lemma, since $H=\dot H_G$, and so $b\wedge [\![\check d\in\dot H]\!]^{\mathbb{B}}\neq 0$ for $d\in H$. If $c\in H$ forces that every $d$ in the generic filter has that property, then indeed every $d\leq c$ has $b\wedge [\![\check d\in\dot H]\!]^{\mathbb{B}}\neq 0$ as claimed.
In other words, from the perspective of the $\mathbb{B}$ forcing, every $d\leq c$ has a nonzero possibility to be in $\dot H$.

Define $\pi:\mathbb{C}\upharpoonright c\to\mathbb{B}$ by $$\pi(d)=b\wedge [\![\check d\in\dot H]\!]^{\mathbb{B}}.$$ Using the fact that $b$ forces that $\dot H$ is a filter, it is straightforward to verify that

  • $d\leq e\implies \pi(d)\leq\pi(e)$, since if $d\leq e$ and $d\in H$, then $e\in H$.
  • $\pi(d\wedge e)=\pi(d)\wedge \pi(e)$, since $[\![\check d\in\dot H]\!]\wedge[\![\check e\in \dot H]\!]=[\![\check{(b\wedge e)}\in\dot H]\!]$.
  • $\pi(d-e)=\pi(d)-\pi(e)$, since $[\![\check{(d-e)}\in\dot H]\!]=[\![\check d\in\dot H]\!]-[\![\check e\in\dot H]\!]$.

Thus, $\pi$ is a Boolean algebra embedding of $\mathbb{C}\upharpoonright c$ into $\mathbb{B}\upharpoonright\pi(c)$.

Let me argue that this embedding is a complete embedding. Suppose that $a=\bigvee A$ for some subset $A\subset\mathbb{C}\upharpoonright c$ with $A\in V$. Since $H$ is $V$-generic, it follows that $a\in H$ just in case $H$ meets $A$. Thus, $[\![\check a\in\dot H]\!]=[\![\exists x\in\check A\, x\in \dot H]\!]=\bigvee_{x\in A}[\![\check x\in\dot H]\!]$, and so $\pi(\bigvee A)=\bigvee_{x\in A}\pi(x)$, and so $\pi$ is complete, as desired. This proves theorem 2.

To prove theorem 1, let me now assume fully that $V[G]=V[H]$. In this case, there is a $\mathbb{C}$ name $\dot G$ for which $G=\dot G_H$. By strengthening $b$, we may assume without loss that $b$ also forces that, that is, that $b$ forces $\Gamma=\check{\dot G}_{\dot H}$, where $\Gamma$ is the canonical $\mathbb{B}$-name for the generic object, and $\check{\dot G}$ is the $\mathbb{B}$-name of the $\mathbb{C}$-name $\dot G$. Let us also strengthen $c$ to ensure that $c$ forces $\dot G$ is $\check V$-generic for $\check{\mathbb{C}}$. For $d\leq c$ define $\pi(d)=[\![\check d\in\dot H]\!]^{\mathbb{B}}$ as above, which provides a complete embedding of $\mathbb{C}\upharpoonright c$ to $\mathbb{B}\upharpoonright\pi(c)$. I shall now argue that this embedding is dense below $\pi(c)$. Suppose that $a\leq \pi(c)$ in $\mathbb{B}$. Since $a$ forces $\check a\in\Gamma$ and also $\check c\in\dot H$, it must also force that there is some $d\leq c$ in $\dot H$ that forces via $\mathbb{C}$ over $\check V$ that $\check a\in\dot G$. So there must really be some $d\leq c$ forcing $\check a\in\dot G$. So $\pi(d)$, which forces $\check d\in\dot H$, will also force $\check a\in\check{\dot G}_{\dot H}=\Gamma$, and so $\pi(d)\Vdash_{\mathbb{B}}\check a\in\Gamma$, which means $\pi(d)\leq a$ in ${\mathbb{B}}$. Thus, the range of $\pi$ on $\mathbb{C}\upharpoonright c$ is dense below $\pi(c)$, and so $\pi$ is a complete dense embedding of ${\mathbb{C}}\upharpoonright c$ to ${\mathbb{B}}\upharpoonright \pi(c)$. Since these are complete Boolean algebras, this means that $\pi$ is actually an isomorphism of $\mathbb{C}\upharpoonright c$ with $\mathbb{B}\upharpoonright \pi(c)$, as desired.

Finally, note that if $d\in H$ below $c$, then since $H=\dot H_G$, it follows that $[\![\check d\in\dot H]\!]\in G$, which is to say $\pi(d)\in G$, and so $\pi$ carries $H$ to $G$ on these cones. So $\pi^{-1}$ is the isomorphism stated in theorem 1.QED

Finally, I note that one cannot get rid of the need to restrict to cones, since it could be that $\mathbb{B}$ and $\mathbb{C}$ are the lottery sums of a common forcing notion, giving rise to $V[G]=V[H]$, together with totally different non-isomorphic forcing notions below some other incompatible conditions. So we cannot expect to prove that $\mathbb{B}\cong\mathbb{C}$, and are content to get merely that $\mathbb{B}\upharpoonright b\cong\mathbb{C}\upharpoonright c$, an isomorphism below respective conditions.

Large cardinals need not be large in HOD, International Workshop on Set Theory, CIRM, Luminy, September 2014

I shall speak at the 13th International Workshop on Set Theory, held at the CIRM Centre International de Rencontres Mathématiques in Luminy near Marseille, France, September 29 to October 3, 2014. 

Abstract.  I shall prove that large cardinals need not generally exhibit their large cardinal nature in HOD. For example, a supercompact cardinal need not be weakly compact in HOD, and there can be a proper class of supercompact cardinals in $V$, none of them weakly compact in HOD, with no supercompact cardinals in HOD. Similar results hold for many other types of large cardinals, such as measurable and strong cardinals. There are many open questions.

This talk will include joint work with Cheng Yong and Sy-David Friedman.

Article | Participants

A meeting at the crossroads – science, performance and the art of possibility, panel discussion, Underground Zero Festival, Intrinsic Value Project, July 2014

I shall be a panelist at A meeting at the crossroads – science, performance and the art of possibilitya panel discussion considering the intrinsic value of Art and Science, a part of the Intrinsic Value series at the Undergroundzero Festival 2014.

Are theatre and the arts vital to life here and now? Does science creatively address the larger questions of our time? This panel will bring together distinguished scientists and theatre professionals to answer these questions. They will consider how both areas are intrinsically valuable to society and investigate the performative possibilities when the two fields overlap.

At the the Abrazo Interno Gallery, Clemente Soto Vélez, 107 Suffolk Street New York NY 10002. (Venue and Tickets) July 9 & 10, 2014, 7-8 pm.

Local properties in set theory

V_thetaSet-theoretic arguments often make use of the fact that a particular property $\varphi$ is local, in the sense that instances of the property can be verified by checking certain facts in only a bounded part of the set-theoretic universe, such as inside some rank-initial segment $V_\theta$ or inside the collection $H_\kappa$ of all sets of hereditary size less than $\kappa$. It turns out that this concept is exactly equivalent to the property being $\Sigma_2$ expressible in the language of set theory.

Theorem. For any assertion $\varphi$ in the language of set theory, the following are equivalent:

  1. $\varphi$ is ZFC-provably equivalent to a $\Sigma_2$ assertion.
  2. $\varphi$ is ZFC-provably equivalent to an assertion of the form “$\exists \theta\, V_\theta\models\psi$,” where $\psi$ is a statement of any complexity.
  3. $\varphi$ is ZFC-provably equivalent to an assertion of the form “$\exists \kappa\, H_\kappa\models\psi$,” where $\psi$ is a statement of any complexity.

Just to clarify, the $\Sigma_2$ assertions in set theory are those of the form $\exists x\,\forall y\,\varphi_0(x,y)$, where $\varphi_0$ has only bounded quantifiers. The set $V_\theta$ refers to the rank-initial segment of the set-theoretic universe, consisting of all sets of von Neumann rank less than $\theta$. The set $H_\kappa$ consists of all sets of hereditary size less than $\kappa$, that is, whose transitive closure has size less than $\kappa$.

Proof. ($3\to 2$) Since $H_\kappa$ is correctly computed inside $V_\theta$ for any $\theta>\kappa$, it follows that to assert that some $H_\kappa$ satisfies $\psi$ is the same as to assert that some $V_\theta$ thinks that there is some cardinal $\kappa$ such that $H_\kappa$ satisfies $\psi$.

($2\to 1$) The statement $\exists \theta\, V_\theta\models\psi$ is equivalent to the assertion $\exists\theta\,\exists x\,(x=V_\theta\wedge x\models\psi)$. The claim that $x\models\psi$ involves only bounded quantifiers, since the quantifiers of $\psi$ become bounded by $x$. The claim that $x=V_\theta$ is $\Pi_1$ in $x$ and $\theta$, since it is equivalent to saying that every $\theta+1$-sequence $\langle x_\alpha\mid\alpha\leq\theta \rangle$ with $x_0=\emptyset$, $x_{\alpha+1}=P(x_\alpha)$ and $x_\lambda=\bigcup_{\alpha<\lambda}x_\alpha$ for limit ordinals $\lambda$, has $x_\theta=x$; this assertion is $\Pi_1$ since all the quantifiers are bounded except for $x_{\alpha+1}=P(x_\alpha)$, which requires a universal quantifier to know that all subsets of $x_\alpha$ are in $x_{\alpha+1}$. So altogether, the assertion that some $V_\theta$ satisfies $\psi$ has complexity $\Sigma_2$ in the language of set theory.

($1\to 3$) This implication is a consequence of the following absoluteness lemma.

Lemma. (Levy) If $\kappa$ is any uncountable cardinal, then $H_\kappa\prec_{\Sigma_1} V$.

Proof. Suppose that $x\in H_\kappa$ and $V\models\exists y\,\psi(x,y)$, where $\psi$ has only bounded quantifiers. Fix some such witness $y$, which exists inside some $H_\gamma$ for perhaps much larger $\gamma$. By the Löwenheim-Skolem theorem, there is $X\prec H_\gamma$ with $\text{TC}(\{x\})\subset X$, $y\in X$ and $X$ of size less than $\kappa$. Let $\pi:X\cong M$ be the Mostowski collapse of $X$, so that $M$ is transitive, and since it has size less than $\kappa$, it follows that $M\subset H_\kappa$. Since the transitive closure of $\{x\}$ was contained in $X$, it follows that $\pi(x)=x$. Thus, since $X\models\psi(x,y)$ we conclude that $M\models \psi(x,\pi(y))$ and so hence $\pi(y)$ is a witness to $\psi(x,\cdot)$ inside $H_\kappa$, as desired. QED

Using the lemma, we now prove the remaining part of the theorem. Consider any $\Sigma_2$ assertion $\exists x\,\forall y\, \varphi_0(x,y)$, where $\varphi_0$ has only bounded quantifiers. This assertion is equivalent to $\exists\kappa\, H_\kappa\models\exists x\,\forall y\,\varphi_0(x,y)$, simply because if there is such a $\kappa$ with $H_\kappa$ having such an $x$, then by the lemma this $x$ works for all $y\in V$ since $H_\kappa\prec_{\Sigma_1}V$; and conversely, if there is an $x$ such that $\forall y\, \varphi_0(x,y)$, then this will remain true inside any $H_\kappa$ with $x\in H_\kappa$. QED

In light of the theorem, it makes sense to refer to the $\Sigma_2$ properties as the locally verifiable properties, or perhaps as semi-local properties, since positive instances of $\Sigma_2$ assertions can be verified in some sufficiently large $V_\theta$, without need for unbounded search. A truly local property, therefore, would be one such that positive and negative instances can be verified this way, and these would be precisely the $\Delta_2$ properties, whose positive and negative instances are locally verifiable.

Tighter concepts of locality are obtained by insisting that the property is not merely verified in some $V_\theta$, perhaps very large, but rather is verified in a $V_\theta$ where $\theta$ has a certain closeness to the parameters or instance of the property. For example, a cardinal $\kappa$ is measurable just in case there is a $\kappa$-complete nonprincipal ultrafilter on $\kappa$, and this is verified inside $V_{\kappa+2}$. Thus, the assertion “$\kappa$ is measurable,” has complexity $\Sigma^2_1$ over $V_\kappa$. One may similarly speak of $\Sigma^n_m$ or $\Sigma^\alpha_m$ properties, to refer to properties that can be verified with $\Sigma_m$ assertions in $V_{\kappa+\alpha}$. Alternatively, for any class function $f$ on the ordinals, one may speak of $f$-local properties, meaning a property that can be checked of $x\in V_\theta$ by checking a property inside $V_{f(\theta)}$.

This post was made in response to a question on MathOverflow.

Math for seven-year-olds: graph coloring, chromatic numbers, and Eulerian paths and circuits

Image (11)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.

Image (12)Image (13)

Image (14)Image (15)

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.

Image (16)Image (17)

Image (18)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.

Image (20)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. Image (19)

 

 

 

Image (28)-001

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. Image (29)

Image (28)-002An Eulerian circuit starts and ends at the same vertex, but an Eulerian path can start and end at different vertices.

Image (30)-001We 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.)

Image (31)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?Image (31)-001

 

 

 

 

The final result: a booklet of fun graph problems!

Graph Coloring Booklet

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.

Uniform $({\lt}\theta)$-supercompactness is equivalent to a coherent system of normal fine measures

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

Large cardinal indestructibility: two slick new proofs of prior results

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

A new large-cardinal never-indestructibility phenomenon, PSC-CUNY Enhanced Research Award, 2014-2015

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.

 

Higher infinity and the foundations of mathematics, plenary General Public Lecture, AAAS, June, 2014

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!

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