# Is this a good way to explicate Skolem's Paradox?

Skolems Paradox shows an ostensible conflict between Cantor's Thoerem (CT) and the downward Löwenheim–Skolem Theorem (ST).

CT: for any set $A$, the powerset of $A$, $P(A)$, has a strictly greater cardinality than $A$. Cardinality is in terms of bijections: two sets have the same cardinality iff there exists a bijection between them. A set $A$ is countable iff there exists a objection between $A$ and the set of naturals $\omega$. Since (by CT) no function surjects $\omega$ onto its powerset, we learn that $P(\omega)$ is uncountable. Thus CT generally tells us some sets are uncountable.

ST: If a countable first-order theory has an infinite model, it has a countable model. The standard axiomatization of set theory, ZFC, is such a theory.

Assume ZFC has a model (which must be infinite).

By ST, ZFC has a countable model 𝔐.

By CT, we can deduce the existence of uncountable sets from ZFC.

Therefore, there must be some set A ∈ 𝔐 such that 𝔐 satisfies $A$ is uncountable. That is, there is no bijection $f \in$ 𝔐 between $A$ and $\omega$.

However, since 𝔐 has a countable domain, there are only countably many elements available to be members of A.

Thus A appears both countable and uncountable.

1. How did first-order logic come to be the dominant formal logic? (and comments)

-

Indeed $\mathfrak M$ sees only a small fraction of the universe, in particular he does not see the bijection between $\omega$ and itself, or between $\omega$ and some of the members of $\mathfrak M$.

However it is perfectly fine to have a model which is countable and has elements which are uncountable.

If you start by taking the real numbers and using it to generate a countable model, you will end up with a countable model of ZFC (of course it would not know of its own countability) in which there is a really uncountable set.

Now recall that $\mathfrak M\models A\text{ is countable}$ if and only if there is $f\in\mathfrak M$ which is a bijection between $A$ and $\omega$. If $\mathfrak M$ does not know about such $f$, $\mathfrak M\models A\text{ is uncountable}$. This is the heart of internal-external points of view.

If, on the other hand, we require $\mathfrak M$ to be transitive then every element of $\mathfrak M$ has to be countable as well (since it is a subset of $\mathfrak M$ by transitivity).

-
I changed the OP a bit, is it OK? I fear "That is, A in 𝔐 is (at most) countable" might be wrong UNLESS I stipulated that 𝔐 was transitive. –  pichael Jun 4 '12 at 18:45
@pichael: It is fine, however as long as you do not assume that $\frak M$ is transitive there is no guarantee that every element of $\frak M$ is countable. –  Asaf Karagila Jun 4 '12 at 18:50
So basically you have been saying that my explanation assumes that $M$ is transitive. What would I have to add/subtract from my explanation to include non-transitive models of ZFC? –  pichael Jun 4 '12 at 23:23
@pichael: If you look at the Skolem-Lowenheim theorem you will see that it does not only guarantee us a countable model, but also it allows us to point at a certain element and ensure that this element would be in the model. Now suppose we have a model in which there is a truly uncountable set $A$; we can consider the countable model in which $A$ is a member. Obviously this model cannot be transitive, as that would imply $A$ is also a subset of that model, which is a contradiction. So you have $A$ which both the universe and the countable model agree is uncountable... –  Asaf Karagila Jun 5 '12 at 4:46
No, the set $A$ is the same set. The cardinality of the set changes. It may be the case that the set has some specific role (being $\omega$, being $\omega_1$, being $\cal P(\omega)$, etc.) which may also change between models. However as sets these are the same, especially when you take submodels of "good" models (i.e. transitive and well-founded models, which may be very large and not just countable). –  Asaf Karagila Jun 5 '12 at 4:55

A set is countably infinite if it is in bijection to $\mathbb{N}$. If you have a countable model, a set can be uncountably from the "point of view" of the model simply because the model doesn't contain the bijection. So the model doesn't see the bijection, and a set is seen as uncountable.

-
Can I give a kind of example for your comment: Let M be a model that satisfies "A is countable." As you say, this just means there is a bijection in M consisting of N and A. Let's throw away all such bijections between A and N and call this new model M'. Thus M sees A as countable, M' sees A as uncountable. –  pichael May 25 '12 at 10:49
@pichael: Of course you have to be careful when you say such things. If $A$ is a set which is provably countable (for example, $\omega$ itself) then $M'$ would not be a model of ZFC. –  Asaf Karagila May 25 '12 at 10:50
@AsafKaragila: I must be missing something crucial here, as that is not immediately obvious to me. What is M' not satisfying? Pairing? –  pichael May 25 '12 at 10:59
@pichael: You will note that I refrain from using $\mathbb N$. This is because $\mathbb N$ is a mathematical idea which is interpreted often as a model of PA which in ZF is interpreted canonically as $\omega$ along with ordinal operations. The same goes for $\mathbb Z$ or $\mathbb Q$ and so on. All of these can be interpreted as any countably infinite set. $\omega$, on the other hand, is a very concrete set in ZFC - it is the collection of finite ordinals. And yes, everything definable from $\omega$ also has to stay if you want $M'$ to be a submodel. –  Asaf Karagila May 25 '12 at 11:08
@pichael: It means sets which can be defined from $\omega$. For example the set of finite non-zero ordinals; the ordinal $\omega+1$; the set of ordinals which are decomposable in multiplication; etc. –  Asaf Karagila May 25 '12 at 11:23