12
$\begingroup$

If we assume ZFC to be consistent we have, by the Löwenheim-Skolem theorem, the existence of a countable model $\mathcal{U}_0$ of ZFC.

In $\mathcal{U}_0$ there is a infinite ordinal, that is a non-empty limit ordinal. Call the smallest one $\omega$. We can also construct the cardinal $2^\omega := \mathrm{card}(\wp (\omega))$, since the existence of the power set is given by the axioms.

However, the latter is uncountable, but it is a subset of $\mathcal{U}_0$, which is countable; this seems to be a contradiction.

I suspect that this "contradiction" can be resolved by distinguishing between infinity between models of ZFC, but I don't know how to do that.

So my question is: How can I resolve this?

Thanks!

$\endgroup$
4
  • 5
    $\begingroup$ Nothing of substance to add to the answer below, but for reference your question is usually referred to as Skolem's Paradox (even though it's not a paradox) $\endgroup$ Jun 17 '17 at 22:08
  • $\begingroup$ Using compactness, one can show there would also be a model of ZFC, N, such that the collection of objects such that N think they are finite ordinals, is actually uncountable. (This is the "reverse Skolem paradox", as I like to call it.) $\endgroup$
    – Asaf Karagila
    Jun 17 '17 at 22:34
  • 1
    $\begingroup$ @spaceisdarkgreen: So you are saying the result is not counterintuitive? Because that's all "paradox" means. $\endgroup$
    – celtschk
    Jun 18 '17 at 10:28
  • 1
    $\begingroup$ @celtschk Just parroting a number of passages I've read where the author felt the need to emphasize that there's no real contradiction here. For instance in Cohen's discovery of forcing talk, he puts scare quotes around "paradox", so I guess I agree that's all ""paradox"" means, but it's one particular use case of "paradox". $\endgroup$ Jun 18 '17 at 16:43
18
$\begingroup$

The contradiction is inside the definition of "countable". A set is countable if there exists a surjection from $\mathbb{N}$ to our set. The function that would make our inside-the-model set countable doesn't exist inside of the model, so inside of the model, the set is uncountable.

$\endgroup$
5
  • $\begingroup$ You mean countably infinite $\endgroup$
    – user81883
    Jun 17 '17 at 22:05
  • $\begingroup$ So the set $2^\omega \subset \mathcal{U}_0$ would still be countable if we'd compare it outside the context of $\mathcal{U}_0$? $\endgroup$
    – Steven
    Jun 17 '17 at 22:05
  • 8
    $\begingroup$ @Steven Exactly. Countability isn't about the set in-and-of itself: ultimately, it boils down to "there exists a function." Changing where that function is allowed to exist can change whether a set "is" countable. Counterintuitive, but that's how it works. $\endgroup$
    – user231101
    Jun 17 '17 at 22:24
  • 3
    $\begingroup$ @Steven Also note that the "$2^\omega$" that lives in $\mathcal{V}_0$ is a different set than the "real-world" $2^\omega$: there are subsets of $\omega$ that aren't in $\mathcal{V}_0$. $\endgroup$
    – user231101
    Jun 17 '17 at 22:25
  • $\begingroup$ @user81883 Thanks, corrected. $\endgroup$ Jun 19 '17 at 17:36
7
$\begingroup$

The issue is not that $2^\omega$ is uncountable. It is that the set $\{A\mid\mathcal U_0\models A\subseteq\omega\}$ is countable. The fact that $\mathcal U_0$ is a model of $\sf ZFC$ means that in $\mathcal U_0$ there is a object which represents this set; but also that there is no bijection between the object $\mathcal U_0$ "thinks" is $\omega$, and the object representing the set above.

So $\mathcal U_0$ "thinks" there is no bijection between some object and $\omega$, which is exactly the definition for $\mathcal U_0$ "thinks" that some object is uncountable.


The reverse thing is also possible, if there is a model of $\sf ZFC$, then there is one $\mathcal U_1$ such that the set $\{A\mid\mathcal U_1\models A\text{ is a finite ordinal}\}$ is uncountable. So $\omega$, or the set that $\mathcal U_1$ "thinks" is $\omega$—the epitome of countability—is in fact uncountable!

$\endgroup$
5
  • $\begingroup$ Sort of related, wouldn't it be possible for the countable model $M$ to have an uncountable set (in $V$) as an element (clearly $M$ is not transitive)? I can't think of a simple argument to rule this out. $\endgroup$
    – user185596
    Jun 18 '17 at 1:12
  • 2
    $\begingroup$ @dav11 Yes, this will of course happen. For example, if $M\preccurlyeq V$ then e.g. $\omega_1\in M$, since $\omega_1$ is definable; now take a countable elementary substructure. Countable elementary (of course not transitive) substructures are incredibly important in set theory, and one particular context is in forcing - proper forcing is all about countable elementary submodels, and their combinatorics is essential. E.g. a basic useful property is, if $M\preccurlyeq V$ then $M\cap\omega_1\in \omega_1$, that is, the countable ordinals in $M$ are closed downwards. $\endgroup$ Jun 18 '17 at 4:29
  • $\begingroup$ @NoahSchweber: Thank you. $\endgroup$
    – user185596
    Jun 18 '17 at 17:04
  • $\begingroup$ When you say "this set" in the second line, are you referring to $2^{\omega}$. And similarly "the set above" in the fourth line. And (yet again) presumably alluding to it with "some object" in the second paragraph. Thanks, Asaf. With regards, $\endgroup$
    – user12802
    Jul 8 '18 at 15:49
  • $\begingroup$ @Andrew: Both refer to the set defined in the first line, which is $2^\omega$ from the point of view of the model. $\endgroup$
    – Asaf Karagila
    Jul 8 '18 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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