Cardinality of the continuum

In set theory, the cardinality of the continuum is the cardinality or "size" of the set of real numbers R{displaystyle mathbb {R} }, sometimes called the continuum. It is an infinite cardinal number and is denoted by |R|{displaystyle |mathbb {R} |} or c{displaystyle {mathfrak {c}}} (a lowercase fraktur script "c").

The real numbers R{displaystyle mathbb {R} } are more numerous than the natural numbers N{displaystyle mathbb {N} }. Moreover, R{displaystyle mathbb {R} } has the same number of elements as the power set of N{displaystyle mathbb {N} }. Symbolically, if the cardinality of N{displaystyle mathbb {N} } is denoted as ℵ0{displaystyle aleph _{0}}, the cardinality of the continuum is

c=2ℵ0>ℵ0.{displaystyle {mathfrak {c}}=2^{aleph _{0}}>aleph _{0},.}

This was proven by Georg Cantor in his 1874 uncountability proof, part of his groundbreaking study of different infinities; the inequality was later stated more simply in his diagonal argument. Cantor defined cardinality in terms of bijective functions: two sets have the same cardinality if and only if there exists a bijective function between them.

Between any two real numbers a < 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 R.{displaystyle mathbb {R} .} This is also true for several other infinite sets, such as any n-dimensional Euclidean space Rn{displaystyle mathbb {R} ^{n}} (see space filling curve). That is,

|(a,b)|=|R|=|Rn|.{displaystyle |(a,b)|=|mathbb {R} |=|mathbb {R} ^{n}|.}

The smallest infinite cardinal number is ℵ0{displaystyle aleph _{0}} (aleph-null). The second smallest is ℵ1{displaystyle aleph _{1}} (aleph-one). The continuum hypothesis, which asserts that there are no sets whose cardinality is strictly between ℵ0{displaystyle aleph _{0}} and c{displaystyle {mathfrak {c}}}, implies that c=ℵ1{displaystyle {mathfrak {c}}=aleph _{1}}.

Contents

• 
  1 Properties
  
  
  
  • 
    1.1 Uncountability
    
  
  
  • 
    1.2 Cardinal equalities
    
  
  
  • 
    1.3 Alternative explanation for c=2ℵ0{displaystyle {mathfrak {c}}=2^{aleph _{0}}}
    
  
  
  
  


• 
  2 Beth numbers
  


• 
  3 The continuum hypothesis
  


• 
  4 Sets with cardinality of the continuum
  


• 
  5 Sets with greater cardinality
  


• 
  6 References
  

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; i.e. c{displaystyle {mathfrak {c}}} is strictly greater than the cardinality of the natural numbers, ℵ0{displaystyle aleph _{0}}:

ℵ0<c.{displaystyle aleph _{0}<{mathfrak {c}}.}

In other words, there are strictly more real numbers than there are integers. Cantor proved this statement in several different ways. See Cantor's first uncountability proof and Cantor's diagonal argument.

Cardinal equalities

A variation on 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, i.e. |A|<2|A|{displaystyle |A|<2^{|A|}}, and so the power set ℘(N){displaystyle wp (mathbb {N} )} of the natural numbers N{displaystyle mathbb {N} } is uncountable. In fact, it can be shown^{[citation needed]} that the cardinality of ℘(N){displaystyle wp (mathbb {N} )} is equal to c{displaystyle {mathfrak {c}}}:

1. Define a map f:R→℘(Q){displaystyle f:mathbb {R} to wp (mathbb {Q} )} from the reals to the power set of the rationals, Q{displaystyle mathbb {Q} } by sending each real number x{displaystyle x} to the set {q∈Q:q≤x}{displaystyle {qin mathbb {Q} :qleq x}} of all rationals less than or equal to x{displaystyle x} (with the reals viewed as Dedekind cuts, this is nothing other than the inclusion map in the set of sets of rationals). This map is injective since the rationals are dense in R. Since the rationals are countable we have that c≤2ℵ0{displaystyle {mathfrak {c}}leq 2^{aleph _{0}}}.


