## Coloring the n-smooth numbers with n colors

February 5, 2019

Péter Pál Pach, my former master’s student Thomas A. C. Chartier and myself have just submitted our paper Coloring the $n$-smooth numbers with $n$ colors. Meanwhile, you can access it through my papers page, or at the ArXiv.

The paper discusses the current status of a question asked by Pach around 10 years ago. I found out about the problem when Dömötör Pálvölgyi asked about it on MathOverflow. Chartier was my master’s student at Boise State and I suggested to him to work on this problem. His thesis covers the results we obtained in the process, see here. At some point I thought it seemed reasonable to publish the current partial results and contacted Pach to check whether he was indeed the originator of the problem. He mentioned he was thinking of doing the same, so we decided to exchange notes and expand what we had, and this paper is the result.

The question is the following: given $n$, can we color the positive integers using precisely $n$ colors in such a way that for any $a$, the numbers $a,2a,\dots,na$ all receive different colors?

The problem remains open in this generality. We discuss the cases where a positive answer is known and several related problems. The results involve combinatorics, number theory and group theory. We also discuss a nice reformulation in terms of tilings that ends up being quite helpful.

## Inner-model reflection principles

February 2, 2019

Typical reflection principles in set theory are concerned with the height of the universe, or the relative height of certain stages. The resemblance between stages or between the universe itself and some of these stages is a very useful guiding principle that serves us to motivate large cardinal statements and many consequences of forcing axioms.

It is natural to wonder about similar reflection principles concerned instead with the width of the universe. In our paper Inner-model reflection principlesNeil BartonGunter FuchsJoel David HamkinsJonas ReitzRalf Schindler and I consider precisely this kind of reflection. Say that the inner-model reflection principle holds if and only if for any set $a$, any first-order property $\varphi(a)$ true in the universe already holds in some proper inner model containing $a$ as an element.

We establish the consistency of the principle relative to ZFC. In fact, we build a model of the stronger ground-model reflection principle, where we further require that any such first-order $\varphi(a)$ reflects to a ground of $V$, that is, an inner model $W$ with $a\in W$ such that $V$ is a set-generic extension of $W$. A formal advantage of this principle is that, using results in what we now call set-theoretic geology, ground-model reflection is formalizable as a first-order schema. Inner-model reflection, on the other hand, seems to genuinely require a second-order formalization. It is still open whether this is indeed the case, in our paper we explain some of the difficulties in showing this.

The paper studies the principle under large cardinals and forcing axioms, and compares it with other statements considered in recent years, such as the maximality principle or the inner model hypothesis. The most technically involved and interesting results in the paper show that inner-model reflection and even ground-model reflection hold in certain fine-structural inner models but also that this requires large cardinals, and that the large cardinal requirements differ for both principles (precisely a proper class of Woodin cardinals is needed for ground-model reflection).

Curiously, the paper started as a series of informal exchanges in response to a question on math.stackexchange.

See also here. The paper will appear in Studia Logica. Meanwhile, it can be accessed on the arXiv, or in my papers page.

## Topological Ramsey numbers and countable ordinals

February 1, 2019

Paul Erdős and Eric Milner published in 1972 A theorem in the partition calculus, where they established that if $\beta$ is a countable ordinal and $n\in\omega$, then there is a countable ordinal $\alpha$ such that

$\alpha\to(\beta,n)^2,$

meaning that any graph whose set of vertices is $\alpha$ either contains a clique (complete subgraph) whose set of vertices $H$ has order type $\beta$ or an independent set of size $n$.

The result is false if $n$ is replaced by $\omega$, except for when $\beta=\omega$, in which case we can take $\alpha=\omega$ as well, this is Ramsey’s theorem.

