2
$\begingroup$

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).

$\endgroup$
5
  • $\begingroup$ In the definition of $S$, I think you mean to say "$D$ is dense in $P$", rather than dense in $M$. $\endgroup$ Jun 23, 2012 at 15:04
  • $\begingroup$ 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$. $\endgroup$ Jun 23, 2012 at 15:59
  • $\begingroup$ Thank you Andreas. You are right. Power set operation is not absolute. $P(x)^M=P(x) \cap M$. I missed that. $\endgroup$
    – Jing Zhang
    Jun 23, 2012 at 16:31
  • $\begingroup$ Yes, I should have removed it when I added the forcing tag. $\endgroup$ Jun 7, 2019 at 15:43
  • 1
    $\begingroup$ @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(?). $\endgroup$ Jun 7, 2019 at 17:25

1 Answer 1

11
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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! $\endgroup$
    – Jing Zhang
    Jun 23, 2012 at 16:39
  • $\begingroup$ 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$. $\endgroup$ Jun 23, 2012 at 17:10
  • $\begingroup$ 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? $\endgroup$
    – Jing Zhang
    Jun 24, 2012 at 4:48
  • $\begingroup$ "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? $\endgroup$ Jun 11, 2014 at 15:57
  • $\begingroup$ 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$. $\endgroup$ Jun 11, 2014 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.