2. Let {0,2}N{displaystyle {0,2}^{mathbb {N} }} be the set of infinite sequences with values in set {0,2}{displaystyle {0,2}}. This set has cardinality 2ℵ0{displaystyle 2^{aleph _{0}}} (the natural bijection between the set of binary sequences and ℘(N){displaystyle wp (mathbb {N} )} is given by the indicator function). Now associate to each such sequence (ai)i∈N{displaystyle (a_{i})_{iin mathbb {N} }} the unique real number in the interval [0,1]{displaystyle [0,1]} with the ternary-expansion given by the digits a1,a2,…{displaystyle a_{1},a_{2},dotsc }, i.e., ∑i=1∞ai3−i{displaystyle sum _{i=1}^{infty }a_{i}3^{-i}}, the i{displaystyle i}-th digit after the fractional point is ai{displaystyle a_{i}} with respect to base 3{displaystyle 3}. The image of this map is called the Cantor set. It is not hard to see that this map is injective, for by avoiding points with the digit 1 in their ternary expansion we avoid conflicts created by the fact that the ternary-expansion of a real number is not unique. We then have that 2ℵ0≤c{displaystyle 2^{aleph _{0}}leq {mathfrak {c}}}.

By the Cantor–Bernstein–Schroeder theorem we conclude that

c=|℘(N)|=2ℵ0.{displaystyle {mathfrak {c}}=|wp (mathbb {N} )|=2^{aleph _{0}}.}

The cardinal equality c2=c{displaystyle {mathfrak {c}}^{2}={mathfrak {c}}} can be demonstrated using cardinal arithmetic:

c2=(2ℵ0)2=22×ℵ0=2ℵ0=c.{displaystyle {mathfrak {c}}^{2}=(2^{aleph _{0}})^{2}=2^{2times {aleph _{0}}}=2^{aleph _{0}}={mathfrak {c}}.}

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

cℵ0=ℵ0ℵ0=nℵ0=cn=ℵ0c=nc=c,{displaystyle {mathfrak {c}}^{aleph _{0}}={aleph _{0}}^{aleph _{0}}=n^{aleph _{0}}={mathfrak {c}}^{n}=aleph _{0}{mathfrak {c}}=n{mathfrak {c}}={mathfrak {c}},}

where n is any finite cardinal ≥ 2, and

cc=(2ℵ0)c=2c×ℵ0=2c,{displaystyle {mathfrak {c}}^{mathfrak {c}}=(2^{aleph _{0}})^{mathfrak {c}}=2^{{mathfrak {c}}times aleph _{0}}=2^{mathfrak {c}},}

where 2c{displaystyle 2^{mathfrak {c}}} is the cardinality of the power set of R, and 2c>c{displaystyle 2^{mathfrak {c}}>{mathfrak {c}}}.

Alternative explanation for c=2ℵ0{displaystyle {mathfrak {c}}=2^{aleph _{0}}}

Every real number has at least one infinite decimal expansion. For example,

1/2 = 0.50000...

1/3 = 0.33333...

π = 3.14159....

(This is true even when the expansion repeats as in the first two examples.)
In any given case, the number of digits is countable since they can be put into a one-to-one correspondence with the set of natural numbers N{displaystyle mathbb {N} }. This fact makes it sensible to talk about (for example) the first, the one-hundredth, or the millionth digit of π. Since the natural numbers have cardinality ℵ0,{displaystyle aleph _{0},} each real number has ℵ0{displaystyle aleph _{0}} digits in its expansion.

Since each real number can be broken into an integer part and a decimal fraction, we get

c≤ℵ0⋅10ℵ0≤2ℵ0⋅(24)ℵ0=2ℵ0+4⋅ℵ0=2ℵ0{displaystyle {mathfrak {c}}leq aleph _{0}cdot 10^{aleph _{0}}leq 2^{aleph _{0}}cdot {(2^{4})}^{aleph _{0}}=2^{aleph _{0}+4cdot aleph _{0}}=2^{aleph _{0}}}

since

ℵ0+4⋅ℵ0=ℵ0.{displaystyle aleph _{0}+4cdot aleph _{0}=aleph _{0},.}

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

2ℵ0≤c.{displaystyle 2^{aleph _{0}}leq {mathfrak {c}},.}

and thus

c=2ℵ0.{displaystyle {mathfrak {c}}=2^{aleph _{0}},.}

