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.

Read the rest of this entry »


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

additions/comments/corrections/suggestions

you find appropriate. I posted a version of the note in August last year, and Grigor Sargsyan soon emailed me some comments, that I have incorporated in the current version.

[I mentioned this on Twitter last year, but apparently not here. These are the relevant links (while discussing the Münster meeting): 1, 2, 3, 4, 5.]


Downward transference of mice and universality of local core models

April 4, 2012

Martin Zeman and I have just submitted our paper Downward transference of mice and universality of local core models to the Journal of Symbolic Logic, downloadable from my papers page. We have also uploaded it on the ArXiv. (I should have been doing this for years; this is the first time I post there.)

It is a nice observation that goes back to Friedman that if 0^\sharp exists and {\mathbf M} is an inner model that correctly computes \omega_2, then 0^\sharp\in {\mathbf M}. Looking at a completely different problem, from the theory of forcing axioms, we were led to the question of how much this result can be generalized.

Our main result is that there is a significant transfer of structure going on, simply due to the agreement of cardinals. (The statement of the result and, of course, the argument, require familiarity with fine structure theory, as developed in Steel’s or Martin’s books.)

Theorem. Assume that {\mathbf M} is a proper class inner model, and that \delta is regular in {\mathbf V}.

  1. If there are no inner models of {\mathbf V} with Woodin cardinals, \delta>\omega_1, and

    \{x\in{\mathcal P}_\delta(\delta^+)\cap{\mathbf M}\mid{\rm cf}^{\mathbf M}(x\cap\delta)>\omega\}

    is stationary, then {\mathbf K}^{\mathbf M}\|\delta is universal for all iterable 1-small premice in {\mathbf V} of cardinality less than \delta.

  2. If, in {\mathbf M}, 0^\P does not exist, and {\mathcal P}_\delta(\delta^+)\cap{\mathbf M} is stationary, and \delta>\omega_1, then the same conclusion holds. If \delta=\omega_1, then {\mathbf K}^{\mathbf M}\|\omega_2 is universal for all countable iterable premice in {\mathbf V}.

Here, as usual, {\mathcal P}_\kappa(\lambda) denotes the collection of subsets of \lambda of size less than \kappa. It is easy to check that {\mathcal P}_{\omega_1} (\omega_2)\cap{\mathbf M} is stationary if {\mathbf M} computes \omega_2 correctly, so this result generalizes the statement about 0^\sharp mentioned above.

In fact, it follows that, if \omega_2 is computed correctly in {\mathbf M}, then any sound mouse in {\mathbf V} projecting to \omega and below 0^\P, is in {\mathbf M}. Beyond 0^\P, the argument becomes more complicated, and we need to assume a global anti-large cardinal assumption, namely, that there are no inner models in {\mathbf V} with Woodin cardinals.

We expect that this restriction can be weakened, perhaps even dispensed with.

(This paper is the second in a series, aiming to explore the structure of inner models for which some agreement of cardinals holds. I briefly mentioned the first paper here.)


On CH (After Hamkins)

April 2, 2012

(Wherein I quote from Twitter.)

This is my excuse to put this page to use. It all started, more or less, around here:

Moreno, Javier (bluelephant). “Es muy bueno este artículo de Hamkins sobre algo así como sociología de la teoría de conjuntos: http://arxiv.org/abs/1203.4026” 2 April 2012, 3:39 p.m. Tweet.

Villaveces, Andrés (gavbenyos). “@bluelephant lo siento bastante crudo – me parece que Joel simplemente pone en versión impresa cierto consenso, pero falta argumentar” 2 April 2012, 4:32 p.m. Tweet.

(Loosely translated: “This is a very good article by Hamkins on something akin to sociology of set theory” “I find it weak — I think that Joel is simply putting in writing a known consensus, but needs to argue for it more”) Long story short, I feel Andrés is right, but I thought I should elaborate my view, at least somewhat. Originally I considered writing a blog entry, but it quickly became apparent it would grow longer than I can afford time-wise. So, I used twitter instead.

(But there is a serious caveat, namely, it seems that the paper is intended for a general mathematical and philosophical audience, so the omission of technical issues is most likely intentional. Javier even remarked as much.)

