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.


A trichotomy theorem in natural models of AD+

June 30, 2009

[Updated: July 24, 2009]

Richard Ketchersid and I have submitted the paper A trichotomy theorem in natural models of {\sf AD}^+ to the Proceedings of BEST. The preprint is available at my papers page. In the paper we provide references and background for the results we discuss, so here I will only mention briefly what the paper is about.

{\sf AD}^+ is a strengthening, due to Woodin, of the more familiar axiom of determinacy. In all known models of determinacy, it is the case that in fact {\sf AD}^+ holds. Since {\sf AD}^+ is an axiom about sets of reals, its natural models are those of the form L({\mathcal P}({\mathbb R})), although there are models of {\sf AD}^+ not of this form. 

In this paper, we prove the following result:

Theorem. Assume that V=L({\mathcal P}({\mathbb R})) and that {\sf AD}^+ holds. Let (X,\le) be any partially ordered set. Then either there is an injection of the full binary tree 2^{\mathbb N} into X such that no two points in its image are \le-comparable, or else X can be written as a well-ordered union of \le-chains.

This statement should be reminiscent of the Harrington-Marker-Shelah theorem on Borel orderings, and in a sense our argument is a generalization of this result. 

Two corollaries are worth pointing out: Suppose first that \le is simply the diagonal on X. Then the theorem gives us:

Corollary. Assume that V=L({\mathcal P}({\mathbb R})) and that {\sf AD}^+ holds. Let X be a set. Then either {\mathbb R} injects into X, or else X is well-orderable.

This can be seen as a generalization of Silver’s theorem on co-analytic equivalence relation. In particular, we have the following basis result:

Corollary. Assume that V=L({\mathcal P}({\mathbb R})) and that {\sf AD}^+ holds. Then \aleph_0 injects into every infinite set, and if X is uncountable, then either \aleph_1 or {\mathbb R} injects into X.

Our arguments make use of technology developed by Woodin. First, any model of {\sf AD}^+ of the form L({\mathcal P}({\mathbb R})) either satisfies {\sf AD}_{\mathbb R} or else it has the form L(S,{\mathbb R}) for some set S of ordinals.

In the second case, one argues via an analysis of the \infty-Borel sets. Essentially, one uses what is sometimes called code compression to obtain, given an \infty-Borel code for a set A, local versions of this code, that are sufficiently absolute in that they compute traces of A correctly both in small inner models of choice, and their forcing extensions. Once this is obtained, the result essentially follows from soft forcing arguments as if the original sets under consideration were Borel. 

In the first case, one uses the argument above to see that a set X is expressible as a well-ordered union of smaller sets, for which the result applies. This uses that, under {\sf AD}_{\mathbb R}, models of the form L({\mathcal P}({\mathbb R})) are of the form {\sf OD}((<\Theta)^\omega), where (<\Theta)^\omega denotes the family of countable bounded subsets of \Theta. One then uses the uniqueness of the supercompactness measures on {\mathcal P}_{\omega_1}(\gamma) for \gamma<\Theta to “paste together” the smaller pieces that make up X in a coherent way. The idea in this case was suggested by Woodin, and it is surprisingly flexible. 

As an application, we consider the countable-finite game due to Scheepers. In this game, one fixes a set S, and two players, I and II, alternate for \omega-many moves, with I moving first, so that each move of I is a countable subset of S, and each move of II is a finite subset of S. Player II wins if and only if the union of the finite sets covers the union of the countable sets. If choice holds, it is obvious that player II has a winning strategy. The same argument shows that, without choice, player II has a winning strategy when S is countable. In contrast, we prove:

Corollary. Assume that V=L({\mathcal P}({\mathbb R})) and that {\sf AD}^+ holds. Then the countable-finite game on S is undetermined for all uncountable sets S.

For a brief presentation of these results, see the talks that Richard and I gave at BEST 18, available here or at my talks page.

(The “trichotomy” in the title refers to an additional clause in the main theorem, related to the Glimm-Effros dichotomy. I expect to post about an extension of this part of the result soon.)


Regressive functions on pairs

May 19, 2008

I recently gave a talk at the Claremont Colleges Algebra/Number Theory/Combinatorics Seminar on the topic of this paper, which can be found in my papers page.

For a set X\subseteq{\mathbb N}^2 let X^{[2]}=\{(n,m)\in X^2:n<m\}. A function f:X^{[2]}\to{\mathbb N} is regressive iff f(u_1,u_2)<u_1 for all u_1<u_2 in X with 0<u_1. A set H\subseteq X is min-homogeneous for f iff f(u,u_1)=f(u,u_2) whenever 0<u<u_1,u_2 and u,u_1,u_2\in H.

Theorem. For all n there exists m such that if X=\{1,2,\dots,m\} and f:X^{[2]}\to{\mathbb N} is regressive, then there is H\subseteq X of size at least n and min-homogeneous for f.

The theorem (due to Kanamori and McAloon) states a version of the classical Ramsey theorem for regressive functions. We cannot expect H to be homogeneous, i.e., in general f\upharpoonright H^{[2]} will not be constant. For example, consider f(u,v)=u-1. Notice also that without loss of generality 1\in H, since f(1,u)=0. It is natural to try to establish the rate of growth of the function g that to each n assigns the least m as in the theorem. Using tools of mathematical logic, as part of a more general result about regressive functions of k variables, Kanamori and McAloon showed:

Theorem. The function g grows faster than any primitive recursive function.

In my paper I show using finite combinatorics methods that g grows precisely as fast as Ackermann’s function. This is obtained as part of an analysis of a more general function g(n,k) of two variables, defined as g but with the additional requirement that {\rm min}(H)\ge k. Obviously, g(2,k)=k+1 and g(3,k)=2k+1. The situation for g(4,k) is less clear, although it is of exponential growth.

Theorem. We have:

  1. g(4,1)=5, g(4,2)=15, g(4,3)=37, g(4,4)\le85.
  2. 2g(4,m)+3\le g(4,m+1), so g(4,m)\ge 5\times 2^m-3 for m\ge3.
  3. g(4,m+1)\le 2^m(m+2)-2^{m-1}+1.

Question. Does g(4,m)\ge 2^{m-1}m hold?

Although I have not been able to prove this, I do not expect it to be particularly difficult.


Intersecting families and definability

April 12, 2008

I have made some changes to my webpage and now my papers can be found here, on a page in this blog.

I have updated my paper Defining small sets from \kappa-cc families of sets, joint with Clemens, Conley and Miller. I would like to mention one of the questions we leave open.

Consider a family {\mathcal A} of sets and let X=\bigcup{\mathcal A}. We say that {\mathcal A} is intersecting iff any two members of {\mathcal A} share at least an element of X. In our paper we are interested in how definability conditions restrict the size of intersecting families. In particular we show that, even if {\mathcal A} and X are infinite, if all the members of {\mathcal A} are finite, then from {\mathcal A} we can define a finite subset of X.

Let n be such that there is a set in {\mathcal A} of size at most n. Then our arguments also show that there is a finite intersecting family {\mathcal A}'\subseteq[X]^{\le n} definable from {\mathcal A}, and we find upper bounds on how large such {\mathcal A}' is.

Say that {\mathcal A} is n-minimal iff {\mathcal A}\subseteq[X]^{\le n} is intersecting and any intersecting {\mathcal A}'\subseteq[X]^{\le n} definable from {\mathcal A} is at least as large as {\mathcal A} itself. It follows that there is a finite bound \psi(n) on how large such a family {\mathcal A} can be.

Question. Is \psi a (strictly) increasing function?

We can show that \psi(n)<\psi(2n) and a few similar results, but whether \psi is monotone is still open.

[Update, April 23, 2010: To reflect a few recent changes that resulted in a companion paper dealing with infinite sets, we have changed the title to Defining non-empty small sets from families of finite sets.]


Cardinal preserving elementary embeddings

February 8, 2008

For a while now I have been thinking about structural restrictions that elementary embeddings must satisfy in set theory. Some of my findings were reported in Oaxaca during the XIII SLALM. An updated version of these results has been accepted for publication in the Proceedings of the Logic Coloquium 2007.  You can find it in my papers page.


Follow

Get every new post delivered to your Inbox.

Join 44 other followers