# What are some sets uncountable in ZF but countable in ZFC?

What are some sets uncountable in ZF but countable in ZFC?

What about the reverse? That is, countable in ZF but uncountable in ZFC.

• Since every model of ZFC is also a model of ZF, anything that ZF proves is uncountable will also be uncountable in ZFC (via the same proof). A more nuanced version of your question is what are some sets which are not provably countable in ZF, but which are provably countable in ZFC. One example of this is "a countable union of countable sets". Indeed, without some choice we can't prove that a countable union of countable sets is countable! Of course, depending on your model it may be the case that this union really is countable, it's just that ZF can't prove it. Sep 25 at 21:03
• "countable" means "bijectable with a subset of $\mathbb{N}$." So of course if a set $X$ is "countable in ZF" (meaning, we can prove such a function exists in ZF) then it is countable in ZFC. If by "uncountable" you mean "we can prove there is no bijection between the set and a subset of $\mathbb{N}$", then there is no set that we can prove is uncountable in ZF but countable in ZFC (it would imply set theory is consistent). However, there are sets that can prove are countable in ZFC (e.g., some countable unions of finite sets). Sep 25 at 21:04
• For a set that is provably uncountable in ZFC but consistently countable (in fact empty) in ZF: the set of all well-orderings of the reals. For a set that is provably countable (in fact empty) in ZFC, but consistently uncountable in ZF: the set of all partitions of the reals into a countable union of countable sets. Sep 25 at 21:14
• @HallaSurvivor "A countable union of countable sets" is a sentence. What about a concrete set? I mean, a certain set whose existence can be proved in ZF but whose countability can't, and yet ZFC can prove its countability. Sep 25 at 21:14
• @Yamada “consistently x” means “not provably not x” or equivalently “there is a model of ZF where x holds”. Sep 25 at 21:21

While the forcing construction is far too technical to explain here, I can at least explain how the proof of the statement "a countable union of countable sets is countable" uses AC. If $$X$$ is a countable union $$X=\bigcup_{i\in\omega}X_i$$, and each $$X_i$$ is countable, that means that for each $$X_i$$, there exists a bijection with $$\omega$$. But to carry over the usual bijection of $$\omega\times\omega$$ with $$\omega$$ to $$X$$, you'll need to choose a particular bijection for each $$X_i$$. Without AC, you can't show that this is possible.