Uncountability (Math 3)

A set $X$ is uncountable if there is no bijection between $X$ and $N$. Equivalently, there is no injection from $X$ to $N$.

Foundational Considerations

In set theories without the axiom of choice, such as Zermelo Frankel set theory without choice (ZF), it can be consistent that there is a cardinal_number $\kappa$ that is incomparable to ${\aleph }_0$. That is, there is no injection from $\kappa$ to ${\aleph }_0$ nor from ${\aleph }_0$ to $\kappa$. In this case, cardinality is not a total order, so it doesn't make sense to think of uncountability as "larger" than ${\aleph }_0$. In the presence of choice, cardinality is a total order, so an uncountable set can be thought of as "larger" than a countable set.

Countability in one model is not necessarily countability in another. By Skolem's Paradox, there is a model of set theory $M$ where its power set of the naturals, denoted $2_M^N\in M$ is countable when considered outside the model. Of course, it is a theorem that $2_M^N$ is uncountable, but that is within the model. That is, there is a bijection $f:N\to 2_M^N$ that is not inside the model $M$ (when $f$ is considered as a set, its graph), and there is no such bijection inside $M$. This means that (un)countability is not absolute.

See also

If you enjoyed this explanation, consider exploring some of Arbital's other featured content!

Arbital is made by people like you, if you think you can explain a mathematical concept then consider contributing to Arbital!