How strong are weak choice principles?

Question

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.)

Answer 1

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.