Beth numbers

Main article: Beth number

The sequence of beth numbers is defined by setting ℶ0=ℵ0{displaystyle beth _{0}=aleph _{0}} and ℶk+1=2ℶk{displaystyle beth _{k+1}=2^{beth _{k}}}. So c{displaystyle {mathfrak {c}}} is the second beth number, beth-one:

c=ℶ1.{displaystyle {mathfrak {c}}=beth _{1}.}

The third beth number, beth-two, is the cardinality of the power set of R (i.e. the set of all subsets of the real line):

2c=ℶ2.{displaystyle 2^{mathfrak {c}}=beth _{2}.}

The continuum hypothesis

Main article: Continuum hypothesis

The famous continuum hypothesis asserts that c{displaystyle {mathfrak {c}}} is also the second aleph number ℵ1{displaystyle aleph _{1}}. In other words, the continuum hypothesis states that there is no set A{displaystyle A} whose cardinality lies strictly between ℵ0{displaystyle aleph _{0}} and c{displaystyle {mathfrak {c}}}

∄A:ℵ0<|A|<c.{displaystyle nexists Aquad :quad aleph _{0}<|A|<{mathfrak {c}}.}

This statement is now known to be independent of the axioms of Zermelo–Fraenkel set theory with the axiom of choice (ZFC). That is, both the hypothesis and its negation are consistent with these axioms. In fact, for every nonzero natural number n, the equality c{displaystyle {mathfrak {c}}} = ℵn{displaystyle aleph _{n}} is independent of ZFC (the case n=1{displaystyle n=1} is 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 on the grounds of cofinality, e.g., c≠ℵω.{displaystyle {mathfrak {c}}neq aleph _{omega }.} In particular, c{displaystyle {mathfrak {c}}} could be either ℵ1{displaystyle aleph _{1}} or ℵω1{displaystyle aleph _{omega _{1}}}, where ω1{displaystyle omega _{1}} 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 c{displaystyle {mathfrak {c}}}. Some common examples are the following:

• the real numbers R{displaystyle mathbb {R} }
  


• any (nondegenerate) closed or open interval in R{displaystyle mathbb {R} } (such as the unit interval [0,1]{displaystyle [0,1]})
  

  For instance, for all a,b∈R{displaystyle a,bin mathbb {R} } such that a<b{displaystyle a<b} we can define the bijection
  

  
  
  f:R→(a,b)x↦arctan⁡x+π2π⋅(b−a)+a{displaystyle {begin{aligned}fcolon mathbb {R} &to (a,b)\x&mapsto {frac {arctan x+{frac {pi }{2}}}{pi }}cdot (b-a)+aend{aligned}}}
  
  

  Now we show the cardinality of an infinite interval. For all a∈R{displaystyle ain mathbb {R} } we can define the bijection
  

  
  
  f:R→(a,∞)x↦{arctan⁡x+π2+aif x<0x+π2+aif x≥0{displaystyle {begin{aligned}fcolon mathbb {R} &to (a,infty )\x&mapsto {begin{cases}arctan x+{frac {pi }{2}}+a&{mbox{if }}x<0\x+{frac {pi }{2}}+a&{mbox{if }}xgeq 0end{cases}}end{aligned}}}
  
  

  and similarly for all b∈R{displaystyle bin mathbb {R} }
  

  
  
  f:R→(−∞,b)x↦{x−π2+bif x<0arctan⁡x−π2+bif x≥0{displaystyle {begin{aligned}fcolon mathbb {R} &to (-infty ,b)\x&mapsto {begin{cases}x-{frac {pi }{2}}+b&{mbox{if }}x<0\arctan x-{frac {pi }{2}}+b&{mbox{if }}xgeq 0end{cases}}end{aligned}}}
  
  


• the irrational numbers
  


• the transcendental numbers
  We note that the set of real algebraic numbers is countably infinite (assign to each formula its Gödel number.) So the cardinality of the real algebraic numbers is ℵ0{displaystyle aleph _{0}}. Furthermore, the real algebraic numbers and the real transcendental numbers are disjoint sets whose union is R{displaystyle mathbb {R} }. Thus, since the cardinality of R{displaystyle mathbb {R} } is c{displaystyle {mathfrak {c}}}, the cardinality of the real transcendental numbers is c−ℵ0=c{displaystyle {mathfrak {c}}-aleph _{0}={mathfrak {c}}}. A similar result follows for complex transcendental numbers, once we have proved that |C|=c{displaystyle leftvert mathbb {C} rightvert ={mathfrak {c}}}.


• the Cantor set
  


• 
  Euclidean space Rn{displaystyle mathbb {R} ^{n}}^[1]
  


• the complex numbers C{displaystyle mathbb {C} }
  
  We note that, per Cantor's proof of the cardinality of Euclidean space,^[1]|R2|=c{displaystyle leftvert mathbb {R} ^{2}rightvert ={mathfrak {c}}}. By definition, any c∈C{displaystyle cin mathbb {C} } can be uniquely expressed as a+bi{displaystyle a+bi} for some a,b∈R{displaystyle a,bin mathbb {R} }. We therefore define the bijection
  
  f:R2→C(a,b)↦a+bi{displaystyle {begin{aligned}fcolon mathbb {R} ^{2}&to mathbb {C} \(a,b)&mapsto a+biend{aligned}}}
  
  


• the power set of the natural numbers P(N){displaystyle {mathcal {P}}(mathbb {N} )} (the set of all subsets of the natural numbers)


• the set of sequences of integers (i.e. all functions N→Z{displaystyle mathbb {N} rightarrow mathbb {Z} }, often denoted ZN{displaystyle mathbb {Z} ^{mathbb {N} }})


• the set of sequences of real numbers, RN{displaystyle mathbb {R} ^{mathbb {N} }}
  


• the set of all continuous functions from R{displaystyle mathbb {R} } to R{displaystyle mathbb {R} }
  


• the Euclidean topology on Rn{displaystyle mathbb {R} ^{n}} (i.e. the set of all open sets in Rn{displaystyle mathbb {R} ^{n}})


• the Borel σ-algebra on R{displaystyle mathbb {R} } (i.e. the set of all Borel sets in R{displaystyle mathbb {R} }).

Sets with greater cardinality

Sets with cardinality greater than c{displaystyle {mathfrak {c}}} include:

• the set of all subsets of R{displaystyle mathbb {R} } (i.e., power set P(R){displaystyle {mathcal {P}}(mathbb {R} )})


• the set 2^R of indicator functions defined on subsets of the reals (the set 2R{displaystyle 2^{mathbb {R} }} is isomorphic to P(R){displaystyle {mathcal {P}}(mathbb {R} )} – the indicator function chooses elements of each subset to include)


• the set RR{displaystyle mathbb {R} ^{mathbb {R} }} of all functions from R{displaystyle mathbb {R} } to R{displaystyle mathbb {R} }
  


• the Lebesgue σ-algebra of R{displaystyle mathbb {R} }, i.e., the set of all Lebesgue measurable sets in R{displaystyle mathbb {R} }.


• the set of all Lebesgue-integrable functions from R{displaystyle mathbb {R} } to R{displaystyle mathbb {R} }
  


• the set of all Lebesgue-measurable functions from R{displaystyle mathbb {R} } to R{displaystyle mathbb {R} }
  


• the Stone–Čech compactifications of N{displaystyle mathbb {N} }, Q{displaystyle mathbb {Q} } and R{displaystyle mathbb {R} }
  


• the set of all automorphisms of the (discrete) field of complex numbers.

These all have cardinality 2c=ℶ2{displaystyle 2^{mathfrak {c}}=beth _{2}} (beth two).

References

1. 
   ^ ^ab Was Cantor Surprised?, Fernando Q. Gouvêa, American Mathematical Monthly, March 2011.
   

• 
  Paul Halmos, Naive set theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. .mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
  ISBN 0-387-90092-6 (Springer-Verlag edition).


• 
  Jech, Thomas, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer.
  ISBN 3-540-44085-2.


• 
  Kunen, Kenneth, 1980. Set Theory: An Introduction to Independence Proofs. Elsevier.
  ISBN 0-444-86839-9.

This article incorporates material from cardinality of the continuum on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

This page is only for reference, If you need detailed information, please check here