What assures in the ZFC set theory the existence of an uncountable set?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.