The least $\alpha$ such that $\alpha\to(\omega+1,\omega)^2$ is $\alpha=\omega_1$, in which case a stronger result holds, namely $\omega_1\to(\omega_1,\omega+1)^2$. In fact, more is true: the homogeneous set $H$ of order type $\omega_1$ can be taken to be a stationary subset of $\omega_1$, and the set of type $\omega+1$ can be required to be closed, meaning that its $\omega$th member is the supremum of the other members of the set. Since stationary sets contain closed subsets of any countable order type, we see that $\omega_1\to_{cl}(\beta,\omega+1)^2$ holds for any countable ordinal $\beta$, where the subindex cl indicates that the sets of vertices of type $\beta$ or $\omega+1$ are required to be closed on their supremum.

It is thus natural to wonder whether a closed version of the Erdős-Milner theorem holds. Jacob Hilton and I establish precisely this result in our paper Topological Ramsey numbers and countable ordinals.

This was a problem I had been curious about for a while, but kept not finding time to investigate. Finally I found a student at Boise State interested in working on this question for their master’s thesis, which gave me the perfect excuse to think seriously about it. I wrote a series of detailed notes for my student, who ended up leaving the program early, so I decided to continue and turn the notes into a paper. I even gave a preliminary talk on the results I had, together with some other results on the partition calculus of small countable ordinals. Hilton was a graduate student at that point, and he contacted me when he found out I was studying the problem, since this was precisely the topic of his dissertation. We decided to combine what we had, and soon we managed to extend our results and solve the full problem.

Many questions remain, as we believe the general bounds we found can be significantly improved, and it seems interesting to compute the optimal value of $\alpha$ such that $\alpha\to_{cl}(\beta,n)^2$ for specific values of $\beta<\omega_1$ and $n<\omega$. Omer Mermelstein has some striking results in this direction.

Our paper appeared in Foundations of Mathematics, the proceedings of the conference in honor of Hugh Woodin’s 60th birthday. It can also be found on the arXiv and on my papers page.

## Partiti

February 1, 2019

Partiti is a puzzle created by Thinh Van Duc Lai, a Vietnamese puzzle enthusiast most of whose puzzles involve mathematics in some form. His work has been featured in The New York Times, see here. Partiti puzzles appeared on Mathematics Magazine throughout 2018.

Brittany Shelton and I coauthored a short piece introducing the puzzle to the Magazine readers at the invitation of Michael Jones, the magazine editor and a colleague at Mathematical Reviews. It is titled Of puzzles and partitions. Introducing Partiti, and can be found on the arXiv or through my papers page.

## The fourteen Victoria Delfino problems and their status in the year 2019

February 1, 2019

The Cabal seminar in southern California was instrumental to the development of determinacy. The Delfino problems were suggested as a way to measure progress on this area. Fourteen problems were suggested in total through the years. Some were solved very quickly after their proposal, a few remain open.

Benedikt Löwe and I wrote a survey of their current status, cleverly titled The fourteen Victoria Delfino problems and their status in the year 2019. The cleverness has forced us to keep changing its title as its publication date kept being postponed. It is scheduled to appear in the fourth volume of the reissued Cabal volumes, which I am told is expected to finally be published this year. The volumes are being published by the Association for Symbolic Logic and Cambridge University Press as part of the Lecture Notes in Logic series.

The survey can be accessed through the Hamburger Beiträge zur Mathematik preprint server; it is paper 770 there. It can also be found through my papers page (currently under notes, and later on, once it appears, under papers).

## On anti-foundation and coding the hereditarily finite sets

August 27, 2016

I would like to highlight a cute question in a recent paper,

MR3400774
Giovanna D’Agostino, Alberto Policriti, Eugenio G. Omodeo, and Alexandru I. Tomescu.
Mapping sets and hypersets into numbers.
Fund. Inform. 140 (2015), no. 3-4, 307–328.

Recall that W. Ackermann verified what in modern terms we call the bi-interpretability of $\mathsf{ZFfin}$ and $\mathsf{PA}$, where the latter is (first-order) Peano arithmetic, and the former is finite set theory, the result of replacing in $\mathsf{ZF}$ the axiom of infinity with its negation (and with foundation formulated as the schema of $\in$-induction). The reference is

MR1513141
Wilhelm Ackermann.
Die Widerspruchsfreiheit der allgemeinen Mengenlehre.
Math. Ann. 114 (1937), no. 1, 305–315.

