15
$\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$
5
  • 6
    $\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$
    – spaceisdarkgreen
    Commented Jun 17, 2017 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 ♦
    Commented Jun 17, 2017 at 22:34
  • 1
    $\begingroup$ @spaceisdarkgreen: So you are saying the result is not counterintuitive? Because that's all "paradox" means. $\endgroup$
    – celtschk
    Commented Jun 18, 2017 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$
    – spaceisdarkgreen
    Commented Jun 18, 2017 at 16:43
  • $\begingroup$ The $\in$ relation in $\mathcal{U}_0$ as a model of ZFC must be different from that in the original model $M$ that sees $\mathcal{U}_0$ as a countable set, otherwise the $\omega$ and its subsets are the same members in $M$ and $\mathcal{U}_0$, so we would have $2^\omega\subset\mathcal{U}_0$ in $M$, contradicting with that $\mathcal{U}_0$ is countable. Please correct me if I am wrong. $\endgroup$
    – Jianing Song
    Commented Sep 12, 2023 at 2:42

2 Answers 2

Reset to default
22
$\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$
9
  • $\begingroup$ You mean countably infinite $\endgroup$
    – user81883
    Commented Jun 17, 2017 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
    Commented Jun 17, 2017 at 22:05
  • 9
    $\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
    Commented Jun 17, 2017 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
    Commented Jun 17, 2017 at 22:25
  • $\begingroup$ @user81883 Thanks, corrected. $\endgroup$
    – Duncan Ramage
    Commented Jun 19, 2017 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
    Commented Jun 18, 2017 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$
    – Noah Schweber
    Commented Jun 18, 2017 at 4:29
  • $\begingroup$ @NoahSchweber: Thank you. $\endgroup$
    – user185596
    Commented Jun 18, 2017 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
    Commented Jul 8, 2018 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 ♦
    Commented Jul 8, 2018 at 16:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .