User andres caicedo - MathOverflow

Answer by Andres Caicedo for If ZFC has a transitive model, does it have one of arbitrary size?

2013-05-05T20:02:38Z

In a comment to François's answer, I point out that the least $\alpha$ such that $L_\alpha$ is a model of $\mathsf{ZFC}$ is countable. In what follows, "model" means "transitive model of $\mathsf{ZFC}$."

If $M$ is transitive, then $L^M=L_\beta\models\mathsf{ZFC}$ for $\beta=\mathsf{ORD}\cap M$, so the least height of a model is countable. Moreover, any model $M$ proves that there is a bijection between each level of its cumulative hierarchy, and one of its ordinals, so if $M$ has height $\kappa$, so is $\kappa$ its size. This proves that the existence of a model does not imply the existence of an uncountable one: If $M$ has least height, let $\alpha_0$ be least such that $L_{\alpha_0}$ is a model, and $\alpha_0$ is larger than the height of $M$ ($\alpha_0$ could be $\mathsf{ORD}$). We see that in $L_{\alpha_0}$ the height of $M$ is countable and there are no models of height larger than the height of $M$.

Asaf asked whether this generalizes, that is, whether for each $\kappa$ the existence of models of size $\kappa$ does not imply the existence of models of larger size. That this is indeed the case follows from extending the argument from the previous paragraph: Let $L_\alpha$ be a model of height (and size) $\kappa$, and let $\alpha_0$ be such that $\alpha<\alpha_0$ and $L_{\alpha_0}$ is a model. We may as well assume that $\alpha_0$ exists (that is, it is an ordinal), or else there is nothing to prove. Now let $X$ be an elementary substructure of $L_{\alpha_0}$ containing both $L_\alpha\cup{L_\alpha}$ (as a subset) and a bijection between $\alpha$ and $|\alpha|^{L_{\alpha_0}}$, and of size $\kappa$, which exists by a standard application of the Lowenheim-Skolem argument. The transitive collapse of $X$ is $L_\beta$ for some $\beta$, and has size $\kappa$. This means that if $\alpha_0$ is least (so the collapse of $X$ is again $L_{\alpha_0}$), then $L_{\alpha_0}$ is a model of $\mathsf{ZFC}$ plus the assertion that there are no set models of height (and therefore size) larger than $|\alpha|=\kappa$.

Without choice, I do not know whether models of $\mathsf{ZF}$ of height $\kappa$ must have size $\kappa$.

[Edit: In response to the last paragraph above, Joel and Asaf pointed out some results. I am including them here, to increase visibility.]

Ali Enayat. Models of set theory with definable ordinals, Arch. Math. Logic 44 (3), (2005), 363–385. MR2140616 (2005m:03098),

Ali discusses some results about transitive models of $\mathsf{ZF}$ that show that the situation is much more subtle than in the presence of choice. One of the most incredible results is due to Friedman, in