I have written about this before. Briefly, one exhibits (definable) translations between the collection $\mathsf{HF}$ of hereditarily finite sets and $\mathbb{N},$ and verifies that the translation extends to a definable translation of the relations, functions and constants of the language of each structure in a way that $\mathsf{PA}$ verifies that $\mathsf{ZFfin}$ holds in the translation of $(\mathsf{HF},\in),$ and $\mathsf{ZFfin}$ verifies that $\mathsf{PA}$ holds in the translation of ${\mathbb N}=(\omega,+,\times,<,0,1)$. Recall that $\mathsf{HF}$ consists of those sets $a$ whose transitive closure is finite, that is, $a$ is finite, and all its elements are finite, and all the elements of its elements are finite, and so on. Using foundation, one easily verifies that $\mathsf{HF}=V_\omega=\bigcup_{n\in\omega}V_n$, that is, it is the collection of sets resulting from iterating the power-set operation (any finite number of times) starting from the empty set.

In the direction relevant here, one defines a map $h:\mathsf{HF}\to\mathbb{N}$ by

$h(a)=\sum_{b\in a}2^{h(b)}.$

One easily verifies, using induction on the set-theoretic rank of the sets involved, that this recursive definition makes sense and is injective (and, indeed, bijective).

Of course this argument uses foundation. In the D’Agostino-Policriti-Omodeo-Tomescu paper they consider instead the theory resulting from replacing foundation with the  anti-foundation axiom, and proceed to describe a suitable replacement for $h$ that injects (codes) $\mathsf{HF}$ into the real numbers. They do quite a bit more in the paper but, for the coding itself, I highly recommend the nice review by Randall Holmes in MathSciNet, linked to above.

The anti-foundation axiom $\mathsf{AFA}$ became known thanks to the work of Peter Aczel, and it is his formulation that I recall below, although it was originally introduced in work of Forti and Honsell from 1983, where they call it $X_1$. Aczel’s presentation appears in the excellent book

MR0940014 (89j:03039)
Peter Aczel.
Non-well-founded sets. With a foreword by Jon Barwise.
CSLI Lecture Notes, 14. Stanford University, Center for the Study of Language and Information, Stanford, CA, 1988. xx+137 pp.
ISBN: 0-937073-22-9.

The original paper is

MR0739920 (85f:03054)
Marco Forti, Furio Honsell.
Set theory with free construction principles.
Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4) 10 (1983), no. 3, 493–522.

Given a binary relation $R$, its field $\mathrm{fld}(R)$ is the union of its domain and codomain. A decoration of $R$ is a function $d:\mathrm{fld}(R)\to V$ satisfying

$d(x)=\{d(y)\mid y\mathrel{R}x\}$

for all $x,y\in\mathrm{fld}(R)$. When $R$ is $\in$ and the sets in question are well-founded, the only decoration is the identity. Similarly, any well-founded relation $R$ admits a unique decoration. Define $\mathsf{AFA}$ as the statement that any binary $R$ (whether well-founded or not) admits a unique decoration.

In $\mathsf{ZF}$ with foundation replaced with $\mathsf{AFA}$ one can prove the existence of many non-well-founded sets. One of the appealing aspects of $\mathsf{AFA}$ is that the resulting univere is actually quite structured: Other anti-foundation axioms allow the existence of infinitely many Quine atoms, sets $x$ such that $x=\{x\}$, for instance. Under $\mathsf{AFA}$, there is exactly one such $x$, usually called $\Omega$. The axiom is sometimes described as saying that it provides solutions to many “equations” among sets. For instance, consider the system of equations $x=\{y\}$ and $y=\{x\}$. Under $\mathsf{AFA}$ the system has $x=y=\Omega$ as its unique solution. Note that assuming $\mathsf{AFA}$, $\Omega$ is in $\mathsf{HF}$, as are many other non-well-founded sets.

