18
$\begingroup$

Let us denote by ACC the axiom of countable choice, namely the assertion that the product of countably many non-empty sets is non-empty, and denote by UCC the assertion that a countable union of countable sets is countable.

UCC is a simple theorem of ZF+ACC.

Proof Suppose for every $i\in\omega$ we have $X_i$ a countable set, and $X_i\cap X_j=\varnothing$ for $j\neq i$.

Since $X_i$ is countable $O_i=\{f\colon X_i\to\omega\mid f\ \text{ injective}\}$ is non-empty. We can choose $f_i\in O_i$ by the axiom of countable choice, and define: $$F\colon\bigcup X_i\to \omega\times\omega\colon\qquad x\mapsto\langle n,f_n(x)\rangle$$ Where $n$ is the unique $n\in\omega$ such that $x\in X_n$.

The Cantor pairing function shows that $\omega\times\omega$ is countable and we are done.

Is the opposite assertion is true, namely ZF+UCC implies ACC? If the answer is negative, does that imply at least some other weaker form of choice?

  • As noted by Emil Jeřábek below, UCC implies the axiom of countable choice for countable sets (the latter abbreviated as CCF).

  • Digging through the paper mentioned by godelian in the comments, I reached [1] in which Howard constructs a model of ZFA in which CCF holds and UCC does not, and by the transfer theorem of Pincus constructs this over ZF. Therefore we have: $$\text{ACC}\Rightarrow\text{UCC}\Rightarrow\text{CCF}$$ The first implication is irreversible in ZFA, by the comment of godelian, and the second irreversible in ZF by [1]. Both papers are two decades old, is there any known progress?

Bibliography:

  1. Howard, P. The axiom of choice for countable collections of countable sets does not imply the countable union theorem. Notre Dame J. Formal Logic Volume 33, Number 2 (1992), 236-243.
Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ UCC implies that the product of countably many nonempty countable sets is nonempty. $\endgroup$
    – Emil Jeřábek
    Commented Sep 7, 2011 at 12:57
  • $\begingroup$ Emil, is the proof done inductively by taking a "limit" of products of increasing finitely many of the countable sets? $\endgroup$
    – Asaf Karagila ♦
    Commented Sep 7, 2011 at 13:17
  • 1
    $\begingroup$ Assume that $X_i$ are countable nonempty for $i< \omega$. Then $X=\bigcup_iX_i$ is countable by UCC, hence we can fix an injection $f\colon X\to\omega$, and define a selector $g\in\prod_iX_i$ by $g(i)=f^{-1}(\min f[X_i])$. $\endgroup$
    – Emil Jeřábek
    Commented Sep 7, 2011 at 13:26
  • 1
    $\begingroup$ Here is how you can show that the countable product of nonempty countable sets is nonempty. Since the union is countable, it can be indexed by the natural numbers. This gives you a natural well-ordering of the union and hence every subset including all these countably many sets. This well-ordering allows you to pick an element from each of these countably many sets. $\endgroup$
    – Michael Greinecker
    Commented Sep 7, 2011 at 13:35
  • 7
    $\begingroup$ If we allow urelements then the implication is not provable. Moreover, countable choice is independent from the stronger assertion that the union of denumerable many sets of power $\aleph_\alpha$ has power $\aleph_\alpha$. This follows from the construction of a permutation model, see Howard, P., "Unions of well-ordered sets" - J. Austral. Math. Soc. Series A, 56 (pp. 117-124) for details (the article is available online). Unfortunately the statement does not seem to be transferable. $\endgroup$
    – godelian
    Commented Sep 7, 2011 at 17:48

1 Answer 1

Reset to default
7
$\begingroup$

The implication $ACC \implies UCC$ is irreversible in $ZF$. This follows again from the transfer theorem of Pincus:

  1. $UCC$ is an injectively boundable statement, see note 103 in "Consequences of the axiom of choice" by Howard & Rubin. Right after the theorem in pp. 285 and its corollary, there are examples of statements of this kind, one of which is form 31 (which is precisely $UCC$). The fact that this is the case follows in turn from the application of lemma 3.5 in Howard, P.-Solski, J.: "The strength of the $\Delta$-system lemma", Notre Dame J. Formal Logic vol 34, pp. 100-106 - 1993

  2. It is known that $¬ACC$ is boundable, and hence injectively boundable.

Then we can apply the transfer theorem of Pincus to the conjunction $UCC \wedge ¬ACC$ and we are done.

SECOND PROOF: Browsing through the "Consequences..." book I've just found another less direct proof of the same fact. I'm adding it here to avoid the interested person from looking it up for himself (especially since the AC website is not working these days). It involves form 9, known as $W_{\aleph_0}$: a set is finite if and only if it is Dedekind finite. Now, $ACC \implies W_{\aleph_0}$ is provable in $ZF$ (in fact this was already proved by Dedekind), while $UCC$ does not imply $W_{\aleph_0}$. The latter follows from the fact that in the basic Fraenkel model, $\mathcal{N}1$, $UCC$ is valid while $W_{\aleph_0}$ is not, and such a result is transferable by considerations of Pincus that can be found at Pincus, D.: "Zermelo-Fraenkel consistency results by Fraenkel Mostowski methods", J. of Symbolic Logic vol 37, pp. 721-743 - 1972 (doi:10.2307/2272420)

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Just for the sake of completeness, I will add here that $W_{\aleph_0}$ is to say that every infinite set has a countable subset, which is somewhat a clearer formulation in my opinion. $\endgroup$
    – Asaf Karagila ♦
    Commented Sep 18, 2011 at 6:22
  • 1
    $\begingroup$ Welcome! Actually it was quite instructive for me to think about this, for a change. And yes, I agree that the formulation you mention is clearer (and closer to its denomination). $\endgroup$
    – godelian
    Commented Sep 18, 2011 at 20:33

You must log in to answer this question.

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