# Why can't a model “say” of itself that it is countable?

Why can't a (standard?) model of ZFC "say of itself" that it is countable?

That is, why is there no bijection $f$ ∈ 𝔐 between 𝔐 and $\omega^𝔐$?

(I've read that it fails regularity, or even without regularity we get Cantor's paradox. But a direct answer to the question would be most helpful.)

Thanks.

-
If ZFC is inconsistent, one could prove that that there is such an $f$. Conversely, if one could prove there is such an $f$, then ZFC would be inconsistent. – André Nicolas Jun 8 '12 at 19:53

## 2 Answers

If $\frak M$ is a [standard] model of ZFC then we know several things:

1. $\frak M$ thinks that $\{x\mid x\notin x\}=\frak M$ is not a set.
2. If $f\in\frak M$ and $\frak M$ thinks that $f$ is a function, then the range of $f$ is a set in $\frak M$. (This is an instance of the axiom schema of replacement)
3. $\omega^\frak M$ is a set in $\frak M$.

These combined tell us that if $\frak M$ knew about a function from its own $\omega$ onto its entire universe it would violate the second thing in the list above, and will not be a model of ZFC.

In the case of a standard model, we can also have the contradiction from the fact that if such $f$ was in $\frak M$ then we would have $\frak M\in\frak M$ and that, as you said, would contradict the axiom of regularity (both in the universe and in $\frak M$) but this is in addition to the above argument.

-
@pichael: The axiom schema of replacement. If $f\in M$ we can write a formula (with parameters) which describes $f$ and satisfies the conditions of the replacement axiom schema, therefore the range of the function is a set, that is to say an element of $M$. However the range is exactly $M$ so we have $M\in M$. – Asaf Karagila Jun 11 '12 at 19:11
No, we can write a formula $\varphi(x,y,a)$ which says that $a$ is a function (a set of ordered pairs which has such and such properties) and that the pair $\langle x,y\rangle$ is in $a$. Now the replacement axiom for $\varphi$ tells us that if we fix parameters and we have a set on which the formula with the parameters define a function, then the range is also a function. Set the parameter to be $f$, and take the domain to be $\omega^M$. The axiom, therefore, tells us that the image of $\omega^M$ under the function $f$ is a set. (cont...) – Asaf Karagila Jun 11 '12 at 19:44
(...) But what is this image? It is $M$. What is a set, for $M$? An element of $M$. Therefore $M$ thinks that $M$ is in $M$. Now we can do all sort of crazy contradictions (Russell's paradox; external well-foundedness; internal well-foundedness; the incompleteness theorem; etc.) :-) – Asaf Karagila Jun 11 '12 at 19:47
@pichael: Suppose that $f\in M$ was a bijection between $\omega^M$ and $M$, then we could use this as the parameter in the $\varphi$ above; yes the range is also a set. For $M$ sets are its elements, it does not know any other set; You know that $\{x\mid x\notin^M x\}$ is not a set in $M$ (where $\in^M$ is the membership relation of $M$) but since $M$ is a model of ZFC the above class is $M$. However since $M\in M$ we have that $M$ is a set in $M$, which contradicts Russell's paradox. – Asaf Karagila Jun 11 '12 at 20:19
@pichael: It does not contradict the Russell's paradox. We derive contradiction using Russell's paradox. The reason that $A=\{x\mid x\notin^M x\}$ is not a set in $M$ is not difficult, suppose that it was. If $A\in^M A$ then by the definition of $A$ we have $A\notin^M A$; and if $A\notin^M A$ then by the definition of $A$ we also have $A\in^M A$. Either way a contradiction. So $A$ is not a set in $M$, that is to say that $A\notin M$ (where $\in,\notin$ without superscript denotes the true membership relation). Now recall that $M\models ZFC$ so $x\in M$ then $x\notin^M x$, thus $A=M$. – Asaf Karagila Jun 13 '12 at 6:31

If you can prove the existence of uncountable sets in ZFC, and if you can also prove a proposition saying the model is countable, then you have a contradiction in ZFC. With countable models of ZFC, the statement that a set is uncountable is true in the model if the set is not "internally" countable, i.e. no enumeration of the set is a member of the model.

-
Your argument is correct, but is written in a very vague way which makes it hard to understand what exactly you meant by this. It also makes it hard to make the distinction of what happens in non-standard models which may be countable and contain truly uncountable sets; or may be uncountable and think that some truly uncountable is countable. All these thing could happen with models of ZFC. However the correct argument is, indeed, that if there was a map onto the universe then the model would know that everything inside is countable; in contradiction to Cantor's theorem. – Asaf Karagila Jun 8 '12 at 21:43
When you say "could happen", do you really mean "do happen"? – Michael Hardy Jun 8 '12 at 22:24
"The model would know" seems rather vague too. Doesn't "the model would know" mean that the statement that the universe is countable is true in the model? I.e. there's a bijection between $\omega$ and the universe and that bijection is itself a member of the model? – Michael Hardy Jun 8 '12 at 22:25
No, since we cannot prove that ZFC has a model from ZFC, I am not saying that it happens. However if ZFC has a model then it has a countable model and then it has a model which is an ultrapower of this countable model, in this ultrapowers the set which is internally $\omega$ is externally uncountable. However in the original countable model it might just be the case that the set representing $\omega$ is countable. So it could happen (i.e. consistent with ...), while "do happen" seems to me synonymous to "provably happens". – Asaf Karagila Jun 8 '12 at 22:28
When I said "does happen", I meant there actually are models in which it happens. Is that what you meant? – Michael Hardy Jun 8 '12 at 22:30