4
$\begingroup$

In the ZFC set theory the "Axiom schema of specification" states that given an infinite set $z$, for any formula $\phi$ the subset $\{x\in z:\phi(x)\}$ always exists. Starting with a countable infinite set $z$ it is possible to construct only a countable infinite number of subsets this way, all of them being countable. My question is: How can we assure the existence of a set which is uncountable?

$\endgroup$
  • 1
    $\begingroup$ We should note that there are countable models of ZFC, and also pointwise definable models of ZFC (models in which every set can be definable without parameters). In such a model, there are no truly "uncountable" sets, but in that model, there are also no bijections from $\omega$ to $\mathcal{P}(\omega)$. $\endgroup$ – Athar Abdul-Quader Feb 10 '17 at 17:25
  • $\begingroup$ @Athar: This is interesting. What is your opinion about the Skolem's paradox which is somehow related? $\endgroup$ – Zoltán Csereháti Feb 10 '17 at 18:11
  • $\begingroup$ It's not much of a paradox, you just need to think about the distinction between "countable" and "countable according to M" where M is some particular model of set theory. $\endgroup$ – Athar Abdul-Quader Feb 10 '17 at 19:27
7
$\begingroup$

The power set axiom ensures that there is a set which cannot be put in bijection with a set of integers. Without the power set axiom it is consistent that every set is countable.

The thing to understand is that we can prove that there is a set which cannot be put into bijection with any subset of the natural numbers of that model. Even if we live in a model which is pointwise definable, in which every set can be defined (such model is countable, of course, but the model itself is "unaware of that").

This is Skolem's paradox in disguise, that first-order logic cannot properly handle the whole "infinite" thing. But it's not really a paradox, it's something we learn to live with and use to our advantage.

$\endgroup$
  • $\begingroup$ &Asaf:The Axiom of Power Set states that for any set z, there is a set y that contains every subset of z. But how to assure that there are really an uncountable number of such subsets? I understand your position, and clearly we want all the conceivable collections of the elements of z to be subsets. However the Axiom of Power Set works with existing sets as subsets. What makes a collection of elements to be a set, if it cannot be specified using any formula ϕ? (I don't know whether it is clear what my problem is.) $\endgroup$ – Zoltán Csereháti Feb 10 '17 at 15:12
  • 1
    $\begingroup$ This goes back to the fact that specification is allowed to use parameters, which I pointed out in comments on your previous question. $\endgroup$ – Asaf Karagila Feb 10 '17 at 15:46
  • 1
    $\begingroup$ I think that the only way you'll make peace with these issues is by actually studying logic and set theory for a while. Maybe a year or two. $\endgroup$ – Asaf Karagila Feb 10 '17 at 16:04
  • 1
    $\begingroup$ This is not the place to dispel your confusion. I don't know what you know or not know. How familiar you are with the distinction of theory and meta-theory; how well-versed you are with the subtle issues related to Goedel's theorems; how much you understand the "usual caveats" when it comes to models of ZF, and how much you even know about basic model theory which is relevant for understanding here. $\endgroup$ – Asaf Karagila Feb 10 '17 at 16:36
  • 1
    $\begingroup$ If you are well-versed in all these topics, I could probably write a quick explanation for you. But if you are versed in them, you should already know the answer yourself. I can only conclude from our interaction that there is a gap which I cannot, and will not, fill over this website. $\endgroup$ – Asaf Karagila Feb 10 '17 at 16:37
1
$\begingroup$

What this boils down to is Cantor's diagonalisation argument that shows that any infinite sequence $\langle A_n\colon n\in\mathbb{N}\rangle$ of subsets $A_n\subseteq \mathbb{N}$ must "miss" some subset $X$ of $\mathbb{N}$, namely the one specified by setting $X=\{x\in\mathbb{N} \colon\; x\not\in A_n\}$. The definition of $X$ implies that for each $n$, we have $n\in X\cup A_n$ but $n\not\in X\cup A_n$. In particular $X\not=A_n$ for each $n$.

To summarize, no infinite sequence indexed by $\mathbb{N}$ can list all of the members of the powerset of $\mathbb N$. This is what mathematicians mean when they say that the power set of $\mathbb{N}$ is uncountable. To formulate this one certainly needs to be able to talk about the powerset (otherwise there is nothing to be declared uncountable), so the powerset axiom is a good candidate for an answer to your question.

$\endgroup$
0
$\begingroup$

Hartogs' thereom asserts that for any set $X$ there is an ordinal number $\alpha$ such that there is no injective function $f\colon \alpha \to X$. For $X$ define $H(X)$ to be the smallest such ordinal.

Consequently, $H(\omega)$ exists - we call it $\omega_1$; this is the smallest uncountable ordinal number.

$\endgroup$

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.