# Uncountability (Math 3)

A set $$X$$ is uncountable if there is no bijection between $$X$$ and $$\mathbb{N}$$. Equivalently, there is no injection from $$X$$ to $$\mathbb{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^\mathbb N_M \in M$$ is countable when considered outside the model. Of course, it is a theorem that $$2^\mathbb N _M$$ is uncountable, but that is within the model. That is, there is a bijection $$f : \mathbb N \to 2^\mathbb N_M$$ 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.