View source for Cardinality of the continuum

{{Short description|Cardinality of the set of real numbers}}
In [[set theory]], the '''cardinality of the continuum''' is the [[cardinality]] or "size" of the [[Set (mathematics)|set]] of [[real numbers]] <math>\mathbb R</math>, sometimes called the [[Continuum (set theory)|continuum]]. It is an [[Infinite set|infinite]] [[cardinal number]] and is denoted by <math>\bold\mathfrak c</math> (lowercase [[Fraktur]] "'''c'''") or <math>\bold|\bold\mathbb R\bold|.</math><ref>{{Cite web | title=Transfinite number {{!}} mathematics | url=https://www.britannica.com/science/transfinite-number|access-date=2020-08-12 | website=Encyclopedia Britannica | language=en}}</ref>

The real numbers <math>\mathbb R</math> are more numerous than the [[natural numbers]] <math>\mathbb N</math>. Moreover, <math>\mathbb R</math> has the same number of elements as the [[power set]] of <math>\mathbb N</math>. Symbolically, if the cardinality of <math>\mathbb N</math> is denoted as [[aleph number#Aleph-nought|<math>\aleph_0</math>]], the cardinality of the continuum is
{{block indent|<math>\mathfrak c = 2^{\aleph_0} > \aleph_0. </math>}}
This was proven by [[Georg Cantor]] in his [[Cantor's first uncountability proof|uncountability proof]] of 1874, part of his groundbreaking study of different infinities. The inequality was later stated more simply in his [[Cantor's diagonal argument|diagonal argument]] in 1891. Cantor defined cardinality in terms of [[bijective function]]s: two sets have the same cardinality if, and only if, there exists a bijective function between them.

Between any two real numbers ''a''&nbsp;<&nbsp;''b'', no matter how close they are to each other, there are always infinitely many other real numbers, and Cantor showed that they are as many as those contained in the whole set of real numbers. In other words, the [[open interval]] (''a'',''b'') is [[equinumerous]] with <math>\mathbb R</math>, as well as with several other infinite sets, such as any ''n''-dimensional [[Euclidean space]] <math>\mathbb R^n</math> (see [[space filling curve]]). That is,
{{block indent|<math>|(a,b)| = |\mathbb R| = |\mathbb R^n|.</math>}}

The smallest infinite cardinal number is <math>\aleph_0</math> ([[aleph number#Aleph-nought|aleph-null]]). The second smallest is <math>\aleph_1</math> ([[aleph number#Aleph-one|aleph-one]]). The [[continuum hypothesis]], which asserts that there are no sets whose cardinality is strictly between <math>\aleph_0</math> and {{nowrap|<math>\mathfrak c</math>}}, means that <math>\mathfrak c = \aleph_1</math>.<ref name=":0">{{Cite web| last=Weisstein| first=Eric W.| title=Continuum| url=https://mathworld.wolfram.com/Continuum.html | access-date=2020-08-12 | website=mathworld.wolfram.com | language=en}}</ref> The truth or falsity of this hypothesis is undecidable and [[Continuum hypothesis#Independence from ZFC|cannot be proven]] within the widely used [[Zermelo–Fraenkel set theory]] with axiom of choice (ZFC).

==Properties==

===Uncountability===
[[Georg Cantor]] introduced the concept of [[cardinality]] to compare the sizes of infinite sets. He famously showed that the set of real numbers is [[uncountably infinite]]. That is, <math>{\mathfrak c}</math> is strictly greater than the cardinality of the [[natural numbers]], <math>\aleph_0</math>:
{{block indent|<math>\aleph_0 < \mathfrak c.</math>}}
In practice, this means that there are strictly more real numbers than there are integers. Cantor proved this statement in several different ways. For more information on this topic, see [[Cantor's first uncountability proof]] and [[Cantor's diagonal argument]].

===Cardinal equalities===
A variation of Cantor's diagonal argument can be used to prove [[Cantor's theorem]], which states that the cardinality of any set is strictly less than that of its [[power set]]. That is, <math>|A| < 2^{|A|}</math> (and so that the power set <math>\wp(\mathbb N)</math> of the [[natural number]]s <math>\mathbb N</math> is uncountable).<ref>{{SpringerEOM|title=Cantor theorem|oldid=51494|mode=cs1}}</ref> In fact, the cardinality of <math>\wp(\mathbb N)</math>, by definition <math>2^{\aleph_0}</math>, is equal to <math>{\mathfrak c}</math>. This can be shown by providing one-to-one mappings in both directions between subsets of a countably infinite set and real numbers, and applying the [[Cantor–Bernstein–Schroeder theorem]] according to which two sets with one-to-one mappings in both directions have the same cardinality.<ref name=stillwell>{{cite journal
 | last = Stillwell | first = John
 | doi = 10.1080/00029890.2002.11919865
 | issue = 3
 | journal = American Mathematical Monthly
 | jstor = 2695360
 | mr = 1903582
 | pages = 286–297
 | title = The continuum problem
 | volume = 109
 | year = 2002}}</ref><ref name=johnson>{{cite book
 | last = Johnson | first = D. L.
 | department = Elements of Logic via Numbers and Sets
 | doi = 10.1007/978-1-4471-0603-6_6
 | isbn = 9781447106036
 | series = Springer Undergraduate Mathematics Series
 | pages = 113–130
 | publisher = Springer London
 | title = Chapter 6: Cardinal numbers
 | chapter = Cardinal Numbers
 | year = 1998}}</ref> In one direction, reals can be equated with [[Dedekind cut]]s, sets of rational numbers,<ref name=stillwell/> or with their [[binary expansion]]s.<ref name=johnson/> In the other direction, the binary expansions of numbers in the half-open interval <math>[0,1)</math>, viewed as sets of positions where the expansion is one, almost give a one-to-one mapping from subsets of a countable set (the set of positions in the expansions) to real numbers, but it fails to be one-to-one for numbers with terminating binary expansions, which can also be represented by a non-terminating expansion that ends in a repeating sequence of 1s. This can be made into a one-to-one mapping by that adds one to the non-terminating repeating-1 expansions, mapping them into <math>[1,2)</math>.<ref name=johnson/> Thus, we conclude that<ref name=stillwell/><ref name=johnson/>
{{block indent|<math>\mathfrak c = |\wp(\mathbb{N})| = 2^{\aleph_0}.</math>}}

The cardinal equality <math>\mathfrak{c}^2 = \mathfrak{c}</math> can be demonstrated using [[cardinal arithmetic]]:
{{block indent|<math>\mathfrak{c}^2 = (2^{\aleph_0})^2 = 2^{2\times{\aleph_0}} = 2^{\aleph_0} = \mathfrak{c}.</math>}}

By using the rules of cardinal arithmetic, one can also show that

{{block indent|<math>\mathfrak c^{\aleph_0} = {\aleph_0}^{\aleph_0} = n^{\aleph_0} = \mathfrak c^n = \aleph_0 \mathfrak c = n \mathfrak c = \mathfrak c</math>}}

where ''n'' is any finite cardinal ≥ 2 and

{{block indent|<math> \mathfrak c ^{\mathfrak c}  =  (2^{\aleph_0})^{\mathfrak c}  = 2^{\mathfrak c\times\aleph_0} = 2^{\mathfrak c}</math>}}

where <math>2 ^{\mathfrak c}</math> is the cardinality of the power set of '''R''', and <math>2 ^{\mathfrak c} > \mathfrak c </math>.

===Alternative explanation for {{not a typo|&cfr; {{=}} 2<sup>א<sub>&lrm;0</sub></sup>}}===
Every real number has at least one infinite [[decimal expansion]]. For example,
{{block indent|1=1/2 = 0.50000...}}
{{block indent|1=1/3 = 0.33333...}}
{{block indent|1=π = 3.14159....}}
(This is true even in the case the expansion repeats, as in the first two examples.)

In any given case, the number of decimal places is [[countable set|countable]] since they can be put into a [[one-to-one correspondence]] with the set of natural numbers <math>\mathbb{N}</math>. This makes it sensible to talk about, say, the first, the one-hundredth, or the millionth decimal place of π. Since the natural numbers have cardinality <math>\aleph_0,</math> each real number has <math>\aleph_0</math> digits in its expansion.

Since each real number can be broken into an integer part and a decimal fraction, we get:
{{block indent|<math>{\mathfrak c} \leq \aleph_0 \cdot 10^{\aleph_0} \leq 2^{\aleph_0} \cdot {(2^4)}^{\aleph_0} = 2^{\aleph_0 + 4 \cdot \aleph_0} = 2^{\aleph_0} </math>}}

where we used the fact that

{{block indent|<math>\aleph_0 + 4 \cdot \aleph_0 = \aleph_0 \,</math>}}

On the other hand, if we map <math>2 = \{0, 1\}</math> to <math>\{3, 7\}</math> and consider that decimal fractions containing only 3 or 7 are only a part of the real numbers, then we get

{{block indent|<math>2^{\aleph_0} \leq {\mathfrak c} \,</math>}}

and thus
{{block indent|<math>{\mathfrak c} = 2^{\aleph_0} \,.</math>}}

==Beth numbers==
{{main|Beth number}}
The sequence of beth numbers is defined by setting <math>\beth_0 = \aleph_0</math> and <math>\beth_{k+1} = 2^{\beth_k}</math>. So <math>{\mathfrak c}</math> is the second beth number, '''beth-one''':
{{block indent|<math>\mathfrak c = \beth_1.</math>}}
The third beth number, '''beth-two''', is the cardinality of the power set of <math>\mathbb{R}</math> (i.e. the set of all subsets of the [[real line]]):
{{block indent|<math>2^\mathfrak c = \beth_2.</math>}}

==The continuum hypothesis==
{{main|Continuum hypothesis}}

The continuum hypothesis asserts that <math>{\mathfrak c}</math> is also the second [[aleph number]], <math>\aleph_1</math>.<ref name=":0" /> In other words, the continuum hypothesis states that there is no set <math>A</math> whose cardinality lies strictly between <math>\aleph_0</math> and <math>{\mathfrak c}</math>
{{block indent|<math>\nexists A \quad:\quad \aleph_0 < |A| < \mathfrak c.</math>}}
This statement is now known to be independent of the axioms of [[Zermelo–Fraenkel set theory]] with the axiom of choice (ZFC), as shown by [[Kurt Gödel]] and [[Paul Cohen]].<ref>{{Cite book |last=Gödel |first=Kurt |date=1940-12-31 |title=Consistency of the Continuum Hypothesis. (AM-3) |url=http://dx.doi.org/10.1515/9781400881635 |doi=10.1515/9781400881635|isbn=9781400881635 }}</ref><ref>{{Cite journal |last=Cohen |first=Paul J. |title=The Independence of the Continuum Hypothesis |date=December 1963 |journal=Proceedings of the National Academy of Sciences |volume=50 |issue=6 |pages=1143–1148 |doi=10.1073/pnas.50.6.1143 |pmid=16578557 |pmc=221287 |bibcode=1963PNAS...50.1143C |issn=0027-8424|doi-access=free }}</ref><ref>{{Cite journal |last=Cohen |first=Paul J. |title=The Independence of the Continuum Hypothesis, Ii |date=January 1964 |journal=Proceedings of the National Academy of Sciences |volume=51 |issue=1 |pages=105–110 |doi=10.1073/pnas.51.1.105 |pmid=16591132 |pmc=300611 |bibcode=1964PNAS...51..105C |issn=0027-8424|doi-access=free }}</ref> That is, both the hypothesis and its negation are consistent with these axioms. In fact, for every nonzero [[natural number]] ''n'', the equality <math>{\mathfrak c}</math> = <math>\aleph_n</math> is independent of ZFC (case <math>n=1</math> being the continuum hypothesis). The same is true for most other alephs, although in some cases, equality can be ruled out by [[König's theorem (set theory)|König's theorem]] on the grounds of [[cofinality]] (e.g. <math>\mathfrak{c}\neq\aleph_\omega</math>). In particular, <math>\mathfrak{c}</math> could be either <math>\aleph_1</math> or <math>\aleph_{\omega_1}</math>, where <math>\omega_1</math> is the [[first uncountable ordinal]], so it could be either a [[successor cardinal]] or a [[limit cardinal]], and either a [[regular cardinal]] or a [[singular cardinal]].

==Sets with cardinality of the continuum==

A great many sets studied in mathematics have cardinality equal to <math>{\mathfrak c}</math>. Some common examples are the following:

{{unordered list
|the [[real number]]s <math>\mathbb{R}</math>
|any ([[Degeneracy (mathematics)|nondegenerate]]) closed or open [[Interval (mathematics)|interval]] in <math>\mathbb{R}</math> (such as the [[unit interval]] {{nowrap|<math>[0,1]</math>)}}
|the [[irrational number]]s
|the [[transcendental numbers]]
{{pb}}
The set of real [[algebraic number]]s is countably infinite (assign to each formula its [[Gödel numbering|Gödel number]].) So the cardinality of the real algebraic numbers is {{nowrap|<math>\aleph_0</math>.}} Furthermore, the real algebraic numbers and the real transcendental numbers are disjoint sets whose union is {{nowrap|<math>\mathbb R</math>.}} Thus, since the cardinality of <math>\mathbb R</math> is {{nowrap|<math>\mathfrak c</math>,}} the cardinality of the real transcendental numbers is {{nowrap|<math>\mathfrak c - \aleph_0 = \mathfrak c</math>.}} A similar result follows for complex transcendental numbers, once we have proved that {{nowrap|<math>\left\vert \mathbb{C} \right\vert = \mathfrak c</math>.}}
|the [[Cantor set]]
|[[Euclidean space]] <math>\mathbb{R}^n</math><ref name=Gouvea>[http://www.maa.org/sites/default/files/pdf/pubs/AMM-March11_Cantor.pdf Was Cantor Surprised?], [[Fernando Q. Gouvêa]], ''[[American Mathematical Monthly]]'', March 2011.</ref>
|the [[complex number]]s <math>\mathbb{C}</math>
{{pb}}
Per Cantor's proof of the cardinality of Euclidean space,<ref name=Gouvea /> {{nowrap|<math>\left\vert \mathbb{R}^2 \right\vert = \mathfrak c</math>.}} By definition, any <math>c\in \mathbb{C}</math> can be uniquely expressed as <math>a + bi</math> for some {{nowrap|<math>a,b \in \mathbb{R}</math>.}} We therefore define the bijection
{{block indent|<math>\begin{align}
 f\colon \mathbb{R}^2 &\to \mathbb{C}\\
 (a,b) &\mapsto a+bi
\end{align}</math>}}
|the [[power set]] of the [[natural number]]s <math>\mathcal{P}(\mathbb{N})</math> (the set of all subsets of the natural numbers)
|the set of [[sequences]] of integers (i.e. all functions {{nowrap|<math>\mathbb{N} \rightarrow \mathbb{Z}</math>,}} often denoted {{nowrap|<math>\mathbb{Z}^\mathbb{N}</math>)}}
|the set of sequences of real numbers, {{nowrap|<math>\mathbb{R}^\mathbb{N}</math>}}
|the set of all [[continuous function|continuous]] functions from <math>\mathbb{R}</math> to <math>\mathbb{R}</math>
|the [[Euclidean topology]] on <math>\mathbb{R}^n</math> (i.e. the set of all [[open set]]s in {{nowrap|<math>\mathbb{R}^n</math>)}}
|the [[Borel algebra|Borel σ-algebra]] on <math>\mathbb{R}</math> (i.e. the set of all [[Borel set]]s in {{nowrap|<math>\mathbb{R}</math>).}}
}}

==Sets with greater cardinality==

Sets with cardinality greater than <math>{\mathfrak c}</math> include:

*the set of all subsets of <math>\mathbb{R}</math> (i.e., power set <math>\mathcal{P}(\mathbb{R})</math>)
*the set [[Power set#Representing subsets as functions|2<sup>'''R'''</sup>]] of [[indicator function]]s defined on subsets of the reals (the set <math>2^{\mathbb{R}}</math> is [[isomorphic]] to <math>\mathcal{P}(\mathbb{R})</math>&nbsp;– the indicator function chooses elements of each subset to include)
*the set <math>\mathbb{R}^\mathbb{R}</math> of all functions from <math>\mathbb{R}</math> to <math>\mathbb{R}</math>
*the [[Lebesgue measure|Lebesgue σ-algebra]] of <math>\mathbb{R}</math>, i.e., the set of all [[Lebesgue measurable]] sets in <math>\mathbb{R}</math>.
*the set of all [[Lebesgue integration|Lebesgue-integrable]] functions from <math>\mathbb{R}</math> to <math>\mathbb{R}</math>
*the set of all [[Measurable function|Lebesgue-measurable]] functions from <math>\mathbb{R}</math> to <math>\mathbb{R}</math>
*the [[Stone–Čech compactification]]s of <math>\mathbb{N}</math>, <math>\mathbb{Q}</math>, and <math>\mathbb{R}</math>
*the set of all automorphisms of the (discrete) field of complex numbers.

These all have cardinality <math>2^\mathfrak c = \beth_2</math> ([[Beth number#Beth two|beth two]])

== See also ==

* [[Cardinal characteristic of the continuum]]

==References==
<references/>

== Bibliography ==
*[[Paul Halmos]], ''Naive set theory''. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. {{ISBN|0-387-90092-6}} (Springer-Verlag edition).
*[[Thomas Jech|Jech, Thomas]], 2003. ''Set Theory: The Third Millennium Edition, Revised and Expanded''. Springer. {{ISBN|3-540-44085-2}}.
*[[Kenneth Kunen|Kunen, Kenneth]], 1980. ''[[Set Theory: An Introduction to Independence Proofs]]''. Elsevier. {{ISBN|0-444-86839-9}}.

{{PlanetMath attribution|urlname=CardinalityOfTheContinuum|title=cardinality of the continuum}}

[[Category:Cardinal numbers]]
[[Category:Set theory]]
[[Category:Infinity]]