Countability: Difference between revisions
Jump to navigation
Jump to search
Content added Content deleted
RhubarbJayde (talk | contribs) No edit summary |
RhubarbJayde (talk | contribs) No edit summary |
||
Line 1: | Line 1: | ||
Countability is a key notion in set theory and apeirology. A set is called countable if it has the same size as the set of the natural numbers. The way this is formally defined is that there is a map \( f: x \to \mathbb{N} \), where \( x \) is the set in question, so that different elements of \( x \) are sent to different natural numbers, and every natural number has some element of \( x \) sent to it. |
Countability is a key notion in set theory and apeirology. A set is called countable if it is possible to arrange its elements in a way so that they can be counted off one-by-one. In other words, it has the same [[Cardinal|size]] as the set of the natural numbers. The way this is formally defined is that there is a map \( f: x \to \mathbb{N} \), where \( x \) is the set in question, so that different elements of \( x \) are sent to different natural numbers, and every natural number has some element of \( x \) sent to it. In other words, there is a [[bijection]] from \( x \) to the natural numbers. However, this may not imply they have the same order-type, if the set is [[Well-ordered set|well-ordered]]. |
||
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. 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. |
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. |