What follows is the series of Tweets I posted. It is not a transcription; to ease reading, I have added a couple of links, reformatted the posts rather than continuing with the MLA suggested approach, very lightly edited the most obvious typos, and added a couple of phrases where I felt more clarity was needed. [Edit, April 22: I also removed a line on MM^{++} vs Woodin’s (*), as the proof of the underlying claim has been withdrawn.]

I started at 10:44 p.m., with a warning: “(Technical pseudo-philosophical thoughts for a few posts.)”

Read the rest of this entry »


Defining non-empty small sets from families of infinite sets

April 23, 2010

John Clemens, Clinton Conley, Benjamin Miller, and I have just submitted to Fundamenta Mathematicae the second part of a paper I mentioned here a while ago. The preprint is available at my papers page.

This paper deals with families of infinite sets, typically given in some definable way in the descriptive set theoretic sense. In analogy with the results in our companion paper, that deals with finite sets, we show here how in a first-order way we can define intersecting families, and how we can extract from them small sets, at least under reasonable restrictions.

These results have been in the works for a while, but it is only very recently that we have been able to state them in their current generality, thanks to recent advances due to Ben Miller. In the mean time, Richard Ketchersid and I have proved some results in models of {\sf AD}^+ (continuing the work reported here) that have also allowed the four of us to find a few extensions of the results in this paper to models of {\sf AD}^+.

Here is a sample result, a generalization of the perfect set theorem: 

Theorem. Suppose that A\subseteq\omega^\omega is \kappa-Suslin. Then either

  1. A contains a pairwise disjoint perfect subset, i.e., for any two sequences f,g in the subset, for all n we have f(n)\ne g(n), or else
  2. A is the union of \kappa many graph intersecting \kappa^+-Borel sets, i.e.,  for any two sequences f,g in any of these sets, there is some n such that f(n)=g(n).

Here, a set is \kappa-Borel iff it comes from basic open sets by taking unions and complements, where we now allow the unions to have size \kappa rather than just countable.

An interesting side effect of our arguments is that the results are provable in {\sf ZF}. We also consider a few extensions that use the axiom of choice, but have decided to indicate explicitly whenever choice is required.


BPFA and projective well-orderings of the reals

December 17, 2009

Sy Friedman and I recently submitted the paper {\sf BPFA} and projective well-orderings of the reals to The Journal of Symbolic Logic. The preprint is available at my papers page.

In a previous paper, Boban Velickovic and I showed that if {\sf BPFA}, the bounded version of the proper forcing axiom, holds, then one can define a well-ordering of the reals using what is in essence a subset C of \omega_1 as a parameter. The argument uses Justin Moore‘s technique of the Mapping Reflection Principle, and provides us with a \Delta_1(C) well-ordering. In this sense, the result is best possible. 

In earlier work, I had shown that {\sf BPFA} is consistent with a projective well-ordering of the reals. The result with Velickovic dramatically improves this; for example, if \omega_1=\omega_1^L and {\sf BPFA} holds, then there is a projective well-ordering of {\mathbb R}. Note that this is an implication rather than just a consistency result, and does not require that the universe is a forcing extension of L. The point here is that the parameter C can be chosen in L so that it is “projective in the codes,” and {\sf MA}_{\omega_1} then provides us with enough coding machinery to transform the \Delta_1(C) definition of the well-ordering into a projective one.

In the new paper, Friedman and I show that in fact under {\sf BPFA}+\omega_1=\omega_1^L, the projective definition is best possible, \Sigma^1_3. For this we need to combine the coding technique giving the \Delta_1(C) well-ordering with a powerful coding device in the absence of sharps, what Friedman calls David’s trick. The point now is that the forcing required to add the witnesses that make the coding work is proper, and {\sf BPFA} suffices to grant in the universe the existence of these objects.

As a technical problem, it would be interesting to see whether the appeal to the mapping reflection principle can be eliminated here. We only obtain a \Sigma^1_4 well-ordering in that case. Also, since {\sf BPFA} turns out, perhaps unexpectedly, to provides us with definable well-orderings, it would be interesting to see that {\sf MA}_{\omega_1} does not suffice for this.


Follow

Get every new post delivered to your Inbox.

Join 67 other followers