3
$\begingroup$

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.

  • 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.2012-06-08

2 Answers 2

6

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.

  • 0
    I intuitively see how we would have $M\in M$, but not formally or explicitly. So, how would we get that $M\in M$ if we supposed that a bijection $f\in M$ existed between the domain of $M$ and $\omega^M$?2012-06-11
  • 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$.2012-06-11
  • 0
    What would that formula be? "$f$ : $\omega^M$$M$ is bijective"?2012-06-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...)2012-06-11
  • 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.) :-)2012-06-11
  • 0
    1. "Set the parameter to be $f$" = let $f$ be a bijection between $\omega^M$ and $M$ (or really, the domain M of $M$), yes? 2. " then the range is also a function" do you mean "is also a _set_"? 3. how might we get russell's paradox? Sorry...I guess if math were a spelling bee I'd do terribly as I would need everything spelled out for me :-P2012-06-11
  • 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.2012-06-11
  • 0
    That's a little quick for my poor brain. Let me make sure I get things so far, here's my summary: if $M$ is a model of ZF, then no bijection $f\in M$ exists between $M$ and any $A\in M$. If there were such an $f\in M$, we could write a formula $\psi$ with $f$ as the parameter such that dom$f$ = $A$ and ran$f$ = $M$. By the replacement axiom for $\psi$, $M\in M$ immediately follows. This is problematic (for some reason). How's that summary?2012-06-13
  • 0
    @pichael: Yes. That is what I wrote.2012-06-13
  • 0
    Sweet. From your second to last comment: what does "above class" mean? Second, how does $M\in M$ contradict Russell's Paradox? (I presume it has to do with what you wrote: "You know that {x∣x∉Mx} is not a set in M." I'm just not seeing it.)2012-06-13
  • 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$.2012-06-13
  • 1
    @pichael: One of the axioms of ZFC tells us that $x\notin x$ (it tells us more than that, but here it's enough so far). So if $M$ is a model of ZFC we have that $x\in M$ then $x\notin^M x$, i.e. if $x$ is a set of $M$ then it is not an element of itself in the sense of $M$. Therefore we can prove that $A=\{x\in M\mid x\notin^M x\}$ is simply $M$, $A\subseteq M$ is obvious but from the above discussion we have that $M\subseteq A$. Therefore $M=A$ and so $A\notin M$ is the same as $M\notin M$. However the bijection showed us that $M\in M$... contradiction!2012-06-13
  • 0
    Again to summarize: if $M$ of ZFC could say of itself it is countable, then by replacement, we could get that $M\in M$. Then by regularity, we know that for every $A\in M$, $A$ is such that $A$$A$. Thus if $M\in M$ then $M$$M$ -- contradiction. Thus there is no bijection $f\in M$ between $M$ and $\omega^M\in M$.2012-06-13
  • 0
    @pichael: Correct.2012-06-13
  • 0
    Is this kosher: Let $M$ be a countable model of ZFC. Given the above discussion, there is no bijection $f$ between $M$ and $\omega^M\in M$. Let $N$ be $M$$f$. Thus $M$ is countable in $N$.2012-06-13
  • 1
    @pichael: Not at all. First note that $M\cup f$ is not even a model of ZFC. Second note is that suppose the universe $V$ is a model of ZFC+Con(ZFC)+$\lnot$Con(Con(ZFC)), i.e. ZFC holds, there is a set model of ZFC but no model of ZFC has an element which internally is a model of ZFC. In such case $M$ can be our countable model, but take any model $N$ such that $M\in N$, we have that $N$ does not know that $M$ itself is a model of ZFC to begin with. Furthermore if $M$ is in $N$ we can use forcing to ensure a bijection (like $f$) exists in a slightly later $N'$, but... (cliff hanger!)2012-06-13
  • 1
    (cont!) it may be the case that $N$ and $M$ disagree on what is $\omega$, so $N$ would think that $M$ is uncountable for one reason or another.2012-06-13
  • 0
    what do the $\langle$ $\rangle$ parenthesis mean?2012-06-13
  • 1
    @pichael: Usually an ordered pair, or a tuple.2012-06-13
  • 0
    You wrote: "we can write a formula φ(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 ⟨x,y⟩ is in a. Now the replacement axiom for φ 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 set." Is the axiom of specification in there at all? (EDIT: I just read specification follows from replacement in ZF but not in Z on Wiki).2012-06-13
  • 1
    @pichael: I think that subset schema is too weak to prove that kind of thing, but I'm not sure about that. Note that subset (specification) follows from replacement, and this implication is strict.2012-06-13
  • 0
    Hi yet again, Asaf. As you can probably tell by my multiplicity of upvotes that I'm trying to understand the various aspects of inside/outside countable/uncountable of Skolem's paradox. You have the patience of a saint (at least back in 2012 :) ). Maybe you could please direct me to an accessible source that demystifies what's going on in addition to the insights I've pieced together from stalking you. With regards,2018-07-08
  • 0
    @Andrew: I'm not quite sure how to help here. I think most set theorists just developed their intuion through use, rather than reading it somewhere. The key point is that you just need to grok the idea of what it means to prove something, and what it means from a semantic point of view. I'm afraid that I can't help much more than that.2018-07-08
