Uncountability (Math 3)

A set \(X\) is un­countable if there is no bi­jec­tion be­tween \(X\) and \(\mathbb{N}\). Equiv­a­lently, there is no in­jec­tion from \(X\) to \(\mathbb{N}\).

Foun­da­tional Considerations

In set the­o­ries with­out the ax­iom of choice, such as Zer­melo Frankel set the­ory with­out choice (ZF), it can be con­sis­tent that there is a car­di­nal num­ber \(\kappa\) that is in­com­pa­rable to \(\aleph_0\). That is, there is no in­jec­tion from \(\kappa\) to \(\aleph_0\) nor from \(\aleph_0\) to \(\kappa\). In this case, car­di­nal­ity is not a to­tal or­der, so it doesn’t make sense to think of un­countabil­ity as “larger” than \(\aleph_0\). In the pres­ence of choice, car­di­nal­ity is a to­tal or­der, so an un­countable set can be thought of as “larger” than a countable set.

Countabil­ity in one model is not nec­es­sar­ily countabil­ity in an­other. By Skolem’s Para­dox, there is a model of set the­ory \(M\) where its power set of the nat­u­rals, de­noted \(2^\mathbb N_M \in M\) is countable when con­sid­ered out­side the model. Of course, it is a the­o­rem that \(2^\mathbb N _M\) is un­countable, but that is within the model. That is, there is a bi­jec­tion \(f : \mathbb N \to 2^\mathbb N_M\) that is not in­side the model \(M\) (when \(f\) is con­sid­ered as a set, its graph), and there is no such bi­jec­tion in­side \(M\). This means that (un)countabil­ity is not ab­solute.

See also

If you en­joyed this ex­pla­na­tion, con­sider ex­plor­ing some of Ar­bital’s other fea­tured con­tent!

Ar­bital is made by peo­ple like you, if you think you can ex­plain a math­e­mat­i­cal con­cept then con­sider con­tribut­ing to ar­bital!


  • Uncountability

    Some in­fini­ties are big­ger than oth­ers. Un­countable in­fini­ties are larger than countable in­fini­ties.