7
$\begingroup$

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.


Some good links I found:
1. How did first-order logic come to be the dominant formal logic? (and comments)

2 Answers 2

12

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).

  • 0
    @pichael: Yes, $M$ itself may be countable from the aspect of different models.2012-06-13
4

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.

  • 0
    Thanks, Michael2018-07-10