Countability: Difference between revisions
For definability in V this gives something like min{α | L_α prec_Δ_1 L}
RhubarbJayde (talk | contribs) No edit summary |
(For definability in V this gives something like min{α | L_α prec_Δ_1 L}) |
||
Line 3:
Georg Cantor, the founder of set theory, proved that the set of integers and the set of rational numbers are both countable, by constructing such maps. More famously, Cantor [[Cantor's diagonal argument|proved]] that the real numbers and that the powerset of the natural numbers are both uncountable, by assuming there was a map \( f \) and deriving a contradiction.
In terms of ordinals, it is clear that [[Omega|\( \omega \)]]<nowiki> is countable. You can also see that \( \omega + 1 \) is countable, by pairing \( \omega \) with zero and \( n \) with \( n + 1 \); that \( \omega 2 \) is countable, by pairing \( n \) with \( 2n \) and pairing \( \omega + n \) with \( 2n + 1 \), and so on. Larger countable ordinals such as \( \omega_1^{\mathrm{CK}} \) also are countable but, due to their size, such a map \( f \) is not \( \Delta_1 \)-definable in their rank of the constructible hierarchy. Furthermore, a gap ordinal may have a map to \( \mathbb{N} \) but this map can not be defined at all using first-order set theory. The least uncountable infinite ordinal is denoted \( \omega_1 \) or \( \Omega \), and it is larger than anything that can be reached from \( \omega \) using successors and countable unions. In particular, it is an </nowiki>[[Epsilon numbers|epsilon number]]<nowiki>, and much more. This is why it is useful as a "diagonalizer" in the construction of ordinal collapsing functions, although \( \omega_1^{\mathrm{CK}} \) is sometimes used instead.</nowiki>
Since \( \omega_1 \) and \( \mathbb{R} \) are both uncountable, it is natural to ask whether they have the same size. The affirmative of this question is known as the [[continuum hypothesis]]. Cantor failed to prove or disprove it, and Gödel and Cohen later proved that, if the \( \mathrm{ZFC} \) axioms are consistent, then the continuum hypothesis can neither be proven nor disproven.
| |||