Cardinality of the continuum
Encyclopedia
In set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

, the cardinality of the continuum is the cardinality or “size” of the set of real numbers , sometimes called the continuum. It is an infinite cardinal number
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...

 and is denoted by or (a lowercase fraktur script c).

The real numbers are more numerous than the natural numbers . Moreover, has the same number of elements as the power set of . Symbolically, if the cardinality of is denoted as , the cardinality of the continuum is
This was proven by Georg Cantor
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...

 in his 1874 uncountability proof
Cantor's first uncountability proof
Georg Cantor's first uncountability proof demonstrates that the set of all real numbers is uncountable. This proof differs from the more familiar proof that uses his diagonal argument...

, part of his groundbreaking study of different infinities, and later more simply in his diagonal argument
Cantor's diagonal argument
Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural...

. 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 This is also true for several other infinite sets, such as any n-dimensional Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...

  (see Space filling curve). That is,


The smallest infinite cardinal number is (aleph-naught). The second smallest is (aleph-one). The continuum hypothesis
Continuum hypothesis
In mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1874, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's 23 problems presented in the year 1900...

, which asserts that there are no sets whose cardinality is strictly between and implies that .

Uncountability

Georg Cantor
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...

 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. is strictly greater than the cardinality of the natural numbers, :
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
Cantor's first uncountability proof
Georg Cantor's first uncountability proof demonstrates that the set of all real numbers is uncountable. This proof differs from the more familiar proof that uses his diagonal argument...

 and Cantor's diagonal argument
Cantor's diagonal argument
Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural...

.

Cardinal equalities

A variation on Cantor's diagonal argument can be used to prove Cantor's theorem
Cantor's theorem
In elementary set theory, Cantor's theorem states that, for any set A, the set of all subsets of A has a strictly greater cardinality than A itself...

 which states that the cardinality of any set is strictly less than that of its power set, i.e. |A| < 2|A|, and so the power set P(N) of the natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s N is uncountable. In fact, it can be shown that the cardinality of P(N) is equal to :
  1. Define a map f : RP(Q) from the reals to the power set of the rationals by sending each real number x to the set of all rationals less than or equal to x (with the reals viewed as Dedekind cut
    Dedekind cut
    In mathematics, a Dedekind cut, named after Richard Dedekind, is a partition of the rationals into two non-empty parts A and B, such that all elements of A are less than all elements of B, and A contains no greatest element....

    s, this is nothing other than the inclusion map
    Inclusion map
    In mathematics, if A is a subset of B, then the inclusion map is the function i that sends each element, x of A to x, treated as an element of B:i: A\rightarrow B, \qquad i=x....

     in the set of sets of rationals). This map is injective
    Injective function
    In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...

     since the rationals are dense
    Dense set
    In topology and related areas of mathematics, a subset A of a topological space X is called dense if any point x in X belongs to A or is a limit point of A...

     in R. Since the rationals are countable we have that .
  2. Let {0,2}N be the set of infinite sequence
    Sequence
    In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...

    s with values in set {0,2}. This set clearly has cardinality (the natural bijection
    Bijection
    A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...

     between the set of binary sequences and P(N) is given by the indicator function). Now associate to each such sequence (ai) the unique real number in the interval
    Unit interval
    In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1...

     [0,1] with the ternary
    Ternary numeral system
    Ternary is the base- numeral system. Analogous to a bit, a ternary digit is a trit . One trit contains \log_2 3 bits of information...

    -expansion given by the digits (ai), i.e. the i-th digit after the decimal point is ai. The image of this map is called the Cantor set
    Cantor set
    In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of remarkable and deep properties. It was discovered in 1875 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883....

    . 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 .

By the Cantor–Bernstein–Schroeder theorem
Cantor–Bernstein–Schroeder theorem
In set theory, the Cantor–Bernstein–Schroeder theorem, named after Georg Cantor, Felix Bernstein, and Ernst Schröder, states that, if there exist injective functions and between the sets A and B, then there exists a bijective function...

 we conclude that

(A different proof of is given in Cantor's diagonal argument. This proof constructs a bijection from {0,1}N to R.)

The cardinal equality can be demonstrated using cardinal arithmetic:
This argument is a condensed version of the notion of interleaving two binary sequences: let 0.a0a1a2... be the binary expansion of x and let 0.b0b1b2... be the binary expansion of y. Then z = 0.a0b0a1b1a2b2..., the interleaving of the binary expansions, is a well-defined function when x and y have unique binary expansions. Only countably many reals have non-unique binary expansions.

By using the rules of cardinal arithmetic one can also show that
where n is any finite cardinal ≥ 2, and
where is the cardinality of the power set of R, and .

Alternative explanation for

Every real number has an 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
Countable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...

 since they can be put into a one-to-one correspondence with the set of natural numbers . 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 each real number has digits in its expansion.

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

since

On the other hand, if we map to and consider that decimal fractions containing only 3 or 7 are only a part of the real numbers, then we get

and thus

Beth numbers

The sequence of beth numbers is defined by setting and . So is the second beth number, beth-one:
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
Real line
In mathematics, the real line, or real number line is the line whose points are the real numbers. That is, the real line is the set of all real numbers, viewed as a geometric space, namely the Euclidean space of dimension one...

):

The continuum hypothesis

