# Countability in first-order logic is relative to what exactly?

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.

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.

• @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$. May 29, 2012 at 22:03
• @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. May 30, 2012 at 8:39
• @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! May 30, 2012 at 13:59
• 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$. May 30, 2012 at 14:03
• @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. May 31, 2012 at 5:33