7
$\begingroup$

A number of results that people use that require the axiom of choice (i.e. do not follow from ZF alone) are known to actually imply the axiom of choice. Therefore, one might naturally wonder whether there are results that require choice to prove yet which, on the contrary, do not imply choice.

The most natural answer to this question is countable choice, or $\kappa$-choice for cardinals $\kappa$.

Therefore, I wonder, are there other (i.e. not equivalent to any of the above) examples of results with this property? What about which are strictly stronger or weaker than all the cardinal-choice axioms (but not equivalent to ZF or ZFC)? In particular, I am interested in results occurring naturally in algebra, geometry, etc. And whether or not there are, is there a deeper reason why results that use choice tend to imply it?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ I'm not certain I understand "require choice to prove". For instance, one can prove countable choice from dependent choice; we don't require the full axiom of choice to prove it. We "require" AC if AC is necessary to prove some statement P, but I can't think of a meaning this might have that isn't the same as AC is a necessary consequence of P. $\endgroup$
    – Todd Trimble
    Commented Nov 25, 2012 at 4:09
  • 1
    $\begingroup$ Todd, it's actually quite reasonable to say that "The countable union of countable sets is not provable without the axiom of choice" as a shorthand to "We cannot prove it from ZF, but we can prove it from ZFC". There are weak choice principles which really cannot be formulated in terms of partial choice or bounded choice, and the only way to "pinpoint" their strength is a tautological "$\varphi$ is not provable from ZF without assuming $\varphi$ holds." of some sort. $\endgroup$
    – Asaf Karagila ♦
    Commented Nov 25, 2012 at 11:31
  • $\begingroup$ @Asaf: I agree. The OP made an edit after I made the comment which reflects what you just said, and I'm happy now. Something that's interesting is that principles that seem to "require choice" in this shorthand sense often wind up being elevated to choice principles in their own right, and people wind up studying the mathematics of ZF + weakened choice principle, as you were perhaps delicately suggesting at the end. $\endgroup$
    – Todd Trimble
    Commented Nov 25, 2012 at 13:08
  • $\begingroup$ @Todd, I actually posted a question about this: mathoverflow.net/questions/104016/… $\endgroup$
    – Asaf Karagila ♦
    Commented Nov 25, 2012 at 13:56
  • 1
    $\begingroup$ @Asaf: that's an interesting discussion! $\endgroup$
    – Todd Trimble
    Commented Nov 25, 2012 at 15:01

8 Answers 8

Reset to default
11
$\begingroup$

A diagram is worth a thousand words.

Taken from the beautiful book by Herrlich, Axiom of choice, Lecture Notes in Mathematics 1876, Springer 2006. Most of the implications are one-way implications, i.e., known to be not reversible:

https://i.sstatic.net/4KMFB.png

Improve this answer
$\endgroup$
1
  • $\begingroup$ Since I am a new user I am not allowed to post image links. Could somebody please change the answer in such a way that the diagram is displayed? Thanks. $\endgroup$
    – AoC
    Commented Nov 26, 2012 at 7:27
9
$\begingroup$

There's a huge amount of information about statements intermediate between "provable in ZF alone" and "provably equivalent to AC" in the book "Consequences of the Axiom of Choice" by Paul Howard and Jean Rubin.

Since you asked specifically about statements stronger than all the cardinal-choice axioms (I assume you mean well-ordered cardinals, i.e., alephs), there's the conjunction of all of them, the axiom of well-ordered choice: "Any well-orderable family of nonempty sets has a choice function." A clever result of Jensen says that this implies dependent choice, which does not follow from $\kappa$-indexed choice for any single $\kappa$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It should be added that Jensen's result extends to show that it is consistent with the negation of $\DC_{\omega_1}$. $\endgroup$
    – Asaf Karagila ♦
    Commented Nov 25, 2012 at 8:03
5
$\begingroup$

Generalizing a bit from ZF with a classical (Boolean) meta-logic: in constructive set theory, there are quite a few choice-principles that are studied in addition to those mentioned earlier, for example the presentation axiom, the axiom of multiple choice, the axiom of weakly initial set of covers, the axiom of small violations of choice, and others. These principles are considerably weaker than AC (even if we assume classical logic).

There is a famous result in topos theory called Diaconescu's theorem which states that if AC is satisfied in a topos, then so is the law of the excluded middle (so that excluded middle can itself be considered a weak choice principle; see here). So full AC is (unsurprisingly) generally considered unacceptable to those who wish to work in intuitionist or constructive settings; on the other hand, the choice principles mentioned above are often felt to be acceptable to constructivists. Toby Bartels, who is sometimes seen here at MO, is an expert on these matters.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ I am not a fan of naming another axiom as AMC... I demand to speak with the supervisor! :-) $\endgroup$
    – Asaf Karagila ♦
    Commented Nov 25, 2012 at 15:55
  • $\begingroup$ Sorry, what does AMC stand for otherwise? $\endgroup$
    – Todd Trimble
    Commented Nov 25, 2012 at 16:50
  • 1
    $\begingroup$ I think it's very important to add that AC implies PEM only in the presence of extensionality. Intensional constructive systems often admit full AC because that captures the constructive meaning of existence. In fact, it is extensionality that is the real non-constructive axiom here. I wrote about this here - dorais.org/archives/1031 $\endgroup$
    – François G. Dorais
    Commented Nov 25, 2012 at 16:58
  • $\begingroup$ Todd, the same initials: Axiom of Multiple Choice. Only that the "original" AMC is equivalent to AC in ZF. Blass used it in his proof that "Every vector space has a basis" implies AC in ZF. $\endgroup$
    – Asaf Karagila ♦
    Commented Nov 25, 2012 at 17:05
  • $\begingroup$ Francois: that's a very nice comment (and post at your website). $\endgroup$
    – Todd Trimble
    Commented Nov 25, 2012 at 17:20
