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 Andreas. You are right. Power set operation is not absolute. $P(x)^M=P(x) \cap M$. I missed that. – Jing Zhang Jun 23 '12 at 16:31
• Yes, I should have removed it when I added the forcing tag. – Joel David Hamkins Jun 7 at 15:43
• @JoelDavidHamkins Ah, sorry - it looks like I misread the edit history. The way it's displayed (on my end at least) it looked like you'd added the number-theory tag; I think what actually happened is that the system re-ordered the tags, so in the edit summary the number theory tag appeared green(?). – Noah Schweber Jun 7 at 17:25

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! – Jing Zhang 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$. – Andrés E. 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? – Jing Zhang Jun 24 '12 at 4:48
• "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$." Only for the c.t. models, right? – goblin Jun 11 '14 at 15:57
• I had meant that the model $N$ exists in a forcing extension of $V$. But if you don't want to force to add it, then mere countability of $M$ suffices (it needn't be transitive nor well-founded). Meanwhile, even for uncountable $M$, there will always be an elementary extension $M\prec \bar M$ such that $\bar M\subset N$ for some $N$ in which $x$ is countable. The model $\bar M$ is simply the Boolean ultrapower by the collapse forcing, and the model $\bar M$ and $N$ exist in $V$. – Joel David Hamkins Jun 11 '14 at 16:10