Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
add comment

2 Answers

up vote 9 down vote accepted

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

share|improve this answer
    
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
1  
@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
1  
@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
1  
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
show 8 more comments

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.

share|improve this answer
    
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
1  
@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
1  
@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
show 9 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.