Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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 2

up vote 5 down vote accepted

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.

share|improve this answer
1  
@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
1  
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
1  
(...) 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
1  
@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
1  
@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.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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