35
$\begingroup$

I just read Dr Strangechoice's explanation that if all subsets of the real numbers are Lebesgue measurable, then you can partition $2^\omega$ into more than $2^\omega$ many pairwise disjoint nonempty subsets. Note that this paradoxical conclusion is a consequence of the Axiom of Determinacy.

I've read of many counterintuitive consequences of the Axiom of Choice, but what other consequences come from the Axiom of Determinacy?

(I am aware that AD is inconsistent with AC, and yes, AC being false is rather counterintuitive.)

$\endgroup$
6
  • 8
    $\begingroup$ The title is funny. If one is used to life under choice, just about every consequence of determinacy is counterintuitive. $\endgroup$ Apr 28, 2013 at 22:42
  • 2
    $\begingroup$ @Andres Caicedo: Isn't that only if you are both used to AC and find AC intuitive? I use AC, but I don't find it intuitive. $\endgroup$ Apr 29, 2013 at 0:30
  • 5
    $\begingroup$ @Douglas, certainly AC has many unintuitive aspects. However the plain formulation is very intuitive, because it's true for finite sets in a very obvious way. But regardless to AD or AC, everything involving infinite sets will end up having some counterintuitive and mind-boggling consequence. And I find that fact intuitive! :-) $\endgroup$
    – Asaf Karagila
    Apr 29, 2013 at 1:20
  • $\begingroup$ Almost all counterintuitiveness belongs to a museum. $\endgroup$ May 2, 2013 at 4:44
  • $\begingroup$ I am not a specialist but the names Steinhaus, Banach, Mazur and Mycielski ring a bell. $\endgroup$ Oct 10, 2016 at 3:45

3 Answers 3

30
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ Did I miss the news that "AD implies that all sets of reals $\dots$ are Ramsey"? I thought this was still open, though I knew that the conclusion was proved under AD${}_{\mathbb R}$. $\endgroup$ May 1, 2013 at 15:33
  • $\begingroup$ Hi Andreas: No, this is still open. I tried to keep the technicalities in the answer at a minimum, which introduced a few inaccuracies, such as writing $\mathsf{AD}$ instead of $\mathsf{AD}^+$, or not elaborating on the role of $\mathsf{DC}$ in Woodin's results. $\endgroup$ May 1, 2013 at 17:56
  • $\begingroup$ (The latest edit should have taken care of the inaccuracy.) $\endgroup$ May 1, 2013 at 18:10
19
$\begingroup$

Graph combinatorics is very different under AD to what we are used to under AC. For example, under AD there is an acyclic graph on $\mathbb{R}$ with no 2-coloring (indeed, no coloring with countably many colors). Hall's marriage theorem is also false, even in a very trivial case: there is a 2-regular bipartite graph on $\mathbb{R}$ with no perfect matching.

These theorems both follow from the assertion that every set of reals has the Baire property, and the arguments can be found in Kechris-Solecki-Todorcevic's 1999 paper: Borel Chromatic Numbers.

I also have a recent paper on descriptive combinatorics that directly uses the axiom of determinacy, and not just measure or category arguments. For example, I show that under AD, for every n, there is an acyclic n-regular graph on $\mathbb{R}$ with chromatic number n+1, and an acyclic bipartite n-regular graph with no perfect matching. The games I use are based on partitions of free products of countable groups into two pieces.

$\endgroup$
14
$\begingroup$

To name a few,

  1. There are no free ultrafilters on $\omega$.
  2. There is no Hamel basis to $\Bbb R$ over $\Bbb Q$.
  3. Under additional (but "reasonable") assumptions, every countable partial order embeds into the cardinals below $\mathcal P(\Bbb R)$.
  4. Every subset of $\omega_1$ either contains a closed and unbounded set, or is disjoint from one.
  5. For every finite $n>2$, $\aleph_n$ is a singular cardinal.
$\endgroup$
4
  • 1
    $\begingroup$ I didn't include many of the negations of the equivalents to the axiom of choice, e.g. counterexamples to Zorn's lemma; [comm. unital] rings without maximal ideals; and so on. Those were obvious because AC is false. $\endgroup$
    – Asaf Karagila
    Apr 28, 2013 at 22:55
  • 2
    $\begingroup$ This really highlights Douglas Zare's point that what's intuitive depends on whether AC is intuitive. I find (1) and (2) quite intuitive, and I gather that many more people did around a hundred years ago. (3) also seems reasonable, although I could imagine its going either way. ((4) and (5) are a little outside where I feel good intuitions.) $\endgroup$ May 1, 2013 at 19:05
  • $\begingroup$ For how a proof of item 3 can proceed, see math.stackexchange.com/questions/385630/… $\endgroup$ May 11, 2013 at 23:37
  • $\begingroup$ How does the proof of 5 go though ? $\endgroup$
    – Maxtimax
    Jan 29, 2017 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.