What are some sets uncountable in ZF but countable in ZFC?
What about the reverse? That is, countable in ZF but uncountable in ZFC.
$\begingroup$
$\endgroup$
8
-
2$\begingroup$ 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. $\endgroup$– HallaSurvivorSep 25 at 21:03
-
1$\begingroup$ "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). $\endgroup$– Arturo MagidinSep 25 at 21:04
-
2$\begingroup$ 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. $\endgroup$– spaceisdarkgreenSep 25 at 21:14
-
$\begingroup$ @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. $\endgroup$– YamadaSep 25 at 21:14
-
1$\begingroup$ @Yamada “consistently x” means “not provably not x” or equivalently “there is a model of ZF where x holds”. $\endgroup$– spaceisdarkgreenSep 25 at 21:21
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
As the comments have already pointed out, since ZFC includes ZF, there is no set for which ZF proves it's uncountable but ZFC proves it's countable.
But perhaps what you have in mind is this: there are models of ZF in which AC fails, and in which (for example) the reals is a countable union of countabl sets. ZFC on the other hand proves that any countable union of countable sets is countable.
Such a model can be constructed by forcing. For example, see Halbeisen, Combinatorial Set Theory, Chapter 17. (You can find this example in many books on Axiomatic Set Theory that cover forcing.)
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.
answered Sep 25 at 22:22