4
$\begingroup$

Skolem's Paradox tells us that countability in first-order logic is relative.

Relative to what?

Below is what I've gathered.

Countability it relative to:
1. what a model takes to be $\mathbb N$
2. what bijections between $\mathbb N$ and some set $A$ a model recognizes.

Two examples:

For (1): Let $$ be a model such that $A$ is uncountable in $$. We add a bijection between $A$ and $\mathbb N$ to $$ and call this new model $$. $A$ is countable in $$. As mentioned here.

For (2): The underlying set of a model $$ might be countable from the perspective of a larger model $$, and so $$ might "see" $\mathbb N$ differently than $$. I'm not sure if I've said this right, but here is a post on this.

1 Answers 1

5

I fear I may have confused you a bit, but this is a confusing topic after all, and it can take quite some time to wrap your head around it completely.

First let us establish the following fact. We live in a big big universe. This universe, for the sake of conversation is a model of ZFC. However this universe is not a set, and we do not know any sets outside our universe.

This universe judges with (extreme prejudice) what is truly countable and what is not, what is countable is what the universe know has a bijection with $\omega$ (which in our case is "the true $\omega$").

Suppose that there is a model of ZFC $\mathfrak M$ which is a set in our universe, it may be countable and it might not be. It might know the same true $\omega$, and it might think that some other set is $\omega^\mathfrak M$ (the set which $\mathfrak M$ thinks is $\omega$). It is important to know, $\omega^\mathfrak M$ may not even be countable! In such case $\mathfrak M$ may think that things are countable even if they are not, as it compares things to its own $\omega$ (which we know is uncountable).

Since $\mathfrak M$ is small, it may know some sets which are truly countable, but it may not know about the bijections these sets have with the true $\omega$, it may be the case that $\omega^\mathfrak M$ is itself uncountable (but $\mathfrak M$ is unaware to this fact, since it judges countability wrong) and then $\mathfrak M$ will get "most" things wrong about countability.

So we end up with the following situation:

  1. There is an absolute notion of countability. This is what the universe decides, or knows, is countable.
  2. Every model inside the universe has its own version of $\omega$ which may be the true $\omega$, may be a different countable set, and in the worst possible case may not even be a countable set! Inside such model, $\mathfrak M$, a set $A$ is countable if the model knows about a bijection between the "local" $\omega^\mathfrak M$ and $A$.
  3. We can then extend such $\mathfrak M$ to a slightly larger $\mathfrak N$ in which some set $A$ which in $\mathfrak M$ was not countable, $\mathfrak N$ thinks is countable (we added the needed bijection).