2

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.

  • 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.2012-06-08
  • 0
    When you say "could happen", do you really mean "do happen"?2012-06-08
  • 0
    "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?2012-06-08
  • 0
    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".2012-06-08
  • 0
    When I said "does happen", I meant there actually are models in which it happens. Is that what you meant?2012-06-08
  • 0
    As for the second comment, "the model would know" is a very accurate statement when talking about models (especially in contexts of models of set theory). It means that the model knows about a certain set from which we can prove a certain proposition. Indeed to say that "the model would know" is to say that the assertion "the universe is countable" is true **internally** in that model.2012-06-08
  • 0
    Michael, I cannot promise that there are **any** models to begin with. If there are models then there are models in which it happens, yes.2012-06-08
  • 0
    "If there are models, then there are models in which it happens" is just what I meant by "does happen".2012-06-08
  • 0
    Well, then the answer is yes. However do not that "does happen" seem to imply some provability while this is somewhat about consistency, and **a lot** about internal-external cardinality of sets. You can read some more [here](http://math.stackexchange.com/a/91603/622).2012-06-08
  • 0
    I don't think it implies that in the context in which you wrote "could happen". Unless you mean it is provable that there are such models. The problem is that when you say "could happen", it makes it sound as if you're _uncertain_ whether there are such models, perhaps because you know it hasn't been proved. But apparently you're saying it _has_ been proved, at least if ZFC is consistent.2012-06-08
  • 0
    Yes, but it does not happen in *all* models. This is the same as asking whether or not a natural number has an even divisor. It *can* happen, and we can prove that if PA is consistent then it *does* happen. However it does not happen for *all* numbers. This disambiguity is fairly resolvable when talking about ZFC, but can cause problems when the topic is models of ZFC. Either way, since we both agreed on the mathematical content I see little point in pursuing a purely syntactical discussion on mathematical-English.2012-06-08
  • 0
    If you say "It could happen that a natural number has an even divisor", your statement is at best ambiguous: it could mean that you're not sure whether it happens. But if you say "Some natural numbers have an even divisor" then that's clear. Likewise if you say "A model of ZFC could be thus-and-so", it might mean that you're unsure whether some models of ZFC are thus-and-so. But if you say "Some models of ZFC are thus-and-so", then it's clear.2012-06-09
  • 0
    It could happen that the continuum is $\aleph_1$. I don't see how you can say that it "does happen" that the continuum is $\aleph_1$.2012-06-09
  • 0
    It _does happen_ that there are models of ZFC in which the continuum has cardinality $\aleph_1$. If you say only that it "could happen" that there are such models, that could mean you are uncertain whether there are. Again, the meaning of the phrase depends on the context.2012-06-09
  • 0
    Yes, I agree. It does happen that models in which CH holds. But you say that "It could happen that CH is true" and not "It does happen that CH is true". I honestly believe that we are waaaaaay over the point that we both fully understand what the other meant and now simply continue to comment out of some inertia. I'll stop now.2012-06-09