2
$\begingroup$

For this purposes of this question, a weak choice principle $W$ is a statement for which the following three statements hold

  • $ZFC$ proves $W$
  • $W$ is independent of $ZF$
  • $ZF+W$ does not prove $C$

Some examples of (what I think are) weak choice principles would be

  • Dependent choice
  • Countable choice
  • There exists a non-measurable set of reals
  • Ultrafilter lemma
  • Ultrafilter lemma, but only for filters on countable sets
  • Boolean Prime Ideal theorem
  • The countable union of countable sets is countable
  • The direct product of countably many nonempty sets is nonempty
  • Every infinite set has a countably infinite subset
  • Every infinite set is Dedekind-infinite

Now I've been able to look up the relations between some of these. Ultrafilter and Boolean Prime Ideal are equivalent. Countable choice proves countable union of countable sets are countable. Others I've had trouble with. Can countable choice prove the ultrafilter lemma?

So what I'm looking for is a nice big list of how various weak choice principles relate to each other. (Or, if there isn't such a thing, we make one.)

$\endgroup$
  • $\begingroup$ No, countable choice can’t prove the ultrafilter lemma. There is Herrlich’s textbook and also Howard and Rubin’s big book of facts. $\endgroup$ – spaceisdarkgreen Nov 16 '18 at 18:24
  • 1
    $\begingroup$ This is a whole diagram worth of answer. Also what do you mean direct product? $\endgroup$ – Asaf Karagila Nov 16 '18 at 18:56
  • 2
    $\begingroup$ You know that hundreds of pages were written on these kind of questions, right? $\endgroup$ – Asaf Karagila Nov 16 '18 at 18:58
4
$\begingroup$

Let me number those principles you mention.

  1. Dependent choice
  2. Countable choice
  3. There exists a non-measurable set of reals
  4. Ultrafilter lemma
  5. Ultrafilter lemma, but only for filters on countable sets
  6. Boolean Prime Ideal theorem
  7. The countable union of countable sets is countable
  8. The direct product of countably many nonempty sets is nonempty
  9. Every infinite set has a countably infinite subset
  10. Every infinite set is Dedekind-infinite

Equivalents

  • (9) is equivalent to (10). The direction (9) to (10) is easy, and (10) to (9) follows by taking an injection $f\colon X\setminus X\setminus\{x\}$ for some $x\in X$ and looking at $f^n(x)$ for $n\in\Bbb N$.
  • (4) is equivalent to (6). The proof from BPI to UF is fairly straightforward by noting that $\mathcal P(X)/\cal F$ is a Boolean algebra and a prime filter is an ultrafilter extending $\cal F$. In the other direction, the standard proofs go through additional equivalents like compactness theorems for first-order logic, or compactness theorems for product of finite discrete spaces.
  • (2) is equivalent to (8). This is really just the definition of a choice function.

Implications, all strict.

  • (1) implies (2). By looking at the relation of extending choice functions from finitely many members of the countable family.
  • (2) implies (9) and (7). Given an infinite $X$, choose from the family $\{A_n\mid n\in\Bbb N\}$ where $A_n$ is all the injective sequences of length $n$. Prove that the union of the chosen sequences is countable.
  • (4) implies (5). Trivial.
  • (5) implies (3). Not trivial. This follows from the 0-1 law, or Lebesgue density lemma. Looking at $2^\omega$ as a copy of the Cantor space, an ultrafilter, if measurable, is either of full measure or null. But a free ultrafilter is neither.

Anything else is not provable.

  • (4) is consistent with the failure of (10). This is Cohen's first model.
  • (1) is consistent with the failure of (3). This is Solovay's model. It does assume the consistency of inaccessible cardinals, a fact Shelah had shown to be necessary.
$\endgroup$
  • $\begingroup$ Looking up the terminology, what I called the direct product is the Cartesian product. $\endgroup$ – eyeballfrog Nov 16 '18 at 21:30
  • 1
    $\begingroup$ Okay. So that is just countable choice. $\endgroup$ – Asaf Karagila Nov 16 '18 at 21:31

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.