Uncountability (Math 3)

A Set $X$ is uncountable if there is no bijection between $X$ and [45h $\mathbb{N}$]. Equivalently, there is no injection from $X$ to $\mathbb{N}$.

Foundational Considerations

In set theories without the axiom of choice, such as [ZF 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 [skolems_paradox 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 [absoluteness 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!