Harvey Friedman. Large models of countable height, Trans. Amer. Math. Soc. 201 (1975), 227–239. MR0416903 (54 #4966).

Let me quote from Harvey's paper:

The first examples of transitive models of $\mathsf{ZF}$ of power $\omega_1$ with countably many ordinals were constructed by Cohen. Later Easton, Solovay, and Sacks showed that every countable transitive model of $\mathsf{ZF}$ has an ordinal-preserving extension satisfying $\mathsf{ZF}$, of power $2^{\omega}$. We prove here that every countable transitive model $M$ of $\mathsf{ZF}$ has an ordinal preserving extension satisfying $\mathsf{ZF}$, of power $\beth_{M\cap\mathsf{ORD}}$.

Harvey's argument uses forcing. For his first result, given $M$ a countable transitive model of $\mathsf{ZF}$, he says that $x\subset\omega^\omega$ is $M$-generic iff any finite sequence of distinct elements of $x$ is $M$-generic (for the product of the appropriate number of copies of Cohen forcing), $x$ is infinite, and dense. The models he builds are of the form $M(x)$ so, in particular, they are transitive. He shows that there are $M$-generics $x$ of size continuum with $M(x)$ a model of $\mathsf{ZF}$ (and $M(x)$ has the same height as $M$). He then builds on the machinery introduced here, and proves that, starting with an $M$-generic $x$, a family of sets $C_\alpha$, $\alpha\lt M\cap\mathsf{ORD}$, can be found with $|C_\alpha|\ge\beth_\alpha$, and such that $M[(C_\alpha)_\alpha]$, properly defined, is a model of $\mathsf{ZF}$ of the claimed size.

Ali builds on this results to produce Paris models of $\mathsf{ZF}$, that is, models $M$ all of whose ordinals are first order definable in $M$. In prior work, he had shown that from the assumption that $L$ satisfies that there are uncountable transitive models of $\mathsf{ZFC}$, it follows that there are unboundedly many $\alpha<\omega_1^L$ such that $L_\alpha$ is Paris. He shows now that from the same assumption, we have that for every infinite $\kappa$ there are Paris models of $\mathsf{ZF}$ of size $\kappa$; this uses Harvey's result, since generic (or simply, ordinal preserving) extensions of $L_\alpha$ are Paris if $L_\alpha$ itself is Paris. It follows that there is a complete extension of $\mathsf{ZF}$ admiting in $L$ Paris models of size $\beth_\alpha$ for each countable $\alpha$. The theory, including the requirement that its models are Paris, can be described in $L_{\omega_1\omega}$. Since the Hanf number of this logic is $\beth_{\omega_1}$, the result follows.

This produces large transitive models indeed, in view of a result of Paris: If a completion $T$ of $\mathsf{ZF}$ has a well-founded model, then every Paris model of $T$ is well-founded.

(All this said, I do not understand this situation very well. It is all still rather surprising.)

Answer by Andres Caicedo for How additive is Lebesgue measure in ZF+AD ?

2010-12-07T03:53:57Z

Ricky:

I think I see how to answer the problem under a stronger assumption. Rather than $\mathsf{AD}$, work in $$ {\sf AD}^+ + V=L({\mathcal P}({\mathbb R})). $$ This is a bit unsatisfying, since it is very possible the question can be answered assuming only $\mathsf{AD}$. In any case, $\mathsf{AD}^+$ is potentially harmless, since it may be that $\mathsf{AD}$ implies $\mathsf{AD}^+$; but it seems strange to need here the additional machinery that $\mathsf{AD}^+$ allows us. The assumption on the form of $V$ is more immediately troublesome, since it actually makes some (non-well-ordered) cardinals "invisible". (Meaning, there may be cardinals $\tau$ that inject into $2^{|{\mathbb R}|}$ but not in $L({\mathcal P}({\mathbb R}))$, so our assumption is potentially simplifying the question.)

Using $\mathsf{AD}^+ + V=L({\mathcal P}({\mathbb R}))$, Richard Ketchersid and I proved (in A trichotomy theorem in natural models of ${\sf AD}^+$, in Set Theory and Its Applications, Contemporary Mathematics, 533, Amer. Math. Soc., Providence, RI, 2011, pp. 227-258) that every set either is well-orderable, or is at least as large as ${\mathbb R}$. (The paper is available here, and it also provides an introduction to $\mathsf{AD}^+$.)

Obviously, Lebesgue measure is not ${\mathbb R}$-additive, considering singletons, so this means it is enough to answer the question for well-ordered cardinals. But given a well-ordered union of sets of reals, we may assume they are pairwise disjoint (arguing inductively). And then it is standard that only countably many of them can be of positive measure. $(*)$

This shows (under the listed assumptions) that Lebesgue measure is $\kappa$-additive for all (well-orderable) $\kappa$ but not $\tau$-additive for any non-well-orderable cardinal $\tau$.

$(*)$ To see that the last paragraph follows, I need to argue that a well-ordered union of measure zero sets has measure zero. In fact, under $\mathsf{AD}$, a bit more holds, namely, $$ \iint_{[0,1]^2}f(x,y)dxdy=\iint_{[0,1]^2}f(x,y)dydx $$ for any bounded $f:[0,1]^2\to{\mathbb R}$ (in particular, the integrals are defined).

From this it is easy to conclude the claim about measure zero sets, e.g., by looking at minimal counterexamples and adapting the standard Sierpiński argument; note that this only uses $\mathsf{DC}({\mathbb R})$ (or even just $\mathsf{AC}_\omega(\mathbb R)$, which follows from $\mathsf{AD}$) and that all sets of reals are Lebesgue measurable.

(Unfortunately, although this Fubini theorem is not too hard, I am not sure of a reference for it. I remember vol. 5 of Fremlin's treatise has it as an exercise.) Let me add that this is a folklore result that is frequently used, as is the dual fact that a well-ordered union of meager sets is meager under $\mathsf{AD}$.

Answer by Andres Caicedo for Basis theorem (due to Solovay?)

2013-05-01T22:41:20Z

The result is indeed Solovay's Basis Theorem.

It is a consequence of Moschovakis's Coding Lemma, and sometimes it is referred to as (a version of) the reflection theorem (for example, in section 8 of Steel's Handbook article). Perhaps the optimal reference (it is self-contained, and easily accessible) is Section 2.4 of

Peter Koellner, and W. Hugh Woodin. Large cardinals from determinacy. In Handbook of set theory. Vols. 1, 2, 3, 1951–2119, Springer, Dordrecht, 2010.

I do not think it appears explicitly in a paper by Solovay. It should date back to 1976 at the latest, which is when Kechris and Solovay observed that not all $\Pi^2_1$ sets can be uniformized if $V=L(\mathbb R)$ and choice fails (see section 30 in Kanamori's book).

Answer by Andres Caicedo for Counterintuitive consequences of the Axiom of Determinacy?

2013-04-28T23:11:41Z

Let's see: $\mathsf{AD}$ implies that all sets of reals are Lebesgue measurable, have the Baire property, and the perfect set property (so, a version of the continuum hypothesis holds). It is conjectured that it also implies that all sets of reals are Ramsey. All these statements fail (badly) in the presence of choice.

(There is a technical strengthening of $\mathsf{AD}$ known as $\mathsf{AD}^+$ that implies that all sets of reals are Ramsey. It is open whether $\mathsf{AD}$ and this strengthening are actually equivalent.)

$\mathsf{AD}$ implies that there are no nonprincipal ultrafilters on the natural numbers. This in turn has as a corollary that every ultrafilter is $\omega_1$-complete. It is this way that the first truly dramatic consequences of determinacy were established:

Solovay showed that $\omega_1$ is measurable, and in fact the club filter on $\omega_1$ is an ultrafilter. Also, $\omega_2$ is measurable, and the restriction of the club filter to sets of cofinality $\omega$ is an $\omega_2$-complete ultrafilter. Same with cofinality $\omega_1$. On the other hand, $\omega_3,\omega_4,\dots$ are not measurable, in fact they are not even regular but have cofinality $\omega_2$. The next regular cardinal is $\omega_{\omega+1}$ which, again, is measurable. It is conjectured that the cofinality function on successor cardinals is nondecreasing below $\Theta$ under $\mathsf{AD}$. Here, $\Theta$ is the supremum of the ordinals that $\mathbb R$ can be mapped onto. Under choice, $\Theta$ is just $\mathfrak c^+$ which, under the continuum hypothesis and choice, is just $\omega_2$. However, here $\Theta$ is a large cardinal. (So, a version of the continuum hypothesis fails.)

Work from Steel and Woodin shows that, if we restrict our attention to $L(\mathbb R)$ (which is an inner model of determinacy if we assume $\mathsf{AD}$ in $V$), then every regular cardinal below $\Theta$ is measurable. This result of Steel and Woodin holds in much more generality than in $L(\mathbb R)$, but the precise statement and the arguments become rather technical. Here, one should also mention Moschovakis's covering lemma. The softest version of it is already significant: If there is a surjection from $\mathbb R$ onto an ordinal $\alpha$, then there is also a surjection from $\mathbb R$ onto $\mathcal P(\alpha)$.

A recent result of Woodin is that every cardinal below $\Theta$ is in a sense of large cardinal character. More precisely, it is Jónsson, or stronger. Again, this is easier to prove under the assumption that $V=L(\mathbb R)$, but holds in full generality. The argument can be seen in this recent preprint in the ArxiV.

The precise pattern of Jónsson cardinals under determinacy is still under investigation, but a nice place to start is the book

Eugene Kleinberg. Infinitary combinatorics and the axiom of determinateness, Lecture Notes in Mathematics 612, Springer-Verlag, Berlin-New York, 1977. MR0479903 (58 #109).

Kleinberg realized that the regular cardinals under determinacy are controlled by partition properties, and the size of certain ultrapowers. This proved key for many results that followed. Moreover, the investigation of infinite exponent partition relations became an important part of the combinatorics of $\mathsf{AD}$. Under choice every infinite exponent relation fails.

The study of non-well-orderable cardinals under $\mathsf{AD}$ is just starting, but there are already significant results, showing that many complicated partial orders can be embedded into the ordering of these cardinals. For example, in

W. Hugh Woodin. The cardinals below $|[\omega_1]^{<\omega_1}|$. Ann. Pure Appl. Logic 140 (1-3), (2006), 161–232. MR2224057 (2007k:03136),

Woodin shows that (in the theory $\mathsf{AD}(\mathbb R)+\mathsf{DC}$) one can find $\Theta$-decreasing sequences, or $\Theta$ many incomparable cardinals, and much more. Here, $\mathsf{AD}(\mathbb R)$ is the strengthening of determinacy where we allow real (rather than integer) moves in our games. In another direction, we have that under determinacy $\mathbb R$ and $\omega_1$ have incomparable cardinalities, and they are both successors of $\omega$. And the cardinality of $\mathbb R$ has several cardinal successors, one of which is the quotient $\mathbb R/\mathbb Q$, where two reals are identified iff their difference is rational. Yes: A quotient has larger size than the original set. See here for more on this.

I'll stop here, but what I've mentioned is really just scratching the surface. You may want to look at chapter 6 of Kanamori's book for more information, or at the beginning of my paper with Richard Ketchersid on a trichotomy result for additional, recent results, and some details on $\mathsf{AD}^+$.

The above being said, in the comments Douglas Zare points out that whether some of these consequences seem unintuitive depends on whether we consider choice and its consequences intuitive or not. Actually, if we are agnostic about $\mathsf{AC}$, many consequences of $\mathsf{AD}$ are natural. The idea is that the sets of reals in an $\mathsf{AD}$ model provide us with a natural class of "definable" sets, extending definability classes such as those coming from the interplay of logic and analysis (Borel or $\Delta^1_1$, projective or $\Sigma^1_n$, etc). A recent theme is that certain properties of simply definable sets of reals provable in $\mathsf{ZF}+\mathsf{DC}_{\mathbb R}$, extend to all sets of reals under determinacy. The pattern of uniformization for projective sets is a classical example of this. A striking recent development in descriptive set theory, due to Ben Miller, is that most classical dichotomy theorems in descriptive set theory are soft consequences of graph-theoretic dichotomies via Baire category arguments, see

Benjamin Miller. The graph-theoretic approach to descriptive set theory. Bulletin of Symbolic Logic, 18 (4), (2012), 554-575.

Extending the work mentioned above, Richard Ketchersid and I have shown that these graph theoretic dichotomies hold for arbitrary sets of reals under $\mathsf{AD}^+$, and therefore we have the classical dichotomies in the $\mathsf{AD}$ context without any restrictions in the complexity of the sets involved. (In fact, we have versions that apply to all sets in $L(\mathcal P(\mathbb R))$, not just to sets of reals.) Andrew Marks's answer points to some of these dichotomies. For more, see here.

Answer by Andres Caicedo for Models of Determinacy

2013-03-14T21:29:40Z

Certainly, $L(\mathbb R)$ is not a mouse (rather, a weasel) over a countable set, and the only way I see of thinking of it as a mouse and still capturing all the reals is making it a mouse over $\mathbb R$, in which case the answer is trivial. There is interesting work on $\mathbb R$-premice, but I do not think this is what you had in mind here.

More relevantly, if determinacy holds, then $L(\mathbb R)$ is a derived model, which I think is how you should think of it. There is a key relationship between models of determinacy and models with limit many Woodin cardinals, given by the derived model theorem. This is significant result. It says, on the one hand, that a symmetric extension of any model of choice with limit many Woodin cardinals results in a model of $\mathsf{AD}^+$. On the other hand, by an appropriate use of Prikry forcing, one can weave together $\mathsf{HOD}$-like models inside models of $\mathsf{AD}^+$, and recover a model of choice with limit many Woodin cardinals. This is how several of the key equiconsistencies between versions of determinacy and appropriate instances of large cardinals have been proved.

Derived models of (fine-structural) mice are special, of course, and there is a significant body of work on their properties. (And I think we can still say much more.)

A good reference for both topics ($\mathbb R$-premice and derived models of mice) is the paper

John R. Steel. Derived models associated to mice. In Computational prospects of infinity. Part I. Tutorials, pp. 105–193, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., 14, World Sci. Publ., Hackensack, NJ, 2008. MR2449479 (2009m:03082).

(A preprint is available at John's page, where you will also find preprints of papers presenting the derived model construction in detail.)

Work on $\mathbb R$-premice leads to the notion of $K(\mathbb R)$, which indeed gives us a nontrivial way of thinking of some models of determinacy as mice, as we can think of "nice" models of $\mathsf{AD}^+$ as initial segments of $K(\mathbb R)$. (The precise meaning of niceness here is technical, and probably not too illuminating at this point. I mean that appropriate versions of the mouse set conjectures hold. John's paper covers this carefully.)

Work on the core model induction gives us that not just from large cardinals, but also from many strong combinatorial statements, we get many mice (over countable sets) inside $L(\mathbb R)$ (or inside general models of determinacy), and the fact that determinacy holds in $L(\mathbb R)$ can be thought of as a consequence of the presence of these mice. The key notion is the concept of a mouse operator, and a good introduction to this topic is the beginning of the monograph in preparation by John and Ralf:

Ralf Schindler and John R. Steel. The core model induction.

For the gap between CMIP and these papers, you may want to look at John's paper in the Handbook, a preprint of which can also be found at his page:

John R. Steel. An outline of inner model theory. In Handbook of set theory. Vols. 1, 2, 3, pp. 1595–1684, Springer, Dordrecht, 2010. MR2768698.

You are probably interested in this general area, so you may enjoy knowing that we posted notes of many of the talks and background material at the page for the first conference on the core model induction and hod mice, Münster, July 19-August 06, 2010.

For the mouse set conjectures in particular, you want to read Grigor's thesis (posted at the conference site), or the preprint he wrote based on it, and available at his webpage:

Grigor Sargsyan. A tale of hybrid mice.

Answer by Andres Caicedo for $\omega$-small and properly small premice.

2013-03-13T18:02:15Z

If $\mathcal M$ is $\omega$-small, then many $\mathcal J^{\mathcal M}_\beta$ may think that (a large fragment of $\mathsf{ZF}$ holds and) there are plenty of Woodin cardinals. What matters is that for any such $\beta$ there is a larger $\tau$ where we see that this is no longer the case.

This may happen for a variety of reasons: Maybe the relevant cardinals got collapsed along the way. Or maybe they remain cardinals but new subsets $A$ got added, for which we do not have witnesses to $A$-strongness. Or maybe the previous witnesses for various sets $A$ do not actually give rise to $A$-strong embeddings of $\mathcal J^{\mathcal M}_\tau$.

The only serious requirement is that $\tau$ must be reached before we arrive at an active stage (one where we add an extender to the sequence).

Properly small mice have the additional requirement that we in fact certify that no cardinals are Woodin by the time we reach the height of the mouse.

Perhaps a simple-minded analogy may help: (Assume $V=L$ if you want.) If $\kappa$ is inaccessible, and $X\prec L_\kappa$ is countable, then the collapse of $X$ is an $L_\beta$ with $\beta$ countable such that $L_\beta$ is a model of $\mathsf{ZFC}$. However, there is an $\alpha$ with $\beta<\alpha<\omega_1$ such that $L_\alpha$ sees that $\beta$ is countable and, of course, by the time we reach $\omega_1$ we have certified that no smaller ordinal (past $\omega$) is a cardinal.

David Gale's subset take-away game

2010-10-12T15:40:50Z

I learned of this problem through Su Gao, who heard of it years ago while a post-doc at Caltech. David Gale introduced this game in the 70s, I believe. I am only aware of two references in print:

Richard K. Guy. Unsolved problems in combinatorial games. In Games of No Chance, (R. J. Nowakowski ed.) MSRI Publications 29, Cambridge University Press, 1996, pp. 475-491.
J. Daniel Christensen and Mark Tilford. David Gale's Subset Take-Away Game. The American Mathematical Monthly, Vol. 104, No. 8 (Oct., 1997), pp. 762-766.

The game depends on a finite set $A$, and is played by two players I and II that alternate, with I playing first. Each move is a subset of $A$. We are given a pool of available subsets, and each move should be a set in the pool. At the beginning, the pool consists of all subsets of $A$ except for $A$ and the empty set. Whenever a set is used in a move, it and all its supersets are removed from the pool. The game ends when the pool is empty, and the player that was to move and cannot (because there are no moves left) loses.

For example, if $|A|\le 2$, then II always wins. If $|A|\le 3$, there is an easy winning strategy for II. To see this, list the elements of $A$ as $a,b,c$ in such a way that the first move of I is either $\{a\}$ or $\{b,c\}$ , and have II respond the other one. This means that when I comes to move again, only $\{b\}$ and $\{c\}$ remain, and II wins.

One can also check by hand that II has a winning strategy if $|A|\le 5$, and Christensen-Tilford showed the same when $|A|=6$, although they did not include the code used for their computer verification.

The conjecture is that II always has a winning strategy.

My question is whether there have been any further developments towards establishing this, or any additional references. Suggestions or related ideas are also welcome.

Sane bound on number of moves for Maker-Breaker game on $\mathbb R^2$ for $\{0,1,2,3,4\}$

2012-12-17T19:03:22Z

The description below comes from

József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 (2009g:91038).

Given a finite set $S$ of points in the plane $\mathbb R^2$, consider the following game between two players Maker and Breaker. The players alternate, each time picking one (previously unselected) point in $\mathbb R^2$, with Maker moving first. Maker's goal is to build a congruent copy of $S$, while Breaker's goal is to prevent this from happening. If at any finite stage Maker's goal is achieved, the game ends, and Maker wins. Otherwise, Breaker wins.

For example, denote by $A(n)$ the set consisting of $n$ points in a row in arithmetic progression, with common difference one.

Maker has a winning strategy, in two moves, if $S=A(2)$.
Maker has a winning strategy, in three moves, if $S=A(3)$.
Maker has a winning strategy, in at most five moves, if $S=A(4)$ (begin by playing the vertices of an equilateral triangle $ABC$ with side length $1$, such that at least two of the lines it determines, say $AB$ and $AC$, have no points played so far by Breaker).

Beck proves a remarkable theorem in the book (Theorem 1.1): For any finite $S$, Maker has a winning strategy. The proof is an elegant generalization of a theorem of Erdős and Selfridge:

First, one shows that (for any $n$) if $(V,\mathcal F)$ is an $n$-uniform hypergraph with $$ \frac{|\mathcal F|}{|V|}>2^{n-3}\Delta_2(\mathcal F), $$ where $$ \Delta_2(\mathcal F)=\max_{x\ne y\in V}|\{A\in\mathcal F\mid \{x,y\}\subseteq A\}| $$ then, in the game where Maker and Breaker alternate picking distinct elements of $V$, Maker can ensure to pick all the elements in some $A\in\mathcal F$.
Second, one shows that for any $S$, there are finite sets $X$ in the plane that contain "many" congruent copies of $S$. "Many" is formalized so that the inequality above holds, where $V=X$ and $\mathcal F$ is the collection of congruent copies of $S$ among the points in $X$. The sets $X$ obtained this way tend to be very large.

The proof of the "Erdős-Selfridge result" goes by considering a "weighed" characteristic function that counts at each stage of the game the number of sets $A\in\mathcal F$ that have not been eliminated yet by the moves of Breaker, and having Maker play so that the value of this function is maximized at each stage. This ensures that, once all points of $X$ have been played, the function is still positive.

This elegant argument unfortunately produces ridiculously large bounds, due to its great generality. If $S=A(5)$, the number of moves needed to ensure Maker's victory following this approach is estimated to be about $309^{44}\approx 3.6\times 10^{109}$. For $|S|\ge10$, Beck tightens the argument somewhat, to show that $2^{2^{|S|^2}}$ moves suffice.

My question:

For $S=A(5)$, can we find a more decent bound on the number of moves?

My requirement on what counts as "decent" is very loose. I expect the bound above is much larger than needed. I would be happy to be proved wrong, of course, by obtaining large lower bounds. (Additional) references in the literature are also welcome. The following is from pg. 24 of Beck's book:

The wonderful thing about Theorem 1.1 is that it is strikingly general. Yet there is an obvious handicap: these upper bounds to the Move Number are all ridiculously large. We are convinced that Maker can build [the set $S=A(5)$] in (say) less than 1000 moves, but do not have the slightest idea how to prove it. The problem is that any kind of brute force case study becomes hopelessly complicated.

Answer by Andres Caicedo for When Is $\mathbb{L}$-Rank Definable in Inner Models of $\mathbb{V} = \mathbb{L}$?

2013-01-25T20:16:21Z

[Edit: The question is more subtle than I originally understood. I am leaving this here so as to avoid it being repeated by others.]

You can define $<'$ internally only if $M$ is a model of $V=L$, that is, only if $M$ is an $L_\alpha$. For example, $M$ could be (in $L$) a forcing extension of some $L_\alpha$. Being in $L$, every point in $M$ has a rank, but we only see in $M$ the rank of points in $L^M=L_\alpha$. However, $<'$ restricted to $L^M$ is definable in $M$. The usual definition ($a,b\in L$ and $\rho(a)<\rho(b)$) relativizes, so its definition from the point of view of $M$ gives the same relation as the definition of $<'$ in $L$ restricted to elements of $L_\alpha$.

A decent reference to see how $<'$ relativizes and the amount of absoluteness involved is Devlin's book on "Constructibility".

Answer by Andres Caicedo for Continuum Hypothesis

2012-12-30T17:29:19Z

A classical reference is Hypothèse du Continu by Waclaw Sierpiński (1934), available through the Virtual Library of Science as part of the series Mathematical Monographs of the Institute of Mathematics of the Polish Academy of Sciences.

Sierpiński discusses equivalences and consequences. The statements covered include examples from set theory, combinatorics, analysis, and algebra. Most of the consequences he did not show equivalent were found later (mainly by Martin, Solovay, and Kunen) to be strictly weaker in that they follow from Martin's Axiom, and some are discussed in the original Martin-Solovay paper.

(In fact, the discovery of Martin's Axiom and the subsequent research on cardinal characteristics of the continuum helped clarify what the role of CH is in many classical arguments, and nowadays results that classically would be stated as consequences of CH are stated as consequences of some equality between cardinal characteristics. See the articles by Blass and Bartoszyński on the Handbook of Set Theory.)

Of course, many equivalents were found after 1934. For example:

Around 1943, Erdős and Kakutani proved that CH is equivalent to there being countably many Hamel bases whose union is $\mathbb R\setminus\{0\}$ .
In the early 60s, Erdős found a nice equivalent in terms of analytic functions (see Chapter 17 in Aigner-Ziegler Proofs from THE BOOK).
Quite recently, Zoli proved that CH is equivalent to the transcendental reals being the union of countably many transcendence bases.

I do not know of an encyclopedic work updating Sierpiński's monograph. Most recent work on CH centers on what Stevo Todorcevic calls Combinatorial Dichotomies in Set Theory. It turns out that for quite a few statements, CH proves a "nonclassification" result, while strong forcing axioms (such as PFA) prove strong "classifications". For example, J. Moore proved that there is a 5-element basis for the uncountable linear orders if PFA holds, while Sierpiński showed that CH gives us $2^{\aleph_1}$ non-isomorphic uncountable dense sets of reals, none of which embeds into another in an order-preserving fashion.

Though not specifically concerned with CH and its equivalences, you may find interesting Steprans's History of the Continuum in the Twentieth Century.

Another recent line of study on CH centers on the role of choice. Propositions equivalent to CH in ZFC may have wildly different truth values if choice is not assumed. For example, under determinacy, CH is true in the sense that every set of reals is either countable or of the same size as the reals. However, it is also false in the sense that $\aleph_1\not\le|\mathbb R|$, and that there is a surjection from $\mathbb R$ onto $\aleph_2$.

Answer by Andres Caicedo for $\Delta^1_2$-well ordering vs $\Delta^1_3$

2012-12-15T17:14:59Z

Hi Yu,

No, your statement is equiconsistent with $\mathsf{ZFC}$. In

Leo Harrington. Long projective wellorderings, Annals of Mathematical Logic 12 (1977) 1-21, MR0465866 (57 #5752).

it is shown that it is equiconsistent with $\mathsf{ZFC}$ to have a boldface $\Delta^1_3$ well-ordering and Martin's axiom. But the existence of boldface $\Delta^1_2$ well-orderings implies that the reals are the reals of $L[r]$ for some real $r$ (this is a result of Mansfield), and this fails under Martin's axiom.

(The boldface in Leo's result can be made lightface at the cost of more complicated coding techniques. This was shown by Sy Friedman, see his book on "Class forcing". If we do not care about also having $\mathsf{MA}$, Leo's paper also shows how to obtain from $\mathsf{ZFC}$ models with lightface $\Delta^1_3$ well-orderings.)

Going beyond $\mathsf{MA}$, recently, Sy and I proved that if $\mathsf{BPFA}$ holds and $\omega_1=\omega_1^L$, then there is a lightface $\Delta^1_3$ well-ordering of $\mathbb R$. Curiously, it is still open whether starting with $L$ and using the standard forcing for $\mathsf{MA}$ ($+2^\omega=\omega_2$) results in a model with a definable well-ordering of $\mathbb R$.

On the other hand, there is a connection with sharps: Assume that there are no inner models with a strong cardinal (or there is a measurable, but there are no inner models with a Woodin cardinal). If all reals have sharps, and there is a $\Delta^1_3(r)$ well-ordering (for some real $r$), then the reals are the reals of the core model $K_r$. This was first noted by Welch.

Some references:

Mansfield result was nicely reproved by Alekos: Alexander Kechris. The perfect set theorem and definable wellorderings of the continuum, J. Symbolic Logic 43 (1978), no. 4, 630–634, MR0518668 (80b:03067).
Sy D. Friedman. Fine structure and class forcing, de Gruyter Series in Logic and its Applications, 3. Walter de Gruyter & Co., Berlin, 2000, MR1780138 (2001g:03001).
Andrés E. Caicedo, Sy D. Friedman. $\mathsf{BPFA}$ and projective well-orderings of the reals, J. Symbolic Logic 76 (2011), no. 4, 1126–1136, MR2895389 (2012m:03123).
For Welch's result, see: Ralf Schindler. Coding into $K$ by reasonable forcing, Trans. Amer. Math. Soc. 353 (2001), no. 2, 479–489, MR1804506 (2002c:03083).

Answer by Andres Caicedo for How many well orderings of $\aleph_0$ are there?

2012-11-17T06:16:25Z

Colin, there are continuum many, as you suspect.

In fact, there are continuum many well-orderings of type $\omega$. The set of infinite binary sequences has size continuum. Given such a sequence $x=(x_0,x_1,\dots)$, let $i\in\{0,1\}$ be least such that $x_n=i$ infinitely often. Consider the enumeration of the naturals $a=(a_0,a_1,\dots)$ that begins with $a_0=i$. Having defined $a_n$, let $a_{n+1}$ be the first natural number not used so far, if $x_n=i$, and let $a_{n+1}$ be the second number not used so far, otherwise.

Since there are infinitely many $k$ such that $x_k=i$, the $a_n$ enumerate all naturals. Since from the sequence we can easily recover $x$, this assignment $x\mapsto a$ is injective. The ordering $a_0\lt a_1\lt a_2\lt\dots$ is a well-ordering of the naturals in type $\omega$.

It follows immediately that, for any countable infinite $\alpha$, there are continuum many well-orderings of the naturals in type $\alpha$. This is because one can simply fix a bijection between $\alpha$ and $\omega$, and use it to "transfer" the procedure just described.

Answer by Andres Caicedo for Important open problems that have already been reduced to a finite but infeasible amount of computation

2012-11-14T06:38:47Z

This is an elaboration of a comment on Suvrit's answer.

Ramsey numbers can be defined for (infinite) ordinals, just as in the finite case: $r(\alpha,\beta)$ is the least $\gamma$ such that for any $2$-coloring of the edges of the complete graph on $\gamma$ vertices there is a set of vertices of type $\alpha$ whose induced graph is red, or a set of vertices of type $\beta$ whose induced graph is blue.

Ramsey's theorem gives that $r(\omega,\omega)=\omega$, but already $r(\omega+1,\omega)=\omega_1$. On the other hand, if $\alpha\lt\omega_1$ and $n$ is finite, then $r(\alpha,n)\lt\omega_1$, and for reasonably small infinite values of $\alpha$, one can attempt to compute $r(\alpha,n)$ explicitly. It turns out that this computation reduces to (Ramsey-theoretic) finite problems, which, just as with the classic computation of finite Ramsey numbers, quickly become unfeasible.

For example:

$r(\omega+3,3)=\omega\cdot2 + 8$. In general, if $0\lt n,m\lt\omega$, then $$ r(\omega+n,m)=\omega\cdot(m-1)+(g(n,m)-(m-1)), $$ where $g(n,m)$ is the least $k$ such that any $2$-coloring of the edges of the complete graph on set of vertices $\{1,\dots,k\}$ such that the induced graph on $C=\{1,\dots,m-1\}$ is blue, either admits a blue $K_m$, or a red $K_{n+1}$ with one of its vertices in $C$.

This was first established by Haddad and Sabbagh in 1969. One has $r(n+1,m)\le g(n,m)\lt\infty$, but typically the first inequality is strict. For example, $r(4,3)=9$ but $g(3,3)=10$. In general, computing $g(n,m)$ is similar to, but harder than computing $r(n+1,m)$.

$r(\omega\cdot3,3)=\omega\cdot9$. In general, if $0\lt n,m\lt\omega$, then $$ r(\omega\cdot n,m)=\omega\cdot l(n,m), $$ where $l(n,m)$ is the least $k$ such that any $2$-coloring of the edges of the complete digraph on $k$ vertices either contains a red complete digraph on $n$ vertices, or a blue transitive tournament on $m$ vertices.

Here, in complete digraphs we have two arrows (going in opposite directions) between any two distinct vertices. This was shown by Erdős and Rado in 1955. As with $g$, the computation of the values of $l(n,m)$ quickly becomes unfeasible.

$r(\omega^2\cdot2,3)=\omega^2\cdot10$. In general, if $0\lt n,m\lt\omega$, then $r(\omega^2\cdot m,n)=\omega^2\cdot h(m,n)$ for a Ramsey-theoretic function $h$ related to $3$-colorings of the edges of digraphs, though its exact description is somewhat technical to include here. This was shown fairly recently by Thilo Weinert, see here.

Answer by Andres Caicedo for What is Gödel's pairing function on ordinals?

2012-11-11T16:55:13Z

Asaf and Joel have answered the question. Let me add a remark that expands the fact that it helps us prove that $\kappa\times$ and $\kappa$ have the same size. All the claims here can be verified rather easily. Multiplication and exponentiation are in the ordinal sense.

It is customary to write $\Gamma(\alpha,\beta)$ for the order type of the predecessors of $(\alpha,\beta)$ under the order than Asaf denotes $\prec$. For example, $\Gamma(\omega,\omega\cdot2)=\omega^2+\omega$.

An ordinal $\alpha$ is (additively) indecomposable iff $\alpha\gt 0$ and whenever $\beta,\gamma\lt\alpha$, then $\beta+\gamma\lt \alpha$. One can easily check that the indecomposable $\alpha$ are precisely those of the form $\omega^\beta$. Say that $\alpha$ is multiplicatively indecomposable iff $\alpha>0$ and $\beta\gamma\lt \alpha$ whenever $\beta,\gamma\lt\alpha$. Then $\alpha$ is multiplicatively indecomposable iff it is $1$ or has the form $\omega^{\omega^\beta}$.

Ok, we can now state the remark; unfortunately I would not know who to credit for this observation, I think of it as folklore: An ordinal $\alpha$ is multiplicatively indecomposable iff it is closed under Gödel pairing, that is, $\Gamma(\beta,\gamma)\lt\alpha$ whenever $\beta,\gamma\lt\alpha$. In particular, $\Gamma(\kappa,\kappa)=\kappa$ for any infinite cardinal $\kappa$, which of course implies that $\kappa\times\kappa$ and $\kappa$ have the same size. Also, if $\kappa$ is uncountable, then there are $\kappa$ ordinals $\alpha$ below $\kappa$ such that $\Gamma(\alpha,\alpha)=\alpha$. Of course, all of this works well in $\mathsf{ZF}$ and all the definitions involved are absolute.

I prefer a different approach when verifying that $\kappa\times\kappa$ and $\kappa$ have the same size, one that (again) is absolute and goes through in $\mathsf{ZF}$, but only requires the use of additively indecomposable ordinals: One first checks that there is a (recursive) bijection $h:\omega\times\omega\to\omega$ with $h(0,0)=0$. Then, given ordinals $\alpha,\beta$, use their Cantor's normal form to write them as $$ \alpha= \omega^{\alpha_1}n_1 + \omega^{\alpha_2}n_2 + \dots + \omega^{\alpha_k}n_k $$ and $$ \beta= \omega^{\alpha_1}n'_1 + \omega^{\alpha_2}n'_2 + \dots + \omega^{\alpha_k}n'_k $$ where $\alpha_1 \gt \alpha_2 \gt \dots \gt \alpha_k$ are ordinals, and $n_1,\dots,n_k, n'_1,\dots,n'_k$ are natural numbers. (Note that these representations are not unique, but at least one of $n_i$ and $n_i'$ is non-zero iff $\alpha_i$ appears as an exponent in the canonical form of $\alpha$ or $\beta$).

Now set $$ H(\alpha,\beta)=\omega^{\alpha_1}h(n_1,n'_1)+\omega^{\alpha_2}h(n_2,n'_2)+\dots+ \omega^{\alpha_k}h(n_k,n'_k). $$ Then $H$ is a bijection between $\alpha\times\alpha$ and $\alpha$ whenever $\alpha$ is indecomposable. And an easy inductive argument, appealing to the explicit proof of Schröder-Bernstein, allows us to use $H$ to argue that there is, provably in $\mathsf{ZF}$, a class function that assigns to each infinite ordinal $\alpha$ a bijection between $\alpha\times\alpha$ and $\alpha$.

(Of course, the existence of this class function can also be argued from $\Gamma$, using that there are $\kappa$ ordinals $\alpha$ below $\kappa$ with $\Gamma(\alpha,\alpha)=\alpha$, but this second approach is somewhat easier.)

I found this argument a while ago, but then saw that Levy gives essentially the same approach in his textbook on set theory. Again, I am not sure who to credit for this construction, it seems to go back to Gerhard Hessenberg's 1906 book, "Grundbegriffe der Mengenlehre".

Answer by Andres Caicedo for Number of linear orders

2012-11-02T16:22:15Z

Hi Martin.

I learned what follows in J.M. Plotkin, ed., Hausdorff on Ordered sets, AMS, History of Mathematics 25, 2005.

The result for countable ordered sets is due to Cantor. More precisely, Cantor produced continuum many countable order types:

Assign to each $x\in 2^\omega$ the type $x_0+(\omega^*+\omega)+x_1+(\omega^*+\omega)+x_2+\dots$

Bernstein proved (by March, 1901 or earlier) that there can be no more than continuum many. The result (both parts) appears in his 1901 dissertation, Untersuchungen aus der Mengenlehre. That there are at most continuum many types was also found independently by Hausdorff (June 27, 1901, according to his Nachlass, during a Summer course on Set theory at the University of Leipzig); it is referred to as the "Cantor-Bernstein theorem" in Hausdorff's Über eine gewisse Art geordneter Mengen, Gesellschaft der Wissenschaften zu Leipzig, Mathematisch-Physische Classe 53 (1901), 460-475. (See pg. 460)

It is probably worth remarking that this shows Bernstein's and Hausdorff's comfort with using choice in their arguments from the beginning, as clearly this gives us a "natural" example showing that $\omega_1\le 2^{\aleph_0}$. (On the other hand, Hausdorff remains unsure at this time on whether $\mathbb R$ can be well-ordered.)

Bernstein gives two proofs of the upper bound. The first goes by identifying an ordered set $M$ with a function $f:M^2\to\{-1,0,1\}$ :

$f(a,b)=-1$ iff $a\lt b$, $f(a,b)=0$ iff $a=b$, and $f(a,b)=1$ iff $a\gt b$.

One then just has to count such functions for $M=\mathbb N$.

The second proof uses Cantor's result that $\mathbb Q$ is universal for countable linear orders, so one only has to count subsets of $\mathbb Q$.

The general result is due to Hausdorff, in his 1901 paper, with the published upper bound the same argument as Bernstein's first proof. (There seem to be no records of Hausdorff's original argument, or of whether it was different.) He doesn't quite use that $M$ is well-orderable, but rather that $\mathfrak m=|M|$ satisfies $\mathfrak m^2=\mathfrak m$.

The lower bound is argued as follows: Given an infinite linearly ordered set $M$ of size $\mathfrak m=|M|$, call it graded iff no two distinct initial segments of $M$ are order isomorphic. Assume $M$ admits a graded ordering (which is clearly the case if $\mathfrak m$ is an aleph). For $m\in M$, denote by $A_m$ the set of predecessors of $m$.

Given a set $S\subseteq M$ of size $\mathfrak m$, assign to it the ordered sum $L_S$ of the sets $\mathbb Q+A_s$, $s\in S$, and note that if $S\ne S'$ then $L_S$ and $L_{S'}$ are not order isomorphic. The result follows if $[\mathfrak m]^{\mathfrak m}=2^{\mathfrak m}$ which, again, holds if $\mathfrak m$ is an aleph. (Plotkin remarks that Hausdorff could have elaborated a bit more on why the sets $L_S$ are not isomorphic.)

Answer by Andres Caicedo for Can measures be added by forcing?

2012-10-28T15:18:13Z

Just some comments to complement Joel's answer:

That forcing can destroy and then recreate measurability is due to Kunen:

Kenneth Kunen. Saturated ideals, The Journal of Symbolic Logic 43 (1) (1978), 65–76. MR0495118 (80a:03068)

The same is true for real valued measurability, this is due to Gitik:

Moti Gitik, Saharon Shelah. More on Real-valued measurable cardinals and forcing with ideals, Israel Journal of Mathematics 124 (2001), 221–242 ([GiSh 582]). MR1856516 (2002g:03110)

For a while it was open whether we can destroy and then reconstruct measurability while still preserving weak compactness. In all arguments I was aware of, it is essential that weak compactness fails in the intermediate model, as what we accomplish is a (destructible) instance of failure of stationary set reflection. Joel points out that his argument actually preserves weak compactness, and can be carried out in other settings to preserve measurability or stronger properties.

More generally, one can ask whether measurability can "appear spontaneously" by forcing, through some other means, just as we obtain saturation on the non-stationary ideal on $\omega_1$ by forcing MM, which cannot be traced back to some measure in some inner model that the forcing is reconstructing.

For another proof of the specific result you are asking (but one that destroys weak compactness in the intermediate extension), see section 4 of my paper on RVM cardinals:

Real-valued measurable cardinals and well-orderings of the reals. In Set theory. Centre de Recerca Matemàtica, Barcelona, 2003–2004, Joan Bagaria, and Stevo Todorcevic, eds.; Trends in Mathematics, Birkhäuser Verlag, Basel, 2006, pp 83–120, MR2267147 (2007g:03064)

Answer by Andres Caicedo for Effect of large cardinals on the value of $\omega_1^L$ in $L$

2012-10-28T06:07:23Z

The answer is no. If there is a transitive set model $M$ of set theory (and this is all you need), then if $\alpha$ is its height (that is, if $\alpha=\mathsf{ORD}^M$), then $L_\alpha$ is a model of $\mathsf{ZFC}+V=L$. Note that the assumption is strictly stronger than the existence of an $\omega$-model of $\mathsf{ZFC}$, which in turn is strictly stronger than the mere consistency of $\mathsf{ZFC}$, but it is strictly weaker than the existence of inaccessible cardinals.

Now work in $L$, and consider a countable elementary substructure $Y\preceq L_\alpha$. Note that $Y$ is well-founded and satisfies $V=L$. Its collapse is then $L_\beta$ for some $\beta$ that, by necessity, is countable in $L$.

(Note that this also addresses (2), by taking $X=\emptyset$.)

By the way, this highlights some of the difficulties a challenger of "$V=L$" must face. Even if there are no inaccessibles, the model $M$ we began with may perfectly well be constructible, and satisfy that there are supercompact cardinals, or whatever. About this, you may also want to look at this post by Joel.

Answer by Andres Caicedo for Is there a classification of or work towards a classification of countable ordered sets?

2012-10-27T21:16:15Z

Yes. The reference to get started is

MR0662564 (84m:06001) Rosenstein, Joseph G. Linear orderings. Pure and Applied Mathematics, 98. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982.

The key idea is Hausdorff's notion of scattered order. These are the ordered sets that contain no copies of the rationals. They admit a detailed classification, essentially by an analysis reminiscent of the study of Cantor-Bendixson derivatives (more precisely, we can build up all scattered ordered sets by iterating "sums" of simple orders, the last link below gives more details).

The key result is Laver's theorem that Fraïssé’s conjecture holds: The class of countable linear ordering can be quasi-ordered by embeddablity. With this ordering, the class contains no infinite descending chain and no infinite antichain.

(So, this is not a classification in the model theoretic sense, but it is more detailed and far-reaching than simply discussing a basis, which of course consists simply of $\omega$ and $\omega^*$.)

If you want to see how Hausdorff's analysis can be used, Laver's proof is the result to study. For an extension, see:

Continuous Fraïssé Conjecture. Arnold Beckmann, Martin Goldstern, Norbert Preining. MR2470199 (2010a:03021) Order 25 (2008), no. 4, 281–298.

Hausdorff's analysis can be continued into a study of uncountable ordered sets, but now things get much more involved, and ZFC does not settle their basic structure theory. See this answer to a related question on the sister site for more details.

Answer by Andres Caicedo for Generalizing Feferman - Levy

2012-10-15T16:26:49Z

Posting this as an answer at Colin's request. The second paragraph of the question is addressed at this other MO question.

The answer to the question in the first paragraph is delicate, it depends on how much of the ground model we decide to preserve: $\alpha$ and $\alpha^+$? $\rm{cof}(\alpha)$ and $\alpha^+$? Only $\alpha^+$? The issue is that a straight generalization of Feferman-Lévy must fail just based on consistency strength considerations, because Jensen's covering lemma gives us that preserving a singular and collapsing its successor requires large cardinals (even in $\mathsf{ZF}$). For the covering lemma, see:

Devlin, Keith I.; Jensen, Ronald B. Marginalia to a theorem of Silver. In $\models$ISILC Logic Conference (Proc. Internat. Summer Inst. and Logic Colloq., Kiel, 1974), G. H. Müller, A. Oberschelp, and K. Potthoff, eds., pp. 115–142. Lecture Notes in Math., Vol. 499, Springer, Berlin, 1975. MR0480036 (58 #235)
Mitchell, William J. The covering lemma. In Handbook of set theory. Vols. 1, 2, 3, Kanamori, Foreman, eds., pp. 1497–1594, Springer, Dordrecht, 2010. MR2768697

Answer by Andres Caicedo for Do sets with positive Lebesgue measure have same cardinality as R?

2010-05-29T19:16:42Z

I'm interpreting the question as: Measurable, with positive measure, not as "having positive outer measure" (for which the answer is independent of the basic axioms of set theory, as pointed out by Joel).

The answer is yes. By elementary properties of Lebesgue measure (regularity), for any $\epsilon>0$, any set $C$ of positive measure contains compact subsets $C_\epsilon$ of measure within $\epsilon$ of the measure of $C$ (interpret this as "arbitrarily large" if $C$ has infinite measure). Any set of positive measure is obviously uncountable. It is straightforward to see that a compact uncountable set of the reals contains a perfect set, and that perfect sets have the same size as the reals. Therefore, $C$ must also have the size of the reals. (I guess the last step uses the Schroeder-Bernstein theorem.)

(On a side note, Cantor proved the result that closed uncountable subsets of ${\mathbb R}$ have the size of the reals. This extends to larger collections of sets, e.g., to all uncountable Borel sets. The first approach to the continuum hypothesis was to try to keep on extending this result.)

To see that perfect sets have the size of the reals: Check that any perfect set has a "copy" of Cantor's set; this is standard; baby Rudin essentially shows how in an exercise in Chapter 1 or 2. Cantor's set, by construction, obviously has size $2^{|{\mathbb N}|}$. Check that the reals also have this size, e.g., by noticing that ${\mathbb R}$ and $(0,1)$ have the same size, and identifying reals in $(0,1)$ with their infinite binary expansion. I suppose this may also use Schroeder-Bernstein depending on how one fleshes this outline out.

Answer by Andres Caicedo for Sets of reals and absoluteness

2012-09-27T00:54:28Z

At the projective level, there are nice level by level generalizations, and looking at Steel's paper in the Handbook should give you the proof and the pre-requisites to understand it fully. This is what is behind the relation between determinacy and large cardinals. On the other hand, $\Sigma^2_1$ is never going to be possible, at least given our current understanding of how large cardinals work, because $\mathsf{CH}$ is $\Sigma^2_1$.

On the other hand, Woodin proved around 1985 that a conditional version of $\Sigma^2_1$ absoluteness holds. In fact, it identifies $\mathsf{CH}$ as a "maximal" sentence, in the following sense:

Theorem. Assume there are a proper class of cardinals that are simultaneously measurable and Woodin. If $\phi$ is a $\Sigma^2_1$ statement (with real parameters from the ground model), then: $\phi$ is true in some set forcing extension of the universe iff $\phi$ is true in every set forcing extension that satisﬁes $\mathsf{CH}$.

For a nice recent account of the argument, see Ilijas Farah, "A proof of the $\Sigma^2_1$ absoluteness theorem", in Advances in Logic, S. Gao, S. Jackson and Y. Zhang, eds., Contemporary Mathematics, 425 (2007) American Mathematical Society, RI., 9-22.

What the actual optimal statement is in terms of large cardinal strength is hard to tell at the moment, as inner model theory does not reach that high. We expect it to be somewhere around the sharp for a mouse with a measurable Woodin.

Beyond $\Sigma^2_1$, there is much speculation. It is expected some strengthening of diamond will be maximal for $\Sigma^2_2$, and we will get a similar theorem, but beyond $\Sigma^2_2$ this starts to conflict with other conjectures.

Answer by Andres Caicedo for Why is there no Borel function mapping every countable set of reals outside itself?

2010-11-25T07:51:49Z

[Edit, Sep. 22, 2012: I am leaving the original answer below, but Andreas's comment is the right approach, so I am incorporating it into the answer, adding a bit of context. We want to argue that there is no definable bijection between $[\mathbb R]^{\le\aleph_0}$ and $\mathbb R$. It suffices to show that there is no such bijection in Solovay's model, or under determinacy. In fact, there is no such bijection in any model where $\omega_1\not\le|\mathbb R|$.

A very general reason showing this is an old observation of Tarski, that follows from Zermelo's work on the well-ordering theorem: In $\mathsf{ZF}$, for any set $X$ we have $|X|\lt |\mathcal W(X)|$, where $\mathcal W(X)$ denotes the collection of well-orderable subsets of $X$. If $\omega_1\not\le|\mathbb R|$, then $\mathcal W(\mathbb R)$ is $[\mathbb R]^{\le\aleph_0}$.

To see the inequality, simply note that any $f:\mathcal W(X)\to X$ gives rise ("by recursion") to a unique $W$ with a well-ordering $\lt$ such that $f(W)\in W$ and $$f(\{a\in W\mid a\lt x\})=x$$ for any $x\in W$. But then $W$ witnesses that $f$ is not injective.]

Joel's answer shows that there is no Borel $f:{\mathbb R}^\omega\to{\mathbb R}$ that is invariant under the equivalence relation that identifies sequences if they have the same range and such that $f(\vec x)$ is not in the range of $\vec x$.

What remains to address is whether we can replace ${\mathbb R}^\omega$ with ${}[{\mathbb R}]^{\le\aleph_0}$, the collection of countable subsets of ${\mathbb R}$. The issue is really whether we can give the space ${}[{\mathbb R}]^{\le\aleph_0}$ a standard Borel structure in a definable manner.

I believe this is not possible: Unless I'm mistaken, the relation $E$ of having the same range is a Borel equivalence relation (on ${\mathbb R}^\omega$) bi-reducible with the equivalence relation commonly known as $T_2$, see Vladimir Kanovei, "Varia: Ideals and Equivalence Relations, beta-version", arXiv:math/0610988. Of course, ${}[{\mathbb R}]^{\le\aleph_0}$ coincides in anatural way with the quotient ${\mathbb R}^\omega/E$.

But the relation $T_2$ is very high in the reducibility hierarchy; in particular, it is above $E_0$, which means that $2^{\mathbb N}/E_0$ injects into ${\mathbb R}^\omega/E$ in a definable fashion. Recall that $xE_0y$ (for $x,y\in2^{\mathbb N}$) iff $x(n)=y(n)$ for all but finitely many $n$.

But it is known that $2^{\mathbb N}/E_0$ does not admit a Borel structure in any reasonable fashion, since in fact it is not even linearly orderable in any reasonably definable manner, see this answer.

As usual, this lack of Borel structure translates under, say, determinacy, to strong answers to Aaron's question, so in determinacy models we have that there is no function $f:[{\mathbb R}]^{\le\aleph_0}\to{\mathbb R}$ mapping each $A$ outside itself.

(Please let me know if I've misidentified $T_2$ and I'll edit accordingly.)

By the way, I learned (essentially) Joel's argument from Alekos Kechris a few years ago, and if I remember correctly, he termed this a classical result. I cannot remember at the moment whether it was attributed to anybody specifically (and I would be curious to know).

Let me close with a curious remark: In light of the answer to Aaron's question, it is natural to wonder whether we can even have a "definable" pairing function, or even a definable "countable pairing" function: A (definable) function that given a countable set ${\mathcal A}$ of sets of reals returns a set $C$ from which each $A$ in ${\mathcal A}$ can be recovered (so $C$ is essentially a definable version of a listing of ${\mathcal A}$).

Surprisingly, this is the case, as pointed out by Steve Jackson. For example, there is (definably) an $F:{\mathcal P}({\mathbb R})\times{\mathcal P}({\mathbb R})\to{\mathcal P}({\mathbb R})$ such that $F(A,B)=F(B,A)$ for all $A,B$, and both $A,B$ are Wadge reducible to $f(A,B)$. If we assume the very weak choice axiom $AC_\omega({\mathbb R})$, then the corresponding result for countable sequences of sets of reals holds as well. The details can be seen in my paper with Ketchersid, "A trichotomy theorem in natural models of AD${}^+$", to appear in the Proceedings of the BEST conference.

Here is the argument for pairs: Identify reals with infinite sequences of naturals. If $A = B$, simply set $F (A, B) = A$. If $A\subseteq B$ or $B\subseteq A$, set $F (A, B) = (0 ∗ S ) \cup (1 ∗ T )$ where $S$ is the smaller of $A, B$, and $T$ is the larger. Here, $0 ∗ S =\{0{}^\frown a \mid a \in S \}$ and similarly for $1 ∗ T$.

If $A\setminus B$ and $B\setminus A$ are both non-empty, we proceed as follows: Let $X (A, B)\subseteq{\mathbb R}^{\mathbb Z}$ be defined by saying that, if $f : {\mathbb Z}\to{\mathbb R}$, then $f \in X (A, B)$ iff there is an $i$ such that $f (i) \in A \setminus B$ (or $B \setminus A$) and, for each $j$, $f (j ) \in A$ if ${}|j − i|$ is even, and $f (j ) \in B$ if ${}|j − i|$ is odd (and reverse the roles of $A, B$ here if $f (i) \in B \setminus A$).

The set $X (A, B)$ is an invariant set (with respect to the shift action of ${\mathbb Z}$ on ${\mathbb R}^{\mathbb Z}$), and $X (A, B) = X (B, A)$. (The points of $A \setminus B$ and $B \setminus A$ have to occur at places of different parity; while points of $A \cap B$ can occur anywhere.)

Given $X (A, B)$, we can compute $A$ (and also $B$) as follows: Fix $z \in A \setminus B$. Then $x \in A$ iff $$\exists f \in X (A, B) \exists i \exists j (f (i) = z \mbox{ and }f (j ) = x \mbox{ and }|j − i|\mbox{ is even}).$$ This shows that $A$ is (boldface) $\Sigma^1_1 (X (A, B))$. If we replace $X (A, B)$ with $X' (A, B)$, the *$\Sigma^1_1$-jump* of $X (A, B)$, then $A$ is Wadge reducible to $X (A, B)$.

Finally, we use that there is a Borel bijection between ${\mathbb R}^{\mathbb Z}$ and ${\mathbb R}$, and define $F (A, B)$ as the image of $X'(A, B)$ under this map.

Extending Jordan loops

2012-09-22T15:41:45Z

I encountered this issue recently, but do not know of any general results to deal with it, so I would appreciate any pointers.

Let $\mathbb T=\{z\in\mathbb C\mid |z|=1\}$ , and let $f:\mathbb T\to\mathbb C$ be continuous and injective, so its image $\mathbb T'$ is a Jordan loop. Under what (general) conditions can we ensure that there is a homeomorphism between the unit disc and the interior of $\mathbb T'$ whose extension to the boundary is $f$?

Moreover, if there are reasonable conditions that ensure this, and $f$ is $C^\infty$, can we further require some nice regularity (perhaps even $C^\infty$) of the extension as well?

Answer by Andres Caicedo for Solovay's paper from AD+ that all sets are Ramsey

2012-09-08T05:58:50Z

About all you need is in Adrian's paper "Happy families". It is not spelled out as following from ${\sf AD}^+$, of course, since the concept did not exist yet.

Anyway, if you are familiar with Solovay's arguments in his paper on all sets of reals being measurable (or as discussed in the Feng-Magidor-Woodin paper on universally Baire sets), then all you want to read is section 2 (up to 2.2.3) of my paper with Richard Ketchersid, "A trichotomy theorem in natural models of ${\sf AD}^+$", in Set Theory and Its Applications, Contemporary Mathematics, vol. 533, Amer. Math. Soc., Providence, RI, 2011, pp. 227-258, MR2777751, and also available at my papers page.

Very briefly, what we use of ${\sf AD}^+$ is little more than all sets of reals having $\infty$-Borel codes. If $S$ is an $\infty$-Borel code for a set of reals $A$, then $L[S]$ is a model of choice, so (from determinacy), its reals are countable and in fact $\omega_1^V$ is inaccessible in $L[S]$. One can now run the argument that sets of reals are Ramsey in the Solovay model, noting that there are (in $V$) generics over $L[S]$ for Mathias's forcing, and the proof is concluded from the defining property of $\infty$-Borel sets.

Since the proof uses the $\infty$-Borel machinery so explicitly, it is still open whether ${\sf AD}$ suffices for this result.

Dual Schroeder-Bernstein theorem

2010-09-15T03:43:19Z

This question was motivated by the comments to http://mathoverflow.net/questions/38754/dual-of-zorns-lemma

Let's denote by the Dual Schroeder-Bernstein theorem (DSB) the statement

For any sets $A$ and $B$, if there are surjections from $A$ onto $B$ and from $B$ onto $A$, then there is a bijection between them.

In set theory without choice, assume that the Dual Schroeder-Bernstein theorem holds. Does it follow that choice must hold as well?

I strongly suspect this is open, though I would be glad to be proven wrong in this regard. In all models of ZF without choice that I have examined, DSB fails. This really does not say much, as there are plenty of models I have not looked at. In any case, I don't see how to even formlate an approach to show the consistency of DSB without AC.

The only reference I know for this is Bernhard Banaschewski, Gregory H. Moore, The dual Cantor-Bernstein theorem and the partition principle, Notre Dame J. Formal Logic 31 (3), (1990), 375–381. In this paper it is shown that a strengthening of DSB does imply AC, namely, that whenever there are surjections $f:A\to B$ and $g:B\to A$, then there is a bijection $h:A\to B$ contained in $f\cup g^{-1}$. (Note that the usual Schroeder-Bernstein theorem holds -without needing choice- in this fashion.)

The partition principle is the statement that whenever there is a surjection from $A$ onto $B$, then there is an injection from $B$ into $A$. As far as I know, it is open whether this implies choice, or whether DSB implies the partition principle. Clearly, the reverse implications hold.

If you are interested in natural examples of failures of DSB in some of the usual models, Benjamin Miller wrote a nice note on this, available at his page.

Added Sep. 21. [Edited Aug. 14, 2012] It may be worthwhile to point out what is known, beyond the Banaschewski-Moore result mentioned above.

Assume DSB, and suppose $x$ is equipotent with $x\sqcup x$. Then, if there is a surjection from $x$ onto a set $y$, we also have an injection from $y$ into $x$. (So we have a weak version of the partition principle.) This idemmultiple hypothesis that $x\sqcup x$ is equipotent to $x$, for all infinite sets $x$, is strictly weaker than choice, as shown in Gershon Sageev, An independence result concerning the axiom of choice, Ann. Math. Logic 8 (1975), 1–184, MR0366668 (51 #2915).

Also, as indicated in Arturo Magidin's answer (and the links in the comments), H. Rubin proved that DSB implies that any infinite set contains a countable subset.

Convergence of $\sum(n^3\sin^2n)^{-1}$

2010-05-14T06:09:43Z

I saw a while ago in a book by Clifford Pickover, that whether $\displaystyle \sum_{n=1}^\infty\frac1{n^3\sin^2 n}$ converges is open.

I would think that the question of its convergence is really about the density in $\mathbb N$ of the sequence of numerators of the standard convergent approximations to $\pi$ (which, in itself, seems like an interesting question). Naively, the point is that if $n$ is "close" to a whole multiple of $\pi$, then $1/(n^3\sin^2n)$ is "close" to $\frac1{\pi^2 n}$.

[Numerically there is some evidence that only some of these values of $n$ affect the overall behavior of the series. For example, letting $S(k)=\sum_{n=1}^{k}\frac1{n^3\sin^2n}$, one sees that $S(k)$ does not change much in the interval, say, $[50,354]$, with $S(354)<5$. However, $S(355)$ is close to $30$, and note that $355$ is very close to $113\pi$. On the other hand, $S(k)$ does not change much from that point until $k=100000$, where I stopped looking.]

I imagine there is a large body of work within which the question of the convergence of this series would fall naturally, and I would be interested in knowing something about it. Sadly, I'm terribly ignorant in these matters. Even knowing where to look for some information on approximations of $\pi$ by rationals, or an ad hoc approach just tailored to this specific series would be interesting as well.

Strictly order preserving maps into the integers

2012-08-01T15:45:06Z

If $P$ and $P'$ are partial orders, a strictly order preserving map from $P$ to $P'$ is an $f:P\to P'$ satisfying that $x\lt y$ implies $f(x)\lt f(y)$ for all $x,y\in P$.

An interval in $P$ is a set of the form ${}[x,y]=\{z\mid x\le z\le y\}$ , where $x\le y$. Note that points in an interval need not be comparable with one another. The height of an interval is the supremum of the lengths of $< $-chains of elements in the interval.

Clearly, if there is a strictly order preserving map from $P$ to $\mathbb Z$, then all intervals in $P$ have finite height. If $P$ is countable, this condition also suffices for the existence of such a map. This dates back to Erné in 1979.

However, there are examples of uncountable $P$ with all intervals of finite height for which there is no strictly order preserving map into $\mathbb Z$. The examples I know have size continuum ($=|\mathbb R|$) or larger. A nice example due to Farley and Schröder can be found here.

Is there an example of size $\omega_1$, preferably one that does not require the axiom of choice?

Answer by Andres Caicedo for Finite measure on the power set

2012-07-31T06:07:16Z

I assume you mean a $\sigma$-additive measure. This is Ulam's measure problem. A positive answer is closely tied up to the existence of real-valued measurable cardinals, so it is equiconsistent with the existence of a measurable cardinal, which is a large cardinal assumption significantly beyond the usual axioms of set theory.

You can see a quick write up of the argument here. A good reference is the beginning of David Fremlin, "Real-valued measurable cardinals", in Set Theory of the reals, Haim Judah, ed., Israel Mathematical Conference Proceedings 6, Bar-Ilan University (1993), 151–304, that I also mention in the notes linked to above.

In short (this is expanded in the notes): If $(X,\mathcal P(X),\lambda)$ is such a measure space, we may as well assume (by concentrating on an appropriate subset, which may be of smaller size than $X$, and renormalizing) that $\lambda$ is a probability measure. Its additivity is the smallest cardinal $\kappa$ such that the measure of the disjoint union of some collection of $\kappa$ many disjoint subsets of $Y$ is not the sum of the measures of the sets in the union. (So the additivity is at least $\aleph_1$, and it is well-defined, since we are assuming that $\lambda(X)>0$.)

Then we can in fact assume $X=\kappa$ (identifying cardinals with sets of ordinals). If $\lambda$ is non-atomic (meaning, for any $E\subseteq\kappa$, if $\lambda(E)>0$ then there is $F\subset E$ with $0<\lambda(F)<\lambda(E)$), then $\lambda$ is (atomlessly) real valued measurable. On the one hand, these cardinals are not too large: $\kappa\le|\mathbb R|$. On the other, $\kappa$ must be weakly inaccessible, and in fact limit of weakly inaccessibles that themselves are limit of weakly inaccessibles, etc. This is very very large.

The other possibility is that $\lambda$ is atomic. Then, after further renormalization, $\lambda$ can be identified with the characteristic function of a non-principal $\kappa$-complete ultrafilter, that is, $\kappa$ is measurable.

Answer by Andres Caicedo for Comparability implies well-orderability?

2012-07-20T14:57:49Z

Hi Asaf. It is open whether the continuum hypothesis for an infinite set $E$ implies the well-orderability of $X$. Of course, if $CH(E)$ holds, then the assumption in your (first) statement holds.

($CH(E)$ is the statement that any subset $A$ of $\mathcal P(E)$, either $A$ injects into $E$, or else $A$ is in bijection with $\mathcal P(E)$.)

This is a question that dates back to Ernst Specker, "Verallgemeinerte Kontinuumshypothese und Auswahlaxiom", Archiv der Mathematik 5 (1954), 332–337. There is a nice presentation in Akihiro Kanamori, David Pincus, "Does GCH imply AC locally?, in "Paul Erdős and his mathematics, II (Budapest, 1999)", Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, (2002), 413–426.

I do not know about the stronger statement you ask for. Part of the difficulty comes from the "bad" cardinal arithmetic we should have below $|{\mathcal P}(E)|$. For example, Specker proved that if CH holds for both $X$ and $\mathcal P(X)$, then $\mathcal P(X)$ is well-orderable.

Answer by Andres Caicedo for Hartogs number and the three power sets

2012-05-30T13:54:52Z

Hi Asaf,

I thought about this a while ago. Of course, the question had been asked and solved before. Digging through the FOM archives for Spring 2009, I found (April 28, 2009; I fixed a typo in what follows):

In a message dated Jan. 28, I asked whether Sierpinski's ZF result that $\aleph(X) < \aleph({\mathcal P}({\mathcal P}({\mathcal P}(X))))$ for all $X$, could be improved by replacing the triple power set with a double power set.

In a follow up dated Feb. 2, I indicated that one can, provided that $\aleph(X)$ is not $\aleph_\alpha$ for some infinite limit ordinal $\alpha < \aleph_\alpha$.

I recently found a reference that settles the other case, and wanted to give an update for those curious about the question. In Theorem 11 of John L. Hickman, "$\Lambda$-minimal lattices", Zeitschr. f. math. Logik und Grundlagen d. Math., 26 (1980), 181-191, it is shown that for any such $\alpha$, it is consistent to have an $X$ with $\aleph(X) = \aleph_\alpha = \aleph({\mathcal P}({\mathcal P}(X)))$.

So, yes, the triple power set is best possible in ZF. (If $\Lambda$ is an aleph (a well-ordered cardinal), a set $X$ is said to be a $\Lambda$-set iff $\aleph(X)=\Lambda$, and yet $X$ cannot be well ordered. In that case, $X$ is $\Lambda$-minimal iff for every $Y\subseteq X$, either ${}|Y|<\lambda$ or ${}|X\setminus Y|<\Lambda$.)

Hickman's argument uses Fraenkel-Mostowski models (and the Jech-Sochor embedding theorem).

See also the appendix to these notes for the argument that two power sets suffice unless $\aleph(X)=\aleph_\alpha$ for some infinite limit $\alpha < \aleph_\alpha$.

Comment by Andres Caicedo

2013-05-21T05:28:16Z

On the other hand, the axiom of choice is needed to show that the dimension of a vector space is well-defined: Without choice, we could have spaces without bases, or with bases of different sizes.

Comment by Andres Caicedo

2013-05-20T03:47:26Z

See also the follow-up mat.univie.ac.at/~michor/roots2.pdf

Comment by Andres Caicedo

2013-05-19T01:34:16Z

John, sorry, is your question the last sentence?

Comment by Andres Caicedo

2013-05-18T02:28:21Z

(And I first heard of this problem here: mathoverflow.net/questions/10102/…)

Comment by Andres Caicedo

2013-05-18T02:25:48Z

Comment by Andres Caicedo

2013-05-17T17:05:08Z

For the last example in the post, see mathoverflow.net/questions/130768/…

Comment by Andres Caicedo

2013-05-16T23:43:29Z

(Asaf: You may leave a comment at the beginning of the answer, indicating that the comments refer to a prior, completely different, version of the answer.)

Comment by Andres Caicedo

2013-05-15T22:56:49Z

Funny, when you mentioned this in your previous question, I almost asked for a reference. I'm still in the process of trying to dig one up myself. (In other news, I believe Marion and I owe you an email.)

Comment by Andres Caicedo

2013-05-14T22:22:31Z

Thank you, John. (It would be nice if they digitized the book so others can see it.)

Comment by Andres Caicedo

2013-05-11T23:37:07Z

For how a proof of item 3 can proceed, see math.stackexchange.com/questions/385630/…

Comment by Andres Caicedo

2013-05-11T17:17:20Z

@JohnStilwell I know this is an old comment, but could you please expand on it? I find this very interesting, and would be nice to mention something about it next time it comes up in lecture. (I know of no works criticizing Hermes's construction)

Comment by Andres Caicedo

2013-05-09T23:32:11Z

Comment by Andres Caicedo

2013-05-07T21:21:56Z

@Noah: In general that won't work: We could have $\theta$ measurable, and force it to become of cofinality $\omega$ without adding bounded subsets. Or we could already begin with $\theta$ of cofinality $\omega$, and then there is no cofinality change we can make.

Comment by Andres Caicedo

2013-05-05T20:30:47Z

Thanks, Joel. I figured Ali should have something on this question, and was planning to track down a reference.

Comment by Andres Caicedo

2013-05-05T18:30:43Z

Nice reference. Thanks!