The famous continuum hypothesis asserts that is also the second aleph number
Aleph number
In set theory, a discipline within mathematics, the aleph numbers are a sequence of numbers used to represent the cardinality of infinite sets. They are named after the symbol used to denote them, the Hebrew letter aleph...

  . In other words, the continuum hypothesis states that there is no set whose cardinality lies strictly between and
This statement is now known to be independent of the axioms of Zermelo–Fraenkel set theory
Zermelo–Fraenkel set theory
In mathematics, Zermelo–Fraenkel set theory with the axiom of choice, named after mathematicians Ernst Zermelo and Abraham Fraenkel and commonly abbreviated ZFC, is one of several axiomatic systems that were proposed in the early twentieth century to formulate a theory of sets without the paradoxes...

 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
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

 n, the equality = is independent of ZFC. (The case 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
König's theorem (set theory)
In set theory, König's theorem colloquially states that if the axiom of choice holds, I is a set, mi and ni are cardinal numbers for every i in I, and m_i In set theory, König's theorem In set theory, König's theorem (named after the Hungarian mathematician Gyula Kőnig, who published under the...

 on the grounds of cofinality
Cofinality
In mathematics, especially in order theory, the cofinality cf of a partially ordered set A is the least of the cardinalities of the cofinal subsets of A....

, e.g., In particular, could be either or , where is the first uncountable ordinal
First uncountable ordinal
In mathematics, the first uncountable ordinal, traditionally denoted by ω1 or sometimes by Ω, is the smallest ordinal number that, considered as a set, is uncountable. It is the supremum of all countable ordinals...

, so it could be either a successor cardinal
Successor cardinal
In the theory of cardinal numbers, we can define a successor operation similar to that in the ordinal numbers. This coincides with the ordinal successor operation for finite cardinals, but in the infinite case they diverge because every infinite ordinal and its successor have the same cardinality...

 or a limit cardinal
Limit cardinal
In mathematics, limit cardinals are certain cardinal numbers. A cardinal number λ is a weak limit cardinal if λ is neither a successor cardinal nor zero. This means that one cannot "reach" λ by repeated successor operations...

, and either a regular cardinal
Regular cardinal
In set theory, a regular cardinal is a cardinal number that is equal to its own cofinality. So, crudely speaking, a regular cardinal is one which cannot be broken into a smaller collection of smaller parts....

 or a singular cardinal.

Sets with cardinality of the continuum

A great many sets studied in mathematics have cardinality equal to . Some common examples are the following:
  • the real number
    Real number
    In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

    s
  • any (nondegenerate) closed or open interval
    Interval (mathematics)
    In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...

     in (such as the unit interval
    Unit interval
    In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1...

     [0,1])
  • the irrational number
    Irrational number
    In mathematics, an irrational number is any real number that cannot be expressed as a ratio a/b, where a and b are integers, with b non-zero, and is therefore not a rational number....

    s
  • the transcendental numbers
  • the Cantor set
    Cantor set
    In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of remarkable and deep properties. It was discovered in 1875 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883....

  • Euclidean space
    Euclidean space
    In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...

     
  • the complex number
    Complex number
    A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...

    s
  • the power set of the natural number
    Natural number
    In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

    s (the set of all subsets of the natural numbers)
  • the set of sequences
    Séquences
    Séquences is a French-language film magazine originally published in Montreal, Quebec by the Commission des ciné-clubs du Centre catholique du cinéma de Montréal, a Roman Catholic film society. Founded in 1955, the publication was edited for forty years by Léo Bonneville, a member of the Clerics...

     of integers (i.e. all functions , often denoted )
  • the set of sequences of real numbers,
  • the set of all continuous
    Continuous function
    In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...

     functions from to
  • the Euclidean topology
    Euclidean topology
    In mathematics, and especially general topology, the Euclidean topology is an example of a topology given to the set of real numbers, denoted by R...

     on (i.e. the set of all open set
    Open set
    The concept of an open set is fundamental to many areas of mathematics, especially point-set topology and metric topology. Intuitively speaking, a set U is open if any point x in U can be "moved" a small amount in any direction and still be in the set U...

    s in )
  • the Borel σ-algebra
    Borel algebra
    In mathematics, a Borel set is any set in a topological space that can be formed from open sets through the operations of countable union, countable intersection, and relative complement...

     on (i.e. the set of all Borel set
    Borel set
    In mathematics, a Borel set is any set in a topological space that can be formed from open sets through the operations of countable union, countable intersection, and relative complement...

    s in ).

Sets with greater cardinality

Sets with cardinality greater than include:
  • the set of all subsets of (i.e., power set )
  • the set 2R of indicator functions defined on subsets of the reals (the set is isomorphic to  – the indicator function chooses elements of each subset to include)
  • the set of all functions from to
  • the Lebesgue σ-algebra
    Lebesgue measure
    In measure theory, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of n-dimensional Euclidean space. For n = 1, 2, or 3, it coincides with the standard measure of length, area, or volume. In general, it is also called...

     of , i.e., the set of all Lebesgue measurable sets in .
  • the Stone–Čech compactification
    Stone–Cech compactification
    In the mathematical discipline of general topology, Stone–Čech compactification is a technique for constructing a universal map from a topological space X to a compact Hausdorff space βX...

    s of , and .


They all have cardinality (Beth two).
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK