Uncountability (Math 3)


by Patrick Stevens Jul 1 2016 updated Oct 26 2016

Formal definition of uncountability, and foundational considerations.

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!