We separate the case of 1, where the countability is absolute (or "true") even if internally some model $\mathfrak M$ may not know that some set is countable, from the cases of 2 and 3 in which a certain model thinks of a set as countable, or uncountable, regardless of its true size.

  • 0
    Technically, we can't say that there is such a universe (or a model of ZFC) because we don't know that ZFC is consistent, right? But assuming it is, by Completeness (?) there is a model/universe. And assuming there is such a universe, there would be an absolute notion of countability.2012-05-29
  • 0
    Second, so there can be a "truly" uncountable set _A_ which our M takes to be countable?! But lets say that M is countable. Clearly, M doesn't then recognize the "true" _A_ as there are only countably many members in M available to be in _A_ (in M). (But then wouldn't A in M be a proper subset of the "true" A?)2012-05-29
  • 1
    @pichael: For the first comment, yes. We cannot know that ZFC is consistent, and we have to assume that and thus it has a model. For the second comment, $M$ can be a model generated in some way that ZFC is true in $M$ (i.e. $M$ is a model of ZFC) but the $\omega^M$ is uncountable. This means that things which $M$ think of as countable may be uncountable. Lastly, if $M$ is *not* transitive then its elements are not subsets of the model, that is we can have some $A\in M$ such that $A\nsubseteq M$. In particular we can have $M$ countable, $A\in M$ a truly uncountable set, thus $A\nsubseteq M$.2012-05-29
  • 0
    So, the only way some _A_ can serve as _w_ in **M** while _A_ is uncountable is that **M** is not transitive? But as we have talked about before (unless I misunderstood), **M** "sees" itself as a (proper?) class and thus doesn't recognize any sets outside **M**. So, to **M**, _A_ is countable (obviously bc _A_ is _w_ in **M**) even though _A_ is uncountable, right? What would happen if **M** was transitive? I've seen "transitive" come up in discussions of Skolem's Paradox, but I don't know about transitivity—e.g. [here](http://www.nd.edu/~tbays/papers/spmath.pdf). I'll do some research.2012-05-29
  • 1
    @pichael: Transitive models are "nice" because they are closed under $\in$, namely $m\in\mathfrak M$ and $x\in m$ then $x\in\mathfrak M$. I'm not sure to answer you whether or not transitive models must agree with the universe on $\omega$, though.2012-05-30
  • 1
    @Asaf: Suppose $\mathfrak M$ is transitive and doesn't agree with the universe about $\omega$, Then its $\omega$ would have to be larger than ours, because every element of our $\omega$ has a finite description in the formal language that proves it is in $\omega$. But since transitive models are well-founded, looking in _from the outside_ we can see that there must be a least one among the non-standard elements of $\omega^{\mathfrak M}$. Such an element cannot have a predecessor, not even _inside_ $\mathfrak M$. Therefore so it cannot be a member of $\omega^{\mathfrak M}$. Contradiction!2012-05-30
  • 1
    On the other hand, if our universe is ill-founded enough for the Mostowski collapse lemma to be true for arbitrary models, we can adjoin a non-archimedean natural to ZFC (with or without Reg) by the usual compactness construction, get a model from the completeness theorem, and then collapse that in order to get a transitive (yet non-well-founded) model that disagrees with the universe on $\omega$.2012-05-30
  • 0
    @Henning: That is great!2012-05-30
  • 0
    @Henning: To your first comment. I don't get why _w_ has to be larger than the universe's (I don't get the "because..." part.) I know "being well-founded" means there is a least element. Is a non-standard element, an element of _w_ in M that doesn't agree with the universe's _w_? Then I'm lost with the remaining inferences. Is there a "for dummies" version? :)2012-05-31
  • 0
    @Asaf: "First let us establish the following fact. We live in a big big universe. This universe, for the sake of conversation is a model of ZFC. However this universe is not a set, and we do not know any sets outside our universe." This is just _V_, right? And _V_ is a proper class? Proper classes can't be models, as models are sets. But we are just going to assume it is for the sake of understanding? OK.2012-05-31
  • 1
    @pichael: Classes *can* be models, these are called *class models*. We have to do set theory *inside* a universe of sets. Much like addition of integers lives "inside" $\mathbb Z$, despite the naive "all numbers are complex" being a larger universe - much like this is set theory. We take our sets from somewhere, and this somewhere is not a set for itself. We call this *meta-theory*, and it plays a role in mathematics (a role many people are oblivious to). My first sentence merely suggests that this meta-theory is ZFC, and therefore the universe is the inside of some model of ZFC.2012-05-31
  • 1
    One important caveat about class models, since they are "too big" to be sets they do not adhere to the completeness theorem's requirement. Namely, if ZFC has a class model it need not imply that it is consistent.2012-05-31
  • 1
    @pichael: You may also be interested in [this answer](http://math.stackexchange.com/questions/151389/standard-model-of-zfc-and-existence-of-model-of-zfc/151453#151453).2012-05-31
  • 1
    @pichael: _Under the assumption_ the the model's $\omega$ is different from ours, it has to be different by being _larger_, because each of _our_ natural numbers need to appear in the model's $\omega$ too. The "for-dummies" version is that if a model of ZFC is transitive, then its $\omega$ is identical to the $\omega$ in the outside universe.2012-05-31
  • 0
    @Asaf: So model theory can be done just when there is an established meta-theory. Our meta-theory is ZFC, while it could be others (such as Z, ZF, MK, KP,...?). "and therefore the universe is the inside of some model of ZFC." Could this be stronger? E.g. "Our meta-theory (ZFC) _determines_ what universe there is and thus what models are available to use."2012-05-31
  • 1
    @pichael: Mathematics is done when there is *some* meta-theory. Model theory, as it deals with sets usually requires us some well-defined notion of what is a set in the first place, so a very natural starting point is taking the meta-theory to be some sort of set theory.2012-05-31
  • 0
    @Asaf: does M think that its _w_ is _w_ ^V or just _w_? (Or does _w_ without V just make no sense?)2012-06-01
  • 1
    @pichael: Think of $\omega$ as a syntactical constant, the true $\omega$ is $\omega^V$, but $\mathfrak M$ does not know about that, it might know $\omega^V$ as its *own* $\omega$; and it might not know $\omega^V$ as such. There exists only one *true* [external] $\omega$, but every model has its own [internal] $\omega$ as well, some models may agree with the universe on what is $\omega$ and some models might disagree with the universe. That's all very confusing, and it takes quite some time to fully understand this.2012-06-01
  • 0
    @Asaf: Exactly what in the OP indicated that I was confused? I.e. exactly what needed correction? Thanks.2012-06-09
  • 0
    @pichael: Wow, my memory does not have this sort of caching to answer you without reading *everything*. If you pinpoint me to a certain comment and be more specific in your question, I might be able to restore the wanted data... :-)2012-06-09
  • 0
    @AsafKaragila: What?! All this time you had me believing you were omniscient... :P I was just referring to your _actual_ [answer](http://math.stackexchange.com/questions/151066/countability-in-first-order-logic-is-relative-to-what-exactly/151100#151100) (above), you wrote: "I fear I may have confused you a bit..." I was wondering what in my original [question](http://math.stackexchange.com/questions/151066/countability-in-first-order-logic-is-relative-to-what-exactly) tipped you off about my being confused/what needed correction.2012-06-09
  • 1
    @pichael: Oh, that. Well, the fact that different models have completely different $\omega$ and that $\mathbb N$ is not $\omega$. One can easily restrict themselves to standard, transitive models of ZFC which agree on the real $\omega$. After understanding the paradox in those terms one can slowly wade into the stranger realm of the non-standard. In particular my insistence on separating $\mathbb N$ and $\omega$ can be confusing, I suppose. So when you wrote this question I felt that I may have confused you in my past answers.2012-06-09
  • 0
    @Asaf: if $V$ is an absolute perspective, then why is countability relative? I realize this has to do with internal/external perspectives again. I guess I'm asking why truth (about some set) is relative to the _inner_ perspective as opposed to $V$'s _external_ perspective?2012-06-10
  • 1
    @pichael: Because we work inside the models of ZFC, not just in the universe. Inside the models we work as if we are unaware of the outside happening; however we - as omnipotent and omniscient beings of that model - are allowed to skip back and forth between the model and the true universe. From the inside it looks very large and from the outside it looks very small.2012-06-10
  • 0
    @Asaf: _How_ can models within $V$ have different versions of $\omega$? What's an example of how to models would come to differ on $\omega$?2012-06-10
  • 0
    @pichael: I was watching Blade Runner, but you started a new thread so I'll elaborate there.2012-06-10
  • 0
    @Asaf: Good movie. No worries, I thought it was a bigger topic than just for a comment anyway.2012-06-10