4
$\begingroup$

An interesting dividing line, different from the ones you see in the cardinal choice axioms, is connected to the Tychonoff theorem saying that products of compact spaces are compact. The general Tychonoff theorem implies full choice, but when restricted to Hausdorff spaces, then the Tychonoff theorem is equivalent to the Boolean prime ideal theorem which in turn is equivalent to the existence of maximal ideals in commutative unitary rings. The Boolean prime ideal theorem says that every ideal in a Boolean algebra is contained in a maximal ideal.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @StephanGeschke: Is the existence of maximal ideals in countable commutative unitary rings equivalent to $ACA_{0}$ over $RCA_{0}$? $\endgroup$
    – Thomas Benjamin
    Commented Dec 6, 2017 at 7:31
4
$\begingroup$

We say that a set is Dedekind-finite if there is no proper subset of the same cardinality. Every finite set is Dedekind-finite, and assuming the axiom of choice the converse is also true. In fact even assuming countable choice is enough.

However, the axiom "Every Dedekind-finite set is finite" is strictly weaker than the axiom of countable choice.

In fact the axiom "The countable union of countable set is countable" is also weaker than the axiom of countable choice.

In the spirit of the above, there are several other propositions which are provable from the axiom of countable choice, and are consistent with the assumption "There exists an infinite Dedekind-finite" (but do not imply it), for example "Every infinite set can be split into two disjoint infinite sets".

Generally speaking, there are several "orthogonal" choice principles (and their obvious extensions, etc.) for example axiom of choice for families of size $\kappa$ is generally independent from choice principles like the Boolean Prime Ideal Theorem (and its consequences).

The generalized Kinna-Wagner principle, while related to the Boolean Prime Ideal theorem can be shown to hold even when BPIT fails badly (e.g. there exists an amorphous set which cannot be linearly ordered). This principle is also a good example for something independent from the "choice-related" choice principles (again, if there is an amorphous set countable choice fails badly).

Improve this answer
$\endgroup$
2
  • $\begingroup$ @Asaf: In the paragraph beginning "In the spirit" I think some text is missing. The first italicized assertion isn't actually an assertion, and the second is a consequence of AC so it can't imply the existence of an infinite Dedekind-finite set. $\endgroup$
    – Andreas Blass
    Commented Nov 25, 2012 at 15:09
  • $\begingroup$ @Andreas: Thank you for the corrections. I hope the edit is better. $\endgroup$
    – Asaf Karagila ♦
    Commented Nov 25, 2012 at 15:19
3
$\begingroup$

Eric Schecter's Handbook of Analysis and Its Foundations is an excellent source for questions like this in analysis. He has some information on the subject on his home page.

One example he gives that's not equivalent to countable choice or the Boolean prime ideal theorem is the Hahn-Banach Theorem.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The Hahn-Banach theorem is a consequence of the Boolean Prime Ideal Theorem mentioned by Stefan Geschke below, by the way. $\endgroup$
    – Asaf Karagila ♦
    Commented Nov 25, 2012 at 13:54
  • $\begingroup$ In fact, the Hahn-Banach theorem is (in one version) equivalent to the existence of finitely additive probability measure on every Boolean algebra (whereas an ultrafilter or prime ideal can be seen as a finitely additive $\{0,1\}$-valued measure). $\endgroup$
    – Goldstern
    Commented Nov 25, 2012 at 18:18
  • $\begingroup$ Right, but it's not equivalent to it, which if I understand the intent of the original question properly, makes it a distinct example. $\endgroup$
    – arsmath
    Commented Nov 25, 2012 at 19:30
  • $\begingroup$ arsmath, I was just complementing. Didn't argue that you gave a "duplicated" answer. $\endgroup$
    – Asaf Karagila ♦
    Commented Nov 25, 2012 at 19:39
  • $\begingroup$ No worries, Asaf. $\endgroup$
    – arsmath
    Commented Nov 25, 2012 at 21:12
3
$\begingroup$

Here's one that I think a lot of people don't realize: the existence of free algebras for all (possibly infinitary) algebraic theories. In his paper "Words, free algebras, and coequalizers" Andreas Blass proved that (assuming the consistency of a proper class of compact cardinals) it is impossible to prove this in ZF. (I don't know for sure that it is strictly weaker than AC, but it seems to me extremely unlikely to be equivalent to AC.) I think this is especially interesting because it doesn't look like any sort of choice principle itself.

Improve this answer
$\endgroup$
2
$\begingroup$

The Banach-Tarski theorem is a famous example of a result following from a weaker-than-ZFC extension of ZF. The Wikipedia article about it says more. I don't know if I'd say it occurs "naturally in algebra, geometry, etc".

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Amusingly enough, the BT theorem follows from the Hahn-Banach theorem (which was mentioned in another post), and in turn the Hahn-Banach theorem follows from the Boolean Prime Ideal theorem (which was also mentioned in another answer here)! $\endgroup$
    – Asaf Karagila ♦
    Commented Nov 25, 2012 at 23:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .