Archive for the ‘Papers’ Category

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

Posted in Papers | 1 Comment »

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.

Posted in Papers | Leave a Comment »

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.

Posted in Papers | Leave a Comment »

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.

Posted in Papers | Leave a Comment »

Goodstein’s function

September 26, 2007

In August I gave a talk during the III jornada conjuntística at the Universidad Nacional de Colombia on Finite combinatorics and logic. The talk was based on three papers. One of them, Goodstein’s function has been accepted for publication in the Revista Colombiana de Matemáticas. You can find it in my papers page.

A discussion of Goodstein’s function and issues related to independence in {\sf PA} can be found in the page for my undecidability course in Caltech. I expect to keep updating that page from time to time.

Posted in Papers | Leave a Comment »