Countable Unions And The Axiom Of Countable Choice - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T09:28:34Z http://mathoverflow.net/feeds/question/74743 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/74743/countable-unions-and-the-axiom-of-countable-choice Countable Unions And The Axiom Of Countable Choice Asaf Karagila 2011-09-07T12:51:06Z 2011-09-18T04:36:08Z <p>Let us denote by <strong>ACC</strong> the axiom of countable choice, namely the assertion that the product of countably many non-empty sets is non-empty, and denote by <strong>UCC</strong> the assertion that a countable union of countable sets is countable.</p> <p>UCC is a simple theorem of ZF+ACC.</p> <p><em>Proof</em> Suppose for every $i\in\omega$ we have $X_i$ a countable set, and $X_i\cap X_j=\varnothing$ for $j\neq i$. </p> <p>Since $X_i$ is countable <code>$O_i=\{f\colon X_i\to\omega\mid f\ \text{ injective}\}$</code> 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$.</p> <p>The Cantor pairing function shows that $\omega\times\omega$ is countable and we are done.</p> <hr> <p>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?</p> <ul> <li><p>As noted by Emil JeÅ™ábek below, UCC implies the axiom of countable choice for countable sets (the latter abbreviated as CCF). </p></li> <li><p>Digging through the paper mentioned by <em>godelian</em> 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?</p></li> </ul> <p><em>Bibliography:</em></p> <ol> <li>Howard, P. <strong><a href="http://projecteuclid.org/euclid.ndjfl/1093636102" rel="nofollow">The axiom of choice for countable collections of countable sets does not imply the countable union theorem.</a></strong> <em><a href="http://projecteuclid.org/handle/euclid.ndjfl" rel="nofollow">Notre Dame J. Formal Logic</a> Volume 33, Number 2 (1992), 236-243.</em></li> </ol> http://mathoverflow.net/questions/74743/countable-unions-and-the-axiom-of-countable-choice/75711#75711 Answer by godelian for Countable Unions And The Axiom Of Countable Choice godelian 2011-09-18T00:46:57Z 2011-09-18T04:36:08Z <p>The implication $ACC \implies UCC$ is irreversible in $ZF$. This follows again from the transfer theorem of Pincus:</p> <p>1) $UCC$ is an injectively boundable statement, see note 103 in "Consequences of the axiom of choice" by Howard &amp; 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 <a href="http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?handle=euclid.ndjfl/1093634567&amp;view=body&amp;content-type=pdf_1" rel="nofollow">Howard, P.-Solski, J.: "The strength of the $\Delta$-system lemma", Notre Dame J. Formal Logic vol 34, pp. 100-106 - 1993</a></p> <p>2) It is known that $¬ACC$ is boundable, and hence injectively boundable.</p> <p>Then we can apply the transfer theorem of Pincus to the conjunction $UCC \wedge ¬ACC$ and we are done. </p> <p>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 <a href="http://consequences.emich.edu/conseq.htm" rel="nofollow">AC website</a> 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 <a href="http://www.jstor.org/pss/2272420" rel="nofollow">Pincus, D.: "Zermelo-Fraenkel consistency results by Fraenkel Mostowski methods", J. of Symbolic Logic vol 37, pp. 721-743 - 1972</a></p>