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.