19
$\begingroup$

It is well-known that Axiom of Choice has several consequences which might be viewed as counter-intuitive or undesirable. For example, existence of non-measurable sets or Banach-Tarski Paradox. H. Herrlich's book on AC has a chapter aptly named Disasters with Choice.

But omitting Axiom of Choice and working in ZF alone might lead to even more weird things. (Again, just have a glance at the table of contents of the same book and check various things mentioned in the chapter Disaster without Choice.)

Therefore there have been some suggestions on possible replacements of AC. For example, for some things working with ZF+countable choice is enough.

One of possible candidates is Axiom of Determinacy. For example, it is known that AD implies countable choice for sets of real numbers. (See, for example Theorem 9.29 in L. Bukovský: The Structure of the Real Line.) Again, for some purposes this version of AC might be sufficient. AD also implies that every subset of $\mathbb R$ is Lebesgue measurable.

Let me quote from the book Pavol Zlatoš: Ani matematika si nemôže byť istá sama sebou - Úvahy o množinách nekonečne, paradoxoch a Gödelových vetách; (Even mathematics cannot be certain about itself, Essays on sets, infinity, paradoxes, and Gödel’s theorems, in Slovak), page 117.

The (not very good) translation is mine. This excerpt follows after mentioning French school represented by R. Baire, E. Borel and H. Lebesgue and Russian school lead by N. N. Luzin.

Both these schools substantially used set-theoretical methods in analysis, topology, theory of functions, measure theory, etc., but Zermelo's proof of well-orderability of continuum and some other "unpleasant" consequences of Axiom of Choice disconcerted them to the extent that they challenged this axiom and ineffective existential proofs in general.

Let us mention that if Axiom of Determinacy had been known at the time, it is possible - or even probable - that these four great mathematicians would have given preference to this axiom over Axiom of Choice. Using Axiom of Determinacy it is possible to build nicer, more elegant and unified descriptive set theory, where various pathological (e.g., non-measurable) subsets of real numbers are impossible.

Or the quote at the beginning of the chapter on AD in H. Herrlich's book (which is attributed to U. Felgner and K. Schulz):

Among all alternatives to the axiom of choice AC the axiom of determinateness AD undoubtedly is the most interesting.

I wonder whether working in ZF+AD would also lead to some consequences which some people might consider undesirable.

  • What are consequences of Axiom of Determinacy which might seem antiintuitive/problematic/paradoxical?
|cite|improve this question
$\endgroup$
  • 4
    $\begingroup$ I do not think of this as disasters, but see the answer I gave to the equivalent MO question. $\endgroup$ – Andrés E. Caicedo Jan 14 '15 at 14:42
  • 1
    $\begingroup$ Intuition changes with time, as is the perception of what is paradoxical. Problematic depends on what you're trying to do. If you're using the Hahn-Banach theorem heavily, you will find its failure to be an absolute disaster. If you're only working with the natural numbers, that much won't bother you. $\endgroup$ – Asaf Karagila♦ Jan 14 '15 at 15:23
  • 1
    $\begingroup$ You may also want to consult Apollo Hogan's thesis (General topology under the axiom of determinacy). One of his goals was to indicate that what we obtain is not disastrous, as opposed to the general situation in the absence of choice. $\endgroup$ – Andrés E. Caicedo Jan 14 '15 at 15:29
  • 2
    $\begingroup$ @AsafKaragila I think you just proved $V\neq L(\mathbb{R})$. There are probably people in California who would like to talk to you. $\endgroup$ – Miha Habič Jan 14 '15 at 17:19
  • 2
    $\begingroup$ @Miha: All in all, I'm an interesting person. I'm sure that there are people in many places that would like to talk to me. $\endgroup$ – Asaf Karagila♦ Jan 14 '15 at 23:24
30
$\begingroup$

It might not be a disaster, but I've always thought it counterintuitive that there is an equivalence relation on the real line with strictly more than continuum many equivalence classes. The equivalence relation isn't even very complicated; it's just congruence modulo $\mathbb Q$ in the additive group of $\mathbb R$. In other words: Vitali wants to give you his standard example of a non-measurable set, and, if you prevent him from doing so, he gets his revenge with this example of partitioning a set into strictly more pieces than it has elements.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for your answer. For the benefit of other users I will add links to two posts by Andres Caicedo mentioning this (the possibility/consistency of cardinality of $\mathbb R/\mathbb Q$ being larger than cardinality of $\mathbb R$). One of them here and one of them on MO. (The second link was already mentioned in the comments to the question.) $\endgroup$ – Martin Sleziak Feb 15 '15 at 6:17
  • $\begingroup$ That's not quite a disaster from determinacy, rather a disaster from measurability (which is a consequence). @Martin: If those sort of disasters are of interest to you, then we can also include the failure of Hahn-Banach, compactness theorem, and other similar consequences from consequences much weaker than determinacy per se. $\endgroup$ – Asaf Karagila♦ Feb 15 '15 at 9:35
  • 1
    $\begingroup$ @AJY Fortunately, "inherently absurd" doesn't count for much in mathematics; try to deduce a contradiction, and see how you'll need the axiom of choice. On the other hand, "inherently absurd" makes good sense to me on the level of psychology; that's why I gave this answer. The inherent absurdity seems to provide a reason for believing the axiom of choice, a sort of counterweight to the alleged inherent absurdity of the Banach-Tarski paradox. $\endgroup$ – Andreas Blass May 18 '16 at 18:25
  • 1
    $\begingroup$ @AJY That's right. I"m not saying that this inequality is equivalent to AC, only that the inequality isn't provable from the other axioms of set theory; in that sense, AC is needed. The "obvious" proof would be to map $\mathbb R/\mathbb Q$ one-to--one into $\mathbb R$ by sending each coset to one of its members; that idea directly invokes the axiom of choice. There might be some non-obvious proofs, but they'll all need some form of choice. $\endgroup$ – Andreas Blass May 18 '16 at 18:32
  • 2
    $\begingroup$ @AJY I don't think you wrote what you meant in the first clause of your comment. There certainly is a surjection $\mathbb R\to\mathbb R/\mathbb Q$ (no choice needed). The rest is correct; in the absence of AC, there might be no injection in the other direction. $\endgroup$ – Andreas Blass May 18 '16 at 22:16
8
$\begingroup$

Determinacy arguably leads to some disasters in cardinal arithmetic. For instance, under AD we have that $\omega_n$ is singular - that is, can be written as a union of fewer-than-$\omega_n$-many sets each of size $<\omega_n$ - for all finite $n>2$. See Asaf's answer to my question on arithmetic in AD.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ If I'm not mistaken, we have that $\omega_n$ has cofinality precisely $\omega_2$ for all $2<n<\omega$. $\endgroup$ – Wojowu Dec 20 '16 at 8:36
-3
$\begingroup$

You need AC to prove Gödel's completeness theorem, and that is a big deal.

See the wikipedia article on Completeness Theorem which I cannot make link.

|cite|improve this answer
$\endgroup$
  • 6
    $\begingroup$ You only need AC to prove the completeness theorem over arbitrary languages. Over countable languages, you can prove it in ZF. $\endgroup$ – Eric Wofsey Dec 17 '16 at 21:50
  • 1
    $\begingroup$ Eric is right. There are even constructive accounts of (some forms of) Gödel's completeness theorem, see for instance the very nice paper by Herbelin and Ilik. $\endgroup$ – Ingo Blechschmidt Jan 18 '18 at 17:08
  • $\begingroup$ Well gee...thank you for the comments. The paper was very cool! $\endgroup$ – Scott Grizzard Jun 30 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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