Here is the open question from the D’Agostino-Policriti-Omodeo-Tomescu paper: Work in set theory with $\mathsf{AFA}$ instead of foundation. Is there a unique, injective, function $h:\mathsf{HF}\to \mathbb{R}$  satisfying

$h(x)=\sum_{y\in x}2^{-h(y)}$

for all $x,y\in\mathsf{HF}$?

Note that there is a unique such $h$ on the well-founded hereditarily finite sets, and it is in fact injective. In general, existence, uniqueness and injectivity of $h$ appear to be open. The claim that there is such a function $h$ is a statement about solutions of certain equations on the reals, and the claim that $h$ is unique requires moreover uniqueness of such solutions. The expectation is that $h(x)$ is transcendental for all non-well-founded hereditarily finite $x$ but, even assuming this, the injectivity of $h$ seems to require additional work.

For example, consider $x=\Omega$. The function $h$ must satisfy

$h(\Omega)=2^{-h(\Omega)}$

and, indeed $h(\Omega)=0.6411857\dots$ is the unique solution $x$ of the equation $x=2^{-x}$

I would be curious to hear of any progress regarding this problem.

## Monochromatic colorings

August 20, 2016

Caïus Wojcik and Luca Zamboni recently posted a paper on the arXiv solving an interesting problem in combinatorics on words.

http://arxiv.org/abs/1608.03519
Monochromatic factorisations of words and periodicity.
Caïus Wojcik, Luca Q. Zamboni.

I had recently learned of the problem through another paper by Zamboni and a collaborator,

MR3425965
Aldo de Luca, Luca Q. Zamboni
On prefixal factorizations of words.
European J. Combin. 52 (2016), part A, 59–73.

It is a nice result and I think it may be enjoyable to work through the argument here. Everything that follows is either straightforward, standard, or comes from these papers.

1. The problem

To make the post reasonably self-contained, I begin by recalling some conventions, not all of which we need here.

By an alphabet we simply mean a set $A$, whose elements we refer to as letters. A word $w$ is a sequence $w:N\to A$ of letters from $A$ where $N$ is a (not necessarily non-empty, not necessarily proper) initial segment of $\mathbb N$. If we denote $w_i=w(i)$ for all $i\in N$, it is customary to write the word simply as

$w_0w_1\dots$

and we will follow the convention. The empty word is typically denoted by $\Lambda$ or $\varepsilon$. By $A^*$ we denote the collection of all finite words from $A$, and $A^+=A^*\setminus \{\varepsilon\}.$ By $|x|$ we denote the length of the word $x$ (that is, the size of the domain of the corresponding function).

We define concatenation of words in the obvious way, and denote by $x_0x_1$ the word resulting from concatenating the words $x_0$ and $x_1$, where $x_0\in A^*$. This operation is associative, and we extend it as well to infinite concatenations.

If a word $w$ can be written as the concatenation of words $x_0,x_1,\dots,$

$w=x_0x_1\dots,$

we refer to the right-hand side as a factorization of $w$. If $w=xy$ and $x$ is non-empty, we say that $x$ is a prefix of $w$. Similarly, if $y$ is non-empty, it is a suffix of $w$. By $x^n$ for $n\in\mathbb N$ we denote the word resulting form concatenating $n$ copies of $x$. Similarly, $x^{\mathbb N}$ is the result of concatenating infinitely many copies.

By a coloring we mean here a function $c:A^+\to C$ where $C$ is a finite set of “colors”.

Apparently the problem I want to discuss was first considered by T.C. Brown around 2006 and, independently, by Zamboni around 2010. It is a question about monochromatic factorizations of infinite words. To motivate it, let me begin with a cute observation.

Fact. Suppose $w=w_0w_1\dots$ is an infinite word, and $c$ is a coloring. There is then a factorization

$w=px_0x_1\dots$

where all the $x_i\in A^+$ have the same color.

