User andres caicedo - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T11:03:18Z http://mathoverflow.net/feeds/user/6085 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/129704/if-zfc-has-a-transitive-model-does-it-have-one-of-arbitrary-size/129768#129768 Answer by Andres Caicedo for If ZFC has a transitive model, does it have one of arbitrary size? Andres Caicedo 2013-05-05T20:02:38Z 2013-05-06T00:50:47Z <p>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}$."</p> <p>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$.</p> <p>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&lt;\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$. </p> <p>Without choice, I do not know whether models of $\mathsf{ZF}$ of height $\kappa$ must have size $\kappa$.</p> <hr> <p>[<strong>Edit:</strong> In response to the last paragraph above, Joel and Asaf pointed out some results. I am including them here, to increase visibility.]</p> <p>In</p> <blockquote> <p>Ali Enayat. <em><a href="http://dx.doi.org/10.1007/s00153-004-0256-9%20" rel="nofollow">Models of set theory with definable ordinals</a></em>, Arch. Math. Logic <strong>44 (3)</strong>, (2005), 363–385. <a href="http://www.ams.org/mathscinet-getitem?mr=2140616" rel="nofollow">MR2140616 (2005m:03098)</a>, </p> </blockquote> <p>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</p> <blockquote> <p>Harvey Friedman. <em><a href="http://www.ams.org/journals/tran/1975-201-00/S0002-9947-1975-0416903-8/home.html" rel="nofollow">Large models of countable height</a></em>, Trans. Amer. Math. Soc. <strong>201</strong> (1975), 227–239. <a href="http://www.ams.org/mathscinet-getitem?mr=416903" rel="nofollow">MR0416903 (54 #4966)</a>.</p> </blockquote> <p>Let me quote from Harvey's paper:</p> <blockquote> <p>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}}$. </p> </blockquote> <p>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. </p> <p>Ali builds on this results to produce <em>Paris models</em> 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&lt;\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.</p> <p>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 <em>every</em> Paris model of $T$ is well-founded. </p> <p>(All this said, I do not understand this situation very well. It is all still rather surprising.)</p> http://mathoverflow.net/questions/48526/how-additive-is-lebesgue-measure-in-zfad/48530#48530 Answer by Andres Caicedo for How additive is Lebesgue measure in ZF+AD ? Andres Caicedo 2010-12-07T03:53:57Z 2013-05-04T16:26:53Z <p>Ricky:</p> <p>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.)</p> <p>Using $\mathsf{AD}^+ + V=L({\mathcal P}({\mathbb R}))$, Richard Ketchersid and I proved (in <em>A trichotomy theorem in natural models of ${\sf AD}^+$</em>, in <strong><a href="http://ams.org/bookstore-getitem/item=CONM-533" rel="nofollow">Set Theory and Its Applications</a></strong>, Contemporary Mathematics, <strong>533</strong>, Amer. Math. Soc., Providence, RI, 2011, pp. 227-258) that <em>every</em> set either is well-orderable, or is at least as large as ${\mathbb R}$. (The paper is available <a href="http://andrescaicedo.files.wordpress.com/2008/04/conm10510.pdf" rel="nofollow">here</a>, and it also provides an introduction to $\mathsf{AD}^+$.)</p> <p>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 <a href="http://math.stackexchange.com/a/372218/462" rel="nofollow">standard</a> that only countably many of them can be of positive measure. $(*)$</p> <p>This shows (under the listed assumptions) that Lebesgue measure is $\kappa$-additive for all (well-orderable) $\kappa$ but not $\tau$-additive for <em>any</em> non-well-orderable cardinal $\tau$.</p> <hr> <p>$(*)$ 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).</p> <p>From this it is easy to conclude the claim about measure zero sets, e.g., by looking at minimal counterexamples and adapting the standard <a href="http://math.stackexchange.com/a/88811/462" rel="nofollow">Sierpiński argument</a>; 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. </p> <p>(Unfortunately, although this Fubini theorem is not too hard, I am not sure of a reference for it. I remember vol. 5 of <a href="http://www.essex.ac.uk/maths/people/fremlin/mt.htm" rel="nofollow">Fremlin's treatise</a> 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}$.</p> http://mathoverflow.net/questions/129348/basis-theorem-due-to-solovay/129358#129358 Answer by Andres Caicedo for Basis theorem (due to Solovay?) Andres Caicedo 2013-05-01T22:41:20Z 2013-05-01T22:41:20Z <p>The result is indeed Solovay's Basis Theorem. </p> <p>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 </p> <blockquote> <p>Peter Koellner, and W. Hugh Woodin. <em>Large cardinals from determinacy</em>. In <strong>Handbook of set theory. Vols. 1, 2, 3</strong>, 1951–2119, Springer, Dordrecht, 2010. </p> </blockquote> <p>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).</p> http://mathoverflow.net/questions/129036/counterintuitive-consequences-of-the-axiom-of-determinacy/129040#129040 Answer by Andres Caicedo for Counterintuitive consequences of the Axiom of Determinacy? Andres Caicedo 2013-04-28T23:11:41Z 2013-05-01T18:10:12Z <p>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. </p> <p>(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.)</p> <p>$\mathsf{AD}$ implies that there are no nonprincipal ultrafilters on the natural numbers. This in turn has as a corollary that <em>every</em> ultrafilter is $\omega_1$-complete. It is this way that the first truly dramatic consequences of determinacy were established:</p> <p>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 <em>not</em> 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.) </p> <p>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 <em>every</em> 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)$. </p> <p>A recent result of Woodin is that <em>every</em> cardinal below $\Theta$ is in a sense of large cardinal character. More precisely, it is <a href="https://en.wikipedia.org/wiki/J%25C3%25B3nsson_cardinal" rel="nofollow">Jónsson</a>, 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 <a href="http://arxiv.org/abs/1304.2323" rel="nofollow">this</a> recent preprint in the ArxiV.</p> <p>The precise pattern of Jónsson cardinals under determinacy is still under investigation, but a nice place to start is the book</p> <blockquote> <p>Eugene Kleinberg. <strong>Infinitary combinatorics and the axiom of determinateness</strong>, Lecture Notes in Mathematics <strong>612</strong>, Springer-Verlag, Berlin-New York, 1977. <a href="http://www.ams.org/mathscinet-getitem?mr=479903" rel="nofollow">MR0479903 (58 #109)</a>.</p> </blockquote> <p>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 <em>every</em> infinite exponent relation fails. </p> <p>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</p> <blockquote> <p>W. Hugh Woodin. <em>The cardinals below</em> $|[\omega_1]^{&lt;\omega_1}|$. Ann. Pure Appl. Logic <strong>140 (1-3)</strong>, (2006), 161–232. <a href="http://www.ams.org/mathscinet-getitem?mr=2224057" rel="nofollow">MR2224057 (2007k:03136)</a>,</p> </blockquote> <p>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 <a href="http://math.stackexchange.com/a/243549/462" rel="nofollow">here</a> for more on this.</p> <p>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 <a href="http://andrescaicedo.files.wordpress.com/2008/04/conm10510.pdf" rel="nofollow">my paper</a> with Richard Ketchersid on a trichotomy result for additional, recent results, and some details on $\mathsf{AD}^+$. </p> <hr> <p>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 <a href="http://wwwmath.uni-muenster.de/persdb/show_perspage.php?id=674" rel="nofollow">Ben Miller</a>, is that most classical dichotomy theorems in descriptive set theory are soft consequences of graph-theoretic dichotomies via Baire category arguments, see</p> <blockquote> <p>Benjamin Miller. <em><a href="https://dl.dropboxusercontent.com/u/47430894/Web/publications/dichotomysurvey.pdf" rel="nofollow">The graph-theoretic approach to descriptive set theory</a></em>. Bulletin of Symbolic Logic, <strong>18 (4)</strong>, (2012), 554-575. </p> </blockquote> <p>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 <a href="http://andrescaicedo.files.wordpress.com/2010/10/luminy2010.pdf" rel="nofollow">here</a>. </p> http://mathoverflow.net/questions/124557/models-of-determinacy/124564#124564 Answer by Andres Caicedo for Models of Determinacy Andres Caicedo 2013-03-14T21:29:40Z 2013-03-14T21:29:40Z <p>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. </p> <p>More relevantly, if determinacy holds, then $L(\mathbb R)$ is a <em>derived model</em>, 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. </p> <p>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.)</p> <p>A good reference for both topics ($\mathbb R$-premice and derived models of mice) is the paper</p> <blockquote> <p>John R. Steel. <em>Derived models associated to mice</em>. In <strong>Computational prospects of infinity. Part I. Tutorials</strong>, pp. 105–193, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., <strong>14</strong>, World Sci. Publ., Hackensack, NJ, 2008. <a href="http://www.ams.org/mathscinet-getitem?mr=2449479" rel="nofollow">MR2449479 (2009m:03082)</a>. </p> </blockquote> <p>(A <a href="http://math.berkeley.edu/~steel/papers/Publications.html" rel="nofollow">preprint</a> is available at John's page, where you will also find preprints of papers presenting the derived model construction in detail.)</p> <p>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 <em>niceness</em> 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.)</p> <p>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:</p> <blockquote> <p>Ralf Schindler and John R. Steel. <strong><a href="http://wwwmath.uni-muenster.de/logik/Personen/rds/core_model_induction.pdf" rel="nofollow">The core model induction.</a></strong></p> </blockquote> <p>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:</p> <blockquote> <p>John R. Steel. <em>An outline of inner model theory</em>. In <strong>Handbook of set theory. Vols. 1, 2, 3</strong>, pp. 1595–1684, Springer, Dordrecht, 2010. <a href="http://www.ams.org/mathscinet-getitem?mr=2768698" rel="nofollow">MR2768698</a>. </p> </blockquote> <p>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 <a href="http://wwwmath.uni-muenster.de/logik/Personen/rds/core_model_induction_and_hod_mice.html" rel="nofollow">conference on the core model induction and hod mice</a>, Münster, July 19-August 06, 2010.</p> <p>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:</p> <blockquote> <p>Grigor Sargsyan. <a href="http://math.rutgers.edu/~gs481/hodmice.html" rel="nofollow"><em>A tale of hybrid mice</em></a>.</p> </blockquote> http://mathoverflow.net/questions/124391/omega-small-and-properly-small-premice/124441#124441 Answer by Andres Caicedo for $\omega$-small and properly small premice. Andres Caicedo 2013-03-13T18:02:15Z 2013-03-13T21:28:00Z <p>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. </p> <p>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$.</p> <p>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). </p> <p>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. </p> <p>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&lt;\alpha&lt;\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.</p> http://mathoverflow.net/questions/41913/david-gales-subset-take-away-game David Gale's subset take-away game Andres Caicedo 2010-10-12T15:40:50Z 2013-03-08T21:31:49Z <p>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: </p> <ul> <li>Richard K. Guy. <em>Unsolved problems in combinatorial games</em>. In <strong>Games of No Chance</strong>, (R. J. Nowakowski ed.) MSRI Publications 29, Cambridge University Press, 1996, pp. 475-491. </li> <li>J. Daniel Christensen and Mark Tilford. <em>David Gale's Subset Take-Away Game</em>. The American Mathematical Monthly, Vol. 104, No. 8 (Oct., 1997), pp. 762-766.</li> </ul> <p>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.</p> <p>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 <code>$\{a\}$</code> or <code>$\{b,c\}$</code>, and have II respond the other one. This means that when I comes to move again, only <code>$\{b\}$</code> and <code>$\{c\}$</code> remain, and II wins. </p> <p>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. </p> <p>The conjecture is that II always has a winning strategy.</p> <p>My question is whether there have been any further developments towards establishing this, or any additional references. Suggestions or related ideas are also welcome. </p> http://mathoverflow.net/questions/116633/sane-bound-on-number-of-moves-for-maker-breaker-game-on-mathbb-r2-for-0-1 Sane bound on number of moves for Maker-Breaker game on $\mathbb R^2$ for $\{0,1,2,3,4\}$ Andres Caicedo 2012-12-17T19:03:22Z 2013-03-03T03:51:20Z <p>The description below comes from </p> <ul> <li>József Beck. <strong>Combinatorial games. Tic-tac-toe theory</strong>, Encyclopedia of Mathematics and its Applications, <strong>114</strong>. Cambridge University Press, Cambridge, 2008, <a href="http://www.ams.org/mathscinet-getitem?mr=2402857" rel="nofollow">MR2402857 (2009g:91038)</a>.</li> </ul> <p>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.</p> <p>For example, denote by $A(n)$ the set consisting of $n$ points in a row in arithmetic progression, with common difference one. </p> <ul> <li>Maker has a winning strategy, in two moves, if $S=A(2)$.</li> <li>Maker has a winning strategy, in three moves, if $S=A(3)$. </li> <li>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).</li> </ul> <p>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:</p> <ol> <li>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 <code>$$\Delta_2(\mathcal F)=\max_{x\ne y\in V}|\{A\in\mathcal F\mid \{x,y\}\subseteq A\}|$$</code> 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$.</li> <li>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. </li> </ol> <p>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.</p> <p>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.</p> <p>My question:</p> <blockquote> <p>For $S=A(5)$, can we find a more decent bound on the number of moves? </p> </blockquote> <p>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:</p> <blockquote> <p>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.</p> </blockquote> http://mathoverflow.net/questions/119882/when-is-mathbbl-rank-definable-in-inner-models-of-mathbbv-mathbbl/119886#119886 Answer by Andres Caicedo for When Is $\mathbb{L}$-Rank Definable in Inner Models of $\mathbb{V} = \mathbb{L}$? Andres Caicedo 2013-01-25T20:16:21Z 2013-01-29T15:53:17Z <p>[<strong>Edit</strong>: The question is more subtle than I originally understood. I am leaving this here so as to avoid it being repeated by others.]</p> <p>You can define $&lt;'$ 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, $&lt;'$ restricted to $L^M$ is definable in $M$. The usual definition ($a,b\in L$ and $\rho(a)&lt;\rho(b)$) relativizes, so its definition from the point of view of $M$ gives the same relation as the definition of $&lt;'$ in $L$ restricted to elements of $L_\alpha$. </p> <p>A decent reference to see how $&lt;'$ relativizes and the amount of absoluteness involved is Devlin's book on "Constructibility".</p> http://mathoverflow.net/questions/117650/continuum-hypothesis/117653#117653 Answer by Andres Caicedo for Continuum Hypothesis Andres Caicedo 2012-12-30T17:29:19Z 2013-01-02T22:32:03Z <p>A classical reference is <strong>Hypothèse du Continu</strong> by Waclaw Sierpiński (1934), available through the <a href="http://pldml.icm.edu.pl/mathbwn/element/bwmeta1.element.dl-catalog-80f4c443-e772-4939-9305-45fe3beb92ec" rel="nofollow">Virtual Library of Science</a> as part of the series <em>Mathematical Monographs</em> of the Institute of Mathematics of the Polish Academy of Sciences. </p> <p>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 <a href="http://en.wikipedia.org/wiki/Martin%27s_axiom" rel="nofollow">Martin's Axiom</a>, and some are discussed in the original Martin-Solovay paper. </p> <p>(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 <strong>Handbook of Set Theory</strong>.)</p> <p>Of course, many equivalents were found after 1934. For example:</p> <ul> <li>Around 1943, Erdős and Kakutani proved that CH is equivalent to there being countably many Hamel bases whose union is <code>$\mathbb R\setminus\{0\}$</code>. </li> <li>In the early 60s, Erdős found a nice equivalent in terms of analytic functions (see Chapter 17 in Aigner-Ziegler <strong>Proofs from THE BOOK</strong>). </li> <li>Quite recently, Zoli proved that CH is equivalent to the transcendental reals being the union of countably many transcendence bases.</li> </ul> <p>I do not know of an encyclopedic work updating Sierpiński's monograph. Most recent work on CH centers on what Stevo Todorcevic calls <a href="http://www.math.toronto.edu/~stevo/dichotomies4.pdf" rel="nofollow"><em>Combinatorial Dichotomies in Set Theory</em></a>. 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. </p> <p>Though not specifically concerned with CH and its equivalences, you may find interesting Steprans's <a href="http://www.math.yorku.ca/~steprans/Research/PDFSOfArticles/hoc2INDEXED.pdf" rel="nofollow"><em>History of the Continuum in the Twentieth Century</em></a>.</p> <p>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$. </p> http://mathoverflow.net/questions/116463/delta1-2-well-ordering-vs-delta1-3/116465#116465 Answer by Andres Caicedo for $\Delta^1_2$-well ordering vs $\Delta^1_3$ Andres Caicedo 2012-12-15T17:14:59Z 2012-12-15T17:41:36Z <p>Hi Yu,</p> <p>No, your statement is equiconsistent with $\mathsf{ZFC}$. In </p> <blockquote> <p>Leo Harrington. <em>Long projective wellorderings</em>, Annals of Mathematical Logic 12 (1977) 1-21, <a href="http://www.ams.org/mathscinet-getitem?mr=465866" rel="nofollow">MR0465866 (57 #5752)</a>.</p> </blockquote> <p>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. </p> <p>(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.)</p> <p>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$. </p> <p>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. </p> <hr> <p>Some references:</p> <ul> <li><p>Mansfield result was nicely reproved by Alekos: Alexander Kechris. <em>The perfect set theorem and definable wellorderings of the continuum</em>, J. Symbolic Logic 43 (1978), no. 4, 630–634, <a href="http://www.ams.org/mathscinet-getitem?mr=1780138" rel="nofollow">MR0518668 (80b:03067)</a>.</p></li> <li><p>Sy D. Friedman. <strong>Fine structure and class forcing</strong>, de Gruyter Series in Logic and its Applications, 3. Walter de Gruyter &amp; Co., Berlin, 2000, <a href="http://www.ams.org/mathscinet-getitem?mr=1780138" rel="nofollow">MR1780138 (2001g:03001)</a>.</p></li> <li><p>Andrés E. Caicedo, Sy D. Friedman. <em>$\mathsf{BPFA}$ and projective well-orderings of the reals</em>, J. Symbolic Logic 76 (2011), no. 4, 1126–1136, <a href="http://www.ams.org/mathscinet-getitem?mr=2895389" rel="nofollow">MR2895389 (2012m:03123)</a>.</p></li> <li><p>For Welch's result, see: Ralf Schindler. <em>Coding into $K$ by reasonable forcing</em>, Trans. Amer. Math. Soc. 353 (2001), no. 2, 479–489, <a href="http://www.ams.org/mathscinet-getitem?mr=1804506" rel="nofollow">MR1804506 (2002c:03083)</a>.</p></li> </ul> http://mathoverflow.net/questions/112651/how-many-well-orderings-of-aleph-0-are-there/112653#112653 Answer by Andres Caicedo for How many well orderings of $\aleph_0$ are there? Andres Caicedo 2012-11-17T06:16:25Z 2012-11-18T06:34:14Z <p>Colin, there are continuum many, as you suspect. </p> <p>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 <code>$i\in\{0,1\}$</code> 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.</p> <p>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$. </p> <p>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.</p> http://mathoverflow.net/questions/112097/important-open-problems-that-have-already-been-reduced-to-a-finite-but-infeasible/112353#112353 Answer by Andres Caicedo for Important open problems that have already been reduced to a finite but infeasible amount of computation Andres Caicedo 2012-11-14T06:38:47Z 2012-11-14T06:58:35Z <p>This is an elaboration of a comment on Suvrit's answer. </p> <p>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. </p> <p>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. </p> <p>For example:</p> <ul> <li>$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 <code>$\{1,\dots,k\}$</code> such that the induced graph on <code>$C=\{1,\dots,m-1\}$</code> is blue, either admits a blue $K_m$, or a red $K_{n+1}$ with one of its vertices in $C$.</li> </ul> <p>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)$. </p> <ul> <li>$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. </li> </ul> <p>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.</p> <ul> <li>$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 <a href="http://www.math.uni-bonn.de/people/weinert/Poetry.pdf" rel="nofollow">here</a>. </li> </ul> http://mathoverflow.net/questions/112079/what-is-godels-pairing-function-on-ordinals/112088#112088 Answer by Andres Caicedo for What is Gödel's pairing function on ordinals? Andres Caicedo 2012-11-11T16:55:13Z 2012-11-11T19:17:38Z <p>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.</p> <p>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$.</p> <p>An ordinal $\alpha$ is <em>(additively) indecomposable</em> 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 <em>multiplicatively indecomposable</em> 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}$.</p> <p>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.</p> <hr> <p>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$).</p> <p>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$.</p> <p>(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.) </p> <p>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".</p> http://mathoverflow.net/questions/111283/number-of-linear-orders/111286#111286 Answer by Andres Caicedo for Number of linear orders Andres Caicedo 2012-11-02T16:22:15Z 2012-11-03T20:49:31Z <p>Hi Martin. </p> <p>I learned what follows in J.M. Plotkin, ed., <strong>Hausdorff on Ordered sets</strong>, AMS, History of Mathematics <strong>25</strong>, 2005.</p> <p>The result for countable ordered sets is due to Cantor. More precisely, Cantor produced continuum many countable order types: </p> <blockquote> <p>Assign to each $x\in 2^\omega$ the type $x_0+(\omega^*+\omega)+x_1+(\omega^*+\omega)+x_2+\dots$ </p> </blockquote> <p>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, <em>Untersuchungen aus der Mengenlehre</em>. That there are at most continuum many types was also found independently by Hausdorff (June 27, 1901, according to his <em>Nachlass</em>, during a Summer course on Set theory at the University of Leipzig); it is referred to as the "Cantor-Bernstein theorem" in Hausdorff's <em>Über eine gewisse Art geordneter Mengen</em>, Gesellschaft der Wissenschaften zu Leipzig, Mathematisch-Physische Classe <strong>53</strong> (1901), 460-475. (See pg. 460) </p> <p>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.)</p> <p>Bernstein gives two proofs of the upper bound. The first goes by identifying an ordered set $M$ with a function <code>$f:M^2\to\{-1,0,1\}$</code>: </p> <blockquote> <p>$f(a,b)=-1$ iff $a\lt b$, $f(a,b)=0$ iff $a=b$, and $f(a,b)=1$ iff $a\gt b$. </p> </blockquote> <p>One then just has to count such functions for $M=\mathbb N$. </p> <p>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$.</p> <hr> <p>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$. </p> <p>The lower bound is argued as follows: Given an infinite linearly ordered set $M$ of size $\mathfrak m=|M|$, call it <em>graded</em> 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$. </p> <p>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.) </p> http://mathoverflow.net/questions/110871/can-measures-be-added-by-forcing/110908#110908 Answer by Andres Caicedo for Can measures be added by forcing? Andres Caicedo 2012-10-28T15:18:13Z 2012-11-03T16:04:46Z <p>Just some comments to complement Joel's answer: </p> <p>That forcing can destroy and then recreate measurability is due to Kunen: </p> <blockquote> <p>Kenneth Kunen. <em>Saturated ideals</em>, The Journal of Symbolic Logic <strong>43 (1)</strong> (1978), 65–76. MR0495118 (80a:03068) </p> </blockquote> <p>The same is true for real valued measurability, this is due to Gitik: </p> <blockquote> <p>Moti Gitik, Saharon Shelah. <em>More on Real-valued measurable cardinals and forcing with ideals</em>, Israel Journal of Mathematics <strong>124</strong> (2001), 221–242 ([GiSh 582]). MR1856516 (2002g:03110)</p> </blockquote> <p>For a while it was open whether we can destroy and then reconstruct measurability while still <em>preserving</em> 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. </p> <p>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. </p> <p>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:</p> <blockquote> <p><em>Real-valued measurable cardinals and well-orderings of the reals</em>. In <strong>Set theory. Centre de Recerca Matemàtica, Barcelona, 2003–2004</strong>, Joan Bagaria, and Stevo Todorcevic, eds.; Trends in Mathematics, Birkhäuser Verlag, Basel, 2006, pp 83–120, MR2267147 (2007g:03064)</p> </blockquote> http://mathoverflow.net/questions/110877/effect-of-large-cardinals-on-the-value-of-omega-1l-in-l/110880#110880 Answer by Andres Caicedo for Effect of large cardinals on the value of $\omega_1^L$ in $L$ Andres Caicedo 2012-10-28T06:07:23Z 2012-10-28T06:07:23Z <p>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. </p> <p>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$.</p> <p>(Note that this also addresses (2), by taking $X=\emptyset$.)</p> <hr> <p>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 <a href="http://jdh.hamkins.org/multiverse-perspective-on-constructibility/" rel="nofollow">this post</a> by Joel. </p> http://mathoverflow.net/questions/110856/is-there-a-classification-of-or-work-towards-a-classification-of-countable-ordere/110858#110858 Answer by Andres Caicedo for Is there a classification of or work towards a classification of countable ordered sets? Andres Caicedo 2012-10-27T21:16:15Z 2012-10-27T21:16:15Z <p>Yes. The reference to get started is </p> <blockquote> <p>MR0662564 (84m:06001) Rosenstein, Joseph G. <strong>Linear orderings</strong>. Pure and Applied Mathematics, 98. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. </p> </blockquote> <p>The key idea is Hausdorff's notion of <em>scattered order</em>. 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). </p> <p>The key result is Laver's theorem that <em>Fraïssé’s conjecture</em> 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.</p> <p>(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^*$.)</p> <p>If you want to see how Hausdorff's analysis can be used, Laver's proof is the result to study. For an extension, see:</p> <blockquote> <p><a href="http://arxiv.org/abs/math/0411117" rel="nofollow">Continuous Fraïssé Conjecture</a>. Arnold Beckmann, Martin Goldstern, Norbert Preining. MR2470199 (2010a:03021) Order 25 (2008), no. 4, 281–298. </p> </blockquote> <p>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 <a href="http://math.stackexchange.com/questions/38575/any-good-decomposition-theorems-for-total-orders/38626#38626" rel="nofollow">this answer</a> to a related question on the sister site for more details.</p> http://mathoverflow.net/questions/109535/generalizing-feferman-levy/109735#109735 Answer by Andres Caicedo for Generalizing Feferman - Levy Andres Caicedo 2012-10-15T16:26:49Z 2012-10-15T19:10:58Z <p>Posting this as an answer at Colin's request. The second paragraph of the question is addressed at this other <a href="http://mathoverflow.net/questions/109680/does-zf-bound-countable-unions-of-countable-sets" rel="nofollow">MO question</a>. </p> <p>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:</p> <ul> <li>Devlin, Keith I.; Jensen, Ronald B. <em>Marginalia to a theorem of Silver</em>. In <strong>$\models$ISILC Logic Conference (Proc. Internat. Summer Inst. and Logic Colloq., Kiel, 1974)</strong>, G. H. Müller, A. Oberschelp, and K. Potthoff, eds., pp. 115–142. Lecture Notes in Math., Vol. 499, Springer, Berlin, 1975. <a href="http://www.ams.org/mathscinet-getitem?mr=480036" rel="nofollow">MR0480036 (58 #235)</a> </li> <li>Mitchell, William J. <em>The covering lemma</em>. In <strong>Handbook of set theory. Vols. 1, 2, 3</strong>, Kanamori, Foreman, eds., pp. 1497–1594, Springer, Dordrecht, 2010. <a href="http://www.ams.org/mathscinet-getitem?mr=2768697" rel="nofollow">MR2768697</a> </li> </ul> http://mathoverflow.net/questions/8972/do-sets-with-positive-lebesgue-measure-have-same-cardinality-as-r/26373#26373 Answer by Andres Caicedo for Do sets with positive Lebesgue measure have same cardinality as R? Andres Caicedo 2010-05-29T19:16:42Z 2012-09-29T22:48:19Z <p>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). </p> <p>The answer is yes. By elementary properties of Lebesgue measure (<a href="http://en.wikipedia.org/wiki/Regularity_theorem_for_Lebesgue_measure" rel="nofollow">regularity</a>), 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 <a href="http://en.wikipedia.org/wiki/Schroeder-Bernstein_theorem" rel="nofollow">Schroeder-Bernstein theorem</a>.)</p> <p>(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.)</p> <p>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.</p> http://mathoverflow.net/questions/108197/sets-of-reals-and-absoluteness/108200#108200 Answer by Andres Caicedo for Sets of reals and absoluteness Andres Caicedo 2012-09-27T00:54:28Z 2012-09-27T00:54:28Z <p>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$. </p> <p>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:</p> <blockquote> <p><strong>Theorem.</strong> 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}$.</p> </blockquote> <p>For a nice recent account of the argument, see Ilijas Farah, "A proof of the $\Sigma^2_1$ absoluteness theorem", in <strong>Advances in Logic</strong>, S. Gao, S. Jackson and Y. Zhang, eds., Contemporary Mathematics, 425 (2007) American Mathematical Society, RI., 9-22.</p> <p>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. </p> <p>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. </p> http://mathoverflow.net/questions/47185/why-is-there-no-borel-function-mapping-every-countable-set-of-reals-outside-itsel/47306#47306 Answer by Andres Caicedo for Why is there no Borel function mapping every countable set of reals outside itself? Andres Caicedo 2010-11-25T07:51:49Z 2012-09-22T19:28:49Z <p>[<strong>Edit, Sep. 22, 2012:</strong> 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|$. </p> <p>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}$. </p> <p>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 <code>$$f(\{a\in W\mid a\lt x\})=x$$</code> for any $x\in W$. But then $W$ witnesses that $f$ is not injective.]</p> <hr> <p>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$.</p> <p>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. </p> <p>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$. </p> <p>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$. </p> <p>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 <a href="http://mathoverflow.net/questions/26861/explicit-ordering-on-set-with-larger-cardinality-than-r/26893#26893" rel="nofollow">answer</a>.</p> <p>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.</p> <p>(Please let me know if I've misidentified $T_2$ and I'll edit accordingly.)</p> <p>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).</p> <hr> <p>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}$).</p> <p>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. </p> <p>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, <code>$0 ∗ S =\{0{}^\frown a \mid a \in S \}$</code> and similarly for $1 ∗ T$.</p> <p>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$).</p> <p>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.) </p> <p>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)$. </p> <p>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. </p> http://mathoverflow.net/questions/107851/extending-jordan-loops Extending Jordan loops Andres Caicedo 2012-09-22T15:41:45Z 2012-09-22T17:30:59Z <p>I encountered this issue recently, but do not know of any general results to deal with it, so I would appreciate any pointers. </p> <blockquote> <p>Let <code>$\mathbb T=\{z\in\mathbb C\mid |z|=1\}$</code>, 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$? </p> </blockquote> <p>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?</p> http://mathoverflow.net/questions/106640/solovays-paper-from-ad-that-all-sets-are-ramsey/106647#106647 Answer by Andres Caicedo for Solovay's paper from AD+ that all sets are Ramsey Andres Caicedo 2012-09-08T05:58:50Z 2012-09-08T11:58:02Z <p>About all you need is in Adrian's paper "<a href="http://www.ams.org/mathscinet-getitem?mr=491197" rel="nofollow">Happy families</a>". It is not spelled out as following from ${\sf AD}^+$, of course, since the concept did not exist yet. </p> <p>Anyway, if you are familiar with Solovay's arguments in his <a href="http://www.ams.org/mathscinet-getitem?mr=265151" rel="nofollow">paper</a> on all sets of reals being measurable (or as discussed in the Feng-Magidor-Woodin <a href="http://www.ams.org/mathscinet-getitem?mr=1233821" rel="nofollow">paper</a> on universally Baire sets), then all you want to read is section 2 (up to 2.2.3) of my <a href="http://www.ams.org/mathscinet-getitem?mr=2777751" rel="nofollow">paper</a> 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 <a href="http://andrescaicedo.wordpress.com/papers" rel="nofollow">page</a>.</p> <p>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.</p> <p>Since the proof uses the $\infty$-Borel machinery so explicitly, it is still open whether ${\sf AD}$ suffices for this result. </p> http://mathoverflow.net/questions/38771/dual-schroeder-bernstein-theorem Dual Schroeder-Bernstein theorem Andres Caicedo 2010-09-15T03:43:19Z 2012-08-14T15:17:10Z <p>This question was motivated by the comments to <a href="http://mathoverflow.net/questions/38754/dual-of-zorns-lemma" rel="nofollow">http://mathoverflow.net/questions/38754/dual-of-zorns-lemma</a></p> <p>Let's denote by the Dual Schroeder-Bernstein theorem (DSB) the statement </p> <blockquote> <p>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.</p> </blockquote> <p>In set theory without choice, assume that the Dual Schroeder-Bernstein theorem holds. Does it follow that choice must hold as well?</p> <p>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.</p> <p>The only reference I know for this is Bernhard Banaschewski, Gregory H. Moore, <em>The dual Cantor-Bernstein theorem and the partition principle</em>, Notre Dame J. Formal Logic <strong>31 (3)</strong>, (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.)</p> <p>The <em>partition principle</em> 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.</p> <p>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 <a href="http://wwwmath.uni-muenster.de:8013/persdb/show_perspage.php?id=674" rel="nofollow">page</a>.</p> <hr> <p><strong>Added Sep. 21. [Edited Aug. 14, 2012]</strong> It may be worthwhile to point out what is known, beyond the Banaschewski-Moore result mentioned above. </p> <p>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 <em>idemmultiple hypothesis</em> that $x\sqcup x$ is equipotent to $x$, for all infinite sets $x$, is strictly weaker than choice, as shown in Gershon Sageev, <em>An independence result concerning the axiom of choice</em>, Ann. Math. Logic 8 (1975), 1–184, MR0366668 (51 #2915). </p> <p>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.</p> http://mathoverflow.net/questions/24579/convergence-of-sumn3-sin2n-1 Convergence of $\sum(n^3\sin^2n)^{-1}$ Andres Caicedo 2010-05-14T06:09:43Z 2012-08-11T23:51:45Z <p>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. </p> <p>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}$.</p> <p>[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)&lt;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.]</p> <p>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 <em>ad hoc</em> approach just tailored to this specific series would be interesting as well.</p> http://mathoverflow.net/questions/103698/strictly-order-preserving-maps-into-the-integers Strictly order preserving maps into the integers Andres Caicedo 2012-08-01T15:45:06Z 2012-08-02T02:25:47Z <p>If $P$ and $P'$ are partial orders, a <em>strictly order preserving</em> 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$.</p> <p>An <em>interval</em> in $P$ is a set of the form <code>${}[x,y]=\{z\mid x\le z\le y\}$</code>, where $x\le y$. Note that points in an interval need not be comparable with one another. The <em>height</em> of an interval is the supremum of the lengths of $&lt;$-chains of elements in the interval.</p> <p>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. </p> <p>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 <a href="http://www.algebra.uni-linz.ac.at/~farley/erne.pdf" rel="nofollow">here</a>.</p> <blockquote> <p>Is there an example of size $\omega_1$, preferably one that does not require the axiom of choice?</p> </blockquote> http://mathoverflow.net/questions/103583/finite-measure-on-the-power-set/103585#103585 Answer by Andres Caicedo for Finite measure on the power set Andres Caicedo 2012-07-31T06:07:16Z 2012-07-31T14:46:03Z <p>I assume you mean a $\sigma$-additive measure. This is Ulam's <em>measure problem</em>. 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.</p> <p>You can see a quick write up of the argument <a href="http://caicedoteaching.wordpress.com/2009/03/05/580-cardinal-arithmetic-8/" rel="nofollow">here</a>. A good reference is the beginning of David Fremlin, "Real-valued measurable cardinals", in <strong>Set Theory of the reals</strong>, Haim Judah, ed., Israel Mathematical Conference Proceedings 6, Bar-Ilan University (1993), 151–304, that I also mention in the notes linked to above.</p> <p>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 <em>additivity</em> is the smallest cardinal $\kappa$ such that the measure of the disjoint union of some collection of $\kappa$ many disjoint subsets of $Y$ is <em>not</em> 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$.)</p> <p>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&lt;\lambda(F)&lt;\lambda(E)$), then $\lambda$ is <em>(atomlessly) real valued measurable</em>. 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.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Measurable_cardinal" rel="nofollow">measurable</a>. </p> http://mathoverflow.net/questions/102733/comparability-implies-well-orderability/102743#102743 Answer by Andres Caicedo for Comparability implies well-orderability? Andres Caicedo 2012-07-20T14:57:49Z 2012-07-20T14:57:49Z <p>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. </p> <p>($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)$.)</p> <p>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.</p> <p>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. </p> http://mathoverflow.net/questions/98365/hartogs-number-and-the-three-power-sets/98381#98381 Answer by Andres Caicedo for Hartogs number and the three power sets Andres Caicedo 2012-05-30T13:54:52Z 2012-05-31T02:12:58Z <p>Hi Asaf,</p> <p>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):</p> <blockquote> <p>In a message dated Jan. 28, I asked whether Sierpinski's ZF result that $\aleph(X) &lt; \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.</p> <p>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 &lt; \aleph_\alpha$.</p> <p>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)))$.</p> </blockquote> <p>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 <em>$\Lambda$-set</em> iff $\aleph(X)=\Lambda$, and yet $X$ cannot be well ordered. In that case, $X$ is <em>$\Lambda$-minimal</em> iff for every $Y\subseteq X$, either ${}|Y|&lt;\lambda$ or ${}|X\setminus Y|&lt;\Lambda$.) </p> <p>Hickman's argument uses Fraenkel-Mostowski models (and the Jech-Sochor embedding theorem).</p> <p>See also the appendix to <a href="http://caicedoteaching.wordpress.com/2009/02/02/580-some-choiceless-results-5/" rel="nofollow">these notes</a> for the argument that two power sets suffice unless $\aleph(X)=\aleph_\alpha$ for some infinite limit $\alpha &lt; \aleph_\alpha$.</p> http://mathoverflow.net/questions/131255/objects-which-cant-be-defined-without-making-choices-but-which-end-up-independen/131257#131257 Comment by Andres Caicedo Andres Caicedo 2013-05-21T05:28:16Z 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. http://mathoverflow.net/questions/105438/square-root-of-a-positive-c-infty-function/105445#105445 Comment by Andres Caicedo Andres Caicedo 2013-05-20T03:47:26Z 2013-05-20T03:47:26Z See also the follow-up <a href="http://mat.univie.ac.at/~michor/roots2.pdf" rel="nofollow">mat.univie.ac.at/~michor/roots2.pdf</a> http://mathoverflow.net/questions/131110/what-are-the-main-structure-theorems-on-finitely-generated-commutative-monoids Comment by Andres Caicedo Andres Caicedo 2013-05-19T01:34:16Z 2013-05-19T01:34:16Z John, sorry, is your question the last sentence? http://mathoverflow.net/questions/131013/one-element-not-belong-to-at-least-half-of-the-subsets Comment by Andres Caicedo Andres Caicedo 2013-05-18T02:28:21Z 2013-05-18T02:28:21Z (And I first heard of this problem here: <a href="http://mathoverflow.net/questions/10102/what-are-interesting-families-of-subsets-of-a-given-set/13626#13626" rel="nofollow" title="what are interesting families of subsets of a given set">mathoverflow.net/questions/10102/&hellip;</a>) http://mathoverflow.net/questions/131013/one-element-not-belong-to-at-least-half-of-the-subsets Comment by Andres Caicedo Andres Caicedo 2013-05-18T02:25:48Z 2013-05-18T02:25:48Z See also <a href="http://mathoverflow.net/questions/47419/difficult-examples-for-frankls-union-closed-conjecture" rel="nofollow" title="difficult examples for frankls union closed conjecture">mathoverflow.net/questions/47419/&hellip;</a> http://mathoverflow.net/questions/130193/does-this-property-of-a-partially-ordered-set-have-a-name Comment by Andres Caicedo Andres Caicedo 2013-05-17T17:05:08Z 2013-05-17T17:05:08Z For the last example in the post, see <a href="http://mathoverflow.net/questions/130768/cardinals-without-choice-interpolation-reference-wanted" rel="nofollow" title="cardinals without choice interpolation reference wanted">mathoverflow.net/questions/130768/&hellip;</a> http://mathoverflow.net/questions/130768/cardinals-without-choice-interpolation-reference-wanted/130772#130772 Comment by Andres Caicedo Andres Caicedo 2013-05-16T23:43:29Z 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.) http://mathoverflow.net/questions/130768/cardinals-without-choice-interpolation-reference-wanted Comment by Andres Caicedo Andres Caicedo 2013-05-15T22:56:49Z 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.) http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/27331#27331 Comment by Andres Caicedo Andres Caicedo 2013-05-14T22:22:31Z 2013-05-14T22:22:31Z Thank you, John. (It would be nice if they digitized the book so others can see it.) http://mathoverflow.net/questions/129036/counterintuitive-consequences-of-the-axiom-of-determinacy/129038#129038 Comment by Andres Caicedo Andres Caicedo 2013-05-11T23:37:07Z 2013-05-11T23:37:07Z For how a proof of item 3 can proceed, see <a href="http://math.stackexchange.com/questions/385630/does-well-ordering-of-the-proper-class-of-cardinal-numbers-imply-choice/385971#comment826091_385971" rel="nofollow" title="does well ordering of the proper class of cardinal numbers imply choice">math.stackexchange.com/questions/385630/&hellip;</a> http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials/27331#27331 Comment by Andres Caicedo Andres Caicedo 2013-05-11T17:17:20Z 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) http://mathoverflow.net/questions/27324/what-are-some-naturally-occurring-high-degree-polynomials Comment by Andres Caicedo Andres Caicedo 2013-05-09T23:32:11Z 2013-05-09T23:32:11Z See also <a href="http://math.stackexchange.com/q/387062/462" rel="nofollow">math.stackexchange.com/q/387062/462</a> http://mathoverflow.net/questions/130019/forcing-mildly-over-a-worldly-cardinal Comment by Andres Caicedo Andres Caicedo 2013-05-07T21:21:56Z 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. http://mathoverflow.net/questions/129704/if-zfc-has-a-transitive-model-does-it-have-one-of-arbitrary-size/129768#129768 Comment by Andres Caicedo Andres Caicedo 2013-05-05T20:30:47Z 2013-05-05T20:30:47Z Thanks, Joel. I figured Ali should have something on this question, and was planning to track down a reference. http://mathoverflow.net/questions/129666/classic-applications-of-baire-category-theorem/129738#129738 Comment by Andres Caicedo Andres Caicedo 2013-05-05T18:30:43Z 2013-05-05T18:30:43Z Nice reference. Thanks!