# Absoluteness of Countability

Let M be a countable transitive model for ZFC, P is a partial order in M. Notions like "partial orders" and "dense" are absolute. Consider the following set $S$={$D\in M: D$ is dense in $P$} = {$D: D$ is dense in $P$}$^M$, the superscript notion denotes relativization. The remark is the set is usually not countable in $M$. (Note: since $M$ is countable, from $V$, the class of all sets, anything lies in $M$ should be countable with respect to $V$). I know from Skolem's Paradox, countability is not absolute. However, if considering the following function: f: $S$ $\rightarrow$ $\omega$ and f is in $V$ and f is injective. Since $f\in P(S\times \omega)$, and $S, \omega \in M$, therefore, by the fact that $M$ is a transitive model of ZFC $f \in M$. The only conclusion I can draw at this point is when relativized to $M, f$ is not one-to-one. However, I feel confused and could not see how this is the case. I am asking for somewhat better example illustrating the non-absoluteness of notion of countability.

By the way, the question originates from Chapter VII Section 2 on Kunen's Set Theory (1980).

-
In the definition of $S$, I think you mean to say "$D$ is dense in $P$", rather than dense in $M$. –  Joel David Hamkins Jun 23 '12 at 15:04
There is an error in the sentence "Since $f\in P(S\times\omega)$, and $S,\omega\in M$, therefore, by the fact that $M$ is a transitive model of ZFC, $f\in M$." The conclusion $f\in M$ would follow by transitivity if you knew that $f$ is a member of some set in $M$. Unfortunately, $P(S\times\omega)$ is not in $M$, even though $S\times\omega$ is. The power set operation is not absolute, and $P^M(S\times\omega)$, which is in $M$, doesn't contain your $f$. On the other hand, "one-to-one" is absolute, so, if you had a function in $M$, it would be one-to-one in $M$ iff it is one-to-one in $V$. –  Andreas Blass Jun 23 '12 at 15:59
Thank you Joel. You are right. –  Zhang Jing Jun 23 '12 at 16:24
Thank you Andreas. You are right. Power set operation is not absolute. $P(x)^M=P(x) \cap M$. I missed that. –  Zhang Jing Jun 23 '12 at 16:31

You asked for an example to show that countability is not absolute to transitive models of set theory.

If there is any transitive model of set theory, then by the Lowenheim-Skolem theorem this model has a countable elementary substructure, whose Mostowski collapse provides a countable transitive model $M$ of set theory (enough of set theory to prove that the reals are uncountable, say). The model $M$ is countable externally, but inside this model there are uncountable objects, such as $\mathbb{R}^M$. So this is a set of real numbers, which in the real world we can see is countable, because it is a subset of the countable set $M$, but inside $M$ it is thought to be uncountable.

Meanwhile, it is perhaps important to mention that the non-absoluteness of countability is much worse than this. The method of forcing shows that for any model of set theory $M$ and any set $x\in M$, there is a larger model $N$, which can be constructed by the method of forcing, such that $x$ is countable in $N$. In slogan form, "any set can be made countable by forcing." The forcing notion is the partial order consisting of finite partial functions from $\omega$ to $x$, ordered by inclusion. A simple density argument shows that any generic filter for this partial order provides a function from $\omega$ onto $x$, thereby witnessing that $x$ has become countable in the forcing extension.

One of the particular steps in your argument where I would object is where you say "therefore, by the fact that $M$ is a transitive model of ZFC, $f\in M$". It simply does not follow from $M$ being transitive that it contains all such functions $f$. You seem to suggest that since $f$ is a subset of $S\times \omega$ that it should be in $M$, but transitivity means that $M$ contains all elements-of-elements, not necessarily all subsets of elements. In particular, the power set of $S\times\omega$ inside $M$ is much smaller than the power set of $S\times\omega$ in $V$. Indeed, the contradiction of your argument proves this, since $f$ itself is not necessarily in $M$. Thus, not only is countability not absolute, but also the power set operation is not absolute.

-
Well explained. Thank you for the information on forcing method. It does collapse any uncountable sets. The mistake you pointed out indeed is the main problem of my arguments, power set operation is not absolute. Thank you! –  Zhang Jing Jun 23 '12 at 16:39
To add to Joel's nice answer, a slightly different example, without forcing: Again, suppose $M$ is a transitive model of set theory. The class $L$ from the point of view of $M$ is really some $L_\alpha$. By Lowenheim-Skolem, we may as well assume that $\alpha$, and thus $L_\alpha$, is countable. Of course, being a model of set theory, it contains sets that it believes uncountable. However, by transitivity, each $x$ in $L_\alpha$ is countable (in $L$), so at some stage $\beta>\alpha$, in $L_\beta$ we see a surjection $f:\omega\to x$. –  Andres Caicedo Jun 23 '12 at 17:10
Thank you @Andres. You mentioned: given a model of set theory, it contains sets it believes uncountable. Therefore, we can conclude the general techniques to argue the existence of uncountable sets, such as Cantor's Diagonalization, are absolute? –  Zhang Jing Jun 24 '12 at 4:48