Proof. The proof is a straightforward application of Ramsey’s theorem: Assign to $c$ the coloring of the set $[\mathbb N]^2$ of $2$-sized subsets of $\mathbb N$ given by $d(\{i,j\})=c(w_iw_{i+1}\dots w_{j-1})$ whenever $i. Ramsey’s theorem ensures that there is an infinite set $I=\{n_0 such that all $w_{n_i}w_{n_i+1}\dots w_{n_j-1}$ with $i have the same color. We can then take $p=w_0\dots w_{n_0-1}$ and $x_i=w_{n_i}\dots w_{n_{i+1}-1}$ for all $i$. $\Box$

In the fact above, the word $w$ was arbitrary, and we obtained a monochromatic factorization of a suffix of $w$. However, without additional assumptions, it is not possible to improve this to a monochromatic factorization of $w$ itself. For example, consider the word $w=01^{\mathbb N}$ and the coloring

$c(x)=\left\{\begin{array}{cl}0&\mbox{if }0\mbox{ appears in }x,\\ 1&\mbox{otherwise.}\end{array}\right.$

If nothing else, it follows that if $w$ is an infinite word that admits a monochromatic factorization for any coloring, then the first letter of $w$ must appear infinitely often. The same idea shows that each letter in $w$ must appear infinitely often.

Actually, significantly more should be true. For example, consider the word

$w=010110111\dots 01^n0 1^{n+1}\dots,$

and the coloring

$c(x)=\left\{\begin{array}{cl}0&\mbox{if }x\mbox{ is a prefix of }w,\\1&\mbox{otherwise.}\end{array}\right.$

This example shows that in fact any such $w$ must admit a prefixal factorization, a factorization

$w=x_0x_1\dots$

where each $x_i$ is a prefix of $w$.

Problem. Characterize those infinite words $w$ with the property P that given any coloring, there is a monochromatic factorization of $w$.

The above shows that any word with property P admits a prefixal factorization. But it is easy to see that this is not enough. For a simple example, consider

$w=010^210^31\dots0^n10^{n+1}1\dots$

Consider the coloring $c$ where $c(x)=0$ if $x$ is not a prefix of $w$, $c(0)=$1, and $c(x)=2$ otherwise. If

$w=x_0x_1\dots$

is a monochromatic factorization of $w$, then $x_0=01\dots$ so $c(x_0)=2$ and each $x_i$ must be a prefix of $w$ of length at least $2$. But it is easy to see that $w$ admits no such factorization: For any $n>2$, consider the first appearance in $w$ of $0^{n+1}$ and note that none of the first $n$ zeros can be the beginning of an $x_i$, so for some $j$ we must have $x_j=01\dots 10^n$ and since $n>2$, in fact $x_j=01\dots 10^n10^n$, but this string only appears once in $w$, so actually $j=0$. Since $n$ was arbitrary, we are done.

Here is a more interesting example: The Thue-Morse word

$t=0110100110010110\dots$

was defined by Axel Thue in 1906 and became known through the work of Marston Morse in the 1920s. It is defined as the limit (in the natural sense) of the sequence $x_0,x_1,\dots$ of finite words given by $x_0=0$ and $x_{n+1}=x_n\bar{x_n}$ where, for $x\in\{0,1\}^*$, $\bar x$ is the result of replacing each letter $i$ in $x$ with $1-i$.

This word admits a prefixal factorization, namely

$t=(011)(01)0(011)0(01)(011)(01)0(01)(011)0(011)(01)0\dots$

To see this, note that the sequence of letters of $t$ can be defined recursively by $t_0=0$, $t_{2n}=t_n$ and $t_{2n+1}=1-t_n$. To see this, note in turn that the sequence given by this recursive definition actually satisfies that $t_n$ is the parity of the number of $1$s in the binary expansion of $n,$ from which the recursive description above as the limit of the $x_n$ should be clear. The relevance of this observation is that no three consecutive letters in $t$ can be the same (since $t_{2n+1}=1-t_{2n}$ for all $n$), and from this it is clear that $t$ can be factored using only the words $0$, $01$, and $011$.

But it is not so straightforward as in the previous example to check whether $t$ admits a factorization into prefixes of length larger than $1$.

Instead, I recall a basic property of $t$ and use it to exhibit an explicit coloring for which $t$ admits no monochromatic factorization.

## Ramsey theory of very small countable ordinals

November 6, 2014

I was an undergraduate student at Los Andes, from 1992 to 1996. This year, their mathematics program is turning 50. There was a conference in September to celebrate the event, and I had the honor to give one of the talks (see here for the English version of the slides).

The Faculty of Science publishes a magazine, Hipótesis, and a special edition will be devoted to the conference. I have submitted an expository paper, based on my talk.

The topic is the partition calculus of very small countable ordinals (mainly ordinals below $\omega^2$, actually). The paper reviews Ramsey’s theorem and a few finite examples, before discussing the two main results.

1.

One is an old theorem by Haddad and Sabbagh, unfortunately not well known. In 1969, they computed the Ramsey numbers $r(\omega+n,m)$ for $n,m$ finite.

Given nonzero ordinals $\alpha,\beta$, recall that $r(\alpha,\beta)$ is the least $\gamma$ such that any red-blue coloring of the edges of $K_\gamma$ either admits a red copy of $K_{\alpha}$ or a blue copy of $K_\beta$. Clearly $r(\alpha,1)=1$, $r(\alpha,\beta)\ge r(\alpha,2)=\alpha$ if $\beta\ge2$, and $r(\alpha,\beta)=r(\beta,\alpha)$, so we may as well assume that $\alpha\ge\beta>2$, and we adopt this convention in what follows.

Ramsey proved two theorems about this function in a famous 1928 paper that introduced the topic. In the notation we have just set up, his first result asserts that $r(n,m)$ is finite whenever $n,m$ are finite, and his second result states that $r(\omega,\omega)=\omega$. The computation of the numbers $r(n,m)$ is an extremely difficult, most likely unfeasible, problem, though $r$ is obviously a recursive function. We are concerned here with the values of the function when at least one of the arguments is infinite.

It turns out that $r(\omega+1,\omega)$ is already $\omega_1$. Hence, if we are interested in studying the countable values of the function $r(\alpha,\beta)$, then we must assume that either $\omega=\alpha$, in which case $r(\alpha,\beta)=\omega$ and there is nothing more to say, or else (that is, if $\alpha$ is countable and strictly larger than $\omega$) we must assume that $\beta$ is finite.

The function has been intensively studied when $\alpha$ is a limit ordinal, particularly a power of $\omega$. Here we look at the much humbler setting where $\omega<\alpha<\omega2$. Recalling that each ordinal equals the set of its predecessors, and using interval notation to describe sets of ordinals, the Haddad-Sabbagh result is as follows:

Lemma. For all positive integers $n, m$ there exists a positive integer $k\ge n, m$ such that for any red-blue coloring of the edges of $K_{[0,k)}$, and such that $K_{[0,m)}$ is blue, there is a subset $H$ of ${}[0, k)$ with $K_H$ monochromatic, and either $K_H$ is blue and $|H| = m + 1$, or else $K_H$ is red, $|H|=n+1$, and $H\cap[0,m)\ne\emptyset$.

Denote by $r_{HS}(n+1,m+1)$ the smallest number $k$ witnessing the lemma.

Theorem. If $n,m$ are positive integers, then $r(\omega +n,m)=\omega(m-1)+t$, where $r_{HS}(n+1,m)=(m-1)+t$.

The theorem was announced in 1969, but the proof never appeared. I have written a survey on the topic, including what should be the first proof in print of this result.

## Square principles in Pmax extensions

May 21, 2012

As mentioned previously, I am part of a SQuaRE (Structured Quartet Research Ensemble), “Descriptive aspects of inner model theory”. The other members of the group are Paul Larson, Grigor Sargsyan, Ralf Schindler, John Steel, and Martin Zeman. We have just submitted our paper Square principles in ${\mathbb P}_{\rm max}$ extensions to the Israel Journal of Mathematics. The paper can be downloaded form my papers page, or from the arXiv.

The forcing ${\mathbb P}_{\rm max}$ was developed by Hugh Woodin in his book The axiom of determinacy, forcing axioms, and the nonstationary ideal${\mathbb P}_{\rm max}$ belongs to $L({\mathbb R})$ and, if determinacy holds, the theory that it forces is combinatorially rich, and we do not currently know how to replicate it with traditional forcing methods.

In particular, Woodin showed that, starting with a model of ${\sf AD}_{\mathbb R}+$$\Theta$ is regular”, a strong form of determinacy, the ${\mathbb P}_{\rm max}$ extension satisfies ${\sf MM}({\mathfrak c})$, the restriction of Martin’s maximum to posets of size at most ${}|{\mathbb R}|$. It is natural to wonder to what extent this can be extended. In this paper, we study the effect of ${\mathbb P}_{\rm max}$ on square principles, centering on those that would be decided by ${\sf MM}({\mathfrak c}^+)$.

These square principles are combinatorial statements stating that a specific version of compactness fails in the universe, namely, there is a certain tree without branches. They were introduced by Ronald Jensen in his paper on The fine structure of the constructible universe. The most well known is the principle $\square_\kappa$:

Definition. Given a cardinal $\kappa$, the principle $\square_{\kappa}$ holds iff there exists a sequence $\langle C_{\alpha} \mid \alpha < \kappa^{+} \rangle$ such that for each $\alpha < \kappa^{+}$,

1. Each $C_{\alpha}$ is club in $\alpha$;
2. For each limit point $\beta$ of $C_{\alpha}$, $C_{\beta} = C_{\alpha} \cap \beta$; and
3. The order type of each $C_\alpha$ is at most $\kappa$.

For $\kappa=\omega$ this is true, but uninteresting. The principle holds in Gödel’s $L$, for all uncountable $\kappa$. It is consistent, relative to a supercompact cardinal, that it fails for all uncountable $\kappa$. For example, this is a consequence of Martin’s maximum.

Recently, the principle $\square(\kappa)$ has been receiving some attention.

Definition. Given an ordinal $\gamma$, the principle $\square(\gamma)$ holds iff there exists a sequence $\langle C_{\alpha} \mid \alpha <\gamma \rangle$ such that

1. For each $\alpha < \gamma$, each $C_{\alpha}$ is club in $\alpha$;
2. For each $\alpha<\gamma$, and each limit point $\beta$ of $C_{\alpha}$, $C_{\beta} = C_{\alpha} \cap \beta$; and
3. There is no thread through the sequence, i.e., there is no club $E\subseteq \gamma$ such that $C_{\alpha} = E \cap \alpha$ for each limit point $\alpha$ of $E$.

Using the Core Model Induction technique developed by Woodin, work of Ernest Schimmerling, extended by Steel, has shown that the statement

$2^{\aleph_1}=\aleph_2+\lnot\square(\omega_2)+\lnot\square_{\omega_2}$

implies that determinacy holds in $L({\mathbb R})$, and the known upper bounds in consistency strength are much higher.

Here are some of our results: First, if one wants to obtain $\lnot\square_{\omega_2}$ in a ${\mathbb P}_{\rm max}$ extension, one needs to start from a reasonably strong determinacy assumption:

Theorem. Assume ${\sf AD}_{\mathbb R}+$$\Theta$ is regular”, and that there is no $\Gamma \subseteq \mathcal{P}(\mathbb{R})$ such that $L(\Gamma, \mathbb{R}) \models$$\Theta$ is Mahlo in ${\sf HOD}$“. Then $\square_{\omega_{2}}$ holds in the ${\mathbb P}_{\rm max}$ extension.

This results uses a blend of fine structure theory with the techniques developed by Sargsyan on his work on hybrid mice. The assumption cannot be improved since we also have the following, the hypothesis of which are a consequence of  ${\sf AD}_{\mathbb R}+V=L({\mathcal P}({\mathbb R}))+$$\Theta$ is Mahlo in ${\sf HOD}$”.

Theorem. Assume that ${\sf AD}^+$ holds and that $\theta$ is a limit on the Solovay sequence such that that there are cofinally many $\kappa<\theta$ that are limits of the Solovay sequence and are regular in ${\sf HOD}$. Then $\square_{\omega_2}$ fails in the ${\mathbb P}_{\rm max}$ extension of ${\sf HOD}_{\mathcal{P}_{\theta}(\mathbb{R})}$.

Here, ${\mathcal P}_\alpha({\mathbb R})$ denotes the collection of subsets of ${\mathbb R}$ of Wadge rank less than $\alpha$. The Solovay sequence, introduced by Robert Solovay in The independence of ${\sf DC}$ from ${\sf AD}$, is a refinement of the definition of $\Theta$, the least ordinal $\alpha$ for which there is no surjection $f:{\mathbb R}\to\alpha$:

Definition. The Solovay sequence if the sequence of ordinals $\langle \theta_{\alpha} \mid \alpha \leq \gamma \rangle$ such that

1. $\theta_{0}$ is the least ordinal that is not the surjective image of the reals by an ordinal definable function;
2. For each $\alpha < \gamma$, $\theta_{\alpha + 1}$ is the least ordinal that is not the surjective image of the reals by a function definable from an ordinal and a set of reals of Wadge rank $\theta_{\alpha}$;
3. For each limit ordinal $\beta \leq \gamma$, $\theta_{\beta} = \sup\{\theta_{\alpha} \mid \alpha < \beta\}$; and
4. $\theta_{\gamma} = \Theta$.

The problem with the result just stated is that choice fails in the resulting model. To remedy this, we need to start with stronger assumptions. Still, these assumptions greatly improve the previous upper bounds for the consistency (with ${\sf ZFC}$) of $2^{\aleph_1}=\aleph_2+\lnot\square(\omega_2)+\lnot\square_{\omega_2}$. In particular, we now know that this theory is strictly weaker than a Woodin limit of Woodin cardinals.

Theorem. Assume that ${\sf AD}_{\mathbb R}$ holds, that $V = L(\mathcal{P}(\mathbb{R}))$, and that stationarily many elements $\theta$ of cofinality $\omega_{1}$ in the Solovay sequence are regular in ${\sf HOD}$. Then in the ${\mathbb P}_{\rm max} * {\rm Add}(\omega_{3},1)$-extension, $\square_{\omega_2}$ fails.

(The forcing ${\rm Add}(\omega_3,1)$ adds a Cohen subset of $\omega_3$. This suffices to well-order ${\mathcal P}({\mathbb R})$, and therefore to force choice. That in the resulting model we also have $2^{\aleph_1}=\aleph_2+\lnot\square(\omega_2)$ follows from prior work of Woodin.)

Finally, I think I should mention a bit of notation. In the paper, we say that $\kappa^+$ is square inaccessible iff $\square_\kappa$ fails. We also say that $\gamma$ is threadable iff $\square(\gamma)$ fails. This serves to put the emphasis on the negations of the square principles, which we feel is where the interest resides. It also solves the slight notational inconvenience of calling $\square_\kappa$ a principle that is actually a statement about $\kappa^+$.

## Determinacy and Jónsson cardinals

April 9, 2012

It is a well known result of Kleinberg that the axiom of determinacy implies that the $\aleph_n$ are Jónsson cardinals for all $n\le\omega$. This follows from a careful analysis of partition properties and the computation of ultrapowers of associated measures. See also here for extensions of this result, references, and some additional context.

Using his theory of descriptions of measures, Steve Jackson proved (in unpublished work) that, assuming determinacy, every cardinal below $\aleph_{\omega_1}$ is in fact Rowbottom. See for example these slides: 12. Woodin mentioned after attending a talk on this result that the HOD analysis shows that every cardinal is Jónsson below $\Theta$.

During the Second Conference on the Core Model Induction and HOD Mice at Münster, Jackson, Ketchersid, and Schlutzenberg reconstructed what we believe is Woodin’s argument.

I have posted a short note with the proof on my papers page. The note is hastily written, and I would appreciate any