Cardinality of the continuum

Last updated

In set theory, 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 and is denoted by (lowercase Fraktur "c") or [1]

Contents

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 in his uncountability proof of 1874, part of his groundbreaking study of different infinities. The inequality was later stated more simply in his diagonal argument in 1891. 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 , as well as with several other infinite sets, such as any n-dimensional Euclidean space (see space filling curve). That is,

The smallest infinite cardinal number is (aleph-null). The second smallest is (aleph-one). The continuum hypothesis, which asserts that there are no sets whose cardinality is strictly between and , means that . [2] The truth or falsity of this hypothesis is undecidable and 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, is strictly greater than the cardinality of the natural numbers, :

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, (and so that the power set of the natural numbers is uncountable). [3] In fact, the cardinality of , by definition , is equal to . 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. [4] [5] In one direction, reals can be equated with Dedekind cuts, sets of rational numbers, [4] or with their binary expansions. [5] In the other direction, the binary expansions of numbers in the half-open interval , 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 . [5] Thus, we conclude that [4] [5]

The cardinal equality can be demonstrated using cardinal arithmetic:

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 𝔠 = 2א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 in the case the expansion repeats, as in the first two examples.)

In any given case, the number of decimal places is countable since they can be put into a one-to-one correspondence with the set of natural numbers . 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 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:

where we used the fact that

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 (i.e. the set of all subsets of the real line):

The continuum hypothesis

The continuum hypothesis asserts that is also the second aleph number, . [2] 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 with the axiom of choice (ZFC), as shown by Kurt Gödel and Paul Cohen. [6] [7] [8] That is, both the hypothesis and its negation are consistent with these axioms. In fact, for every nonzero natural number n, the equality = is independent of ZFC (case 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 on the grounds of cofinality (e.g. ). In particular, could be either or , where 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 . Some common examples are the following:

Sets with greater cardinality

Sets with cardinality greater than include:

These all have cardinality (beth two)

See also

Related Research Articles

In mathematics, specifically set theory, the continuum hypothesis is a hypothesis about the possible sizes of infinite sets. It states:

"There is no set whose cardinality is strictly between that of the integers and the real numbers."

In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is countable if there exists an injective function from it into the natural numbers; this means that each element in the set may be associated to a unique natural number, or that the elements of the set can be counted one at a time, although the counting may never finish due to an infinite number of elements.

<span class="mw-page-title-main">Cardinal number</span> Size of a possibly infinite set

In mathematics, a cardinal number, or cardinal for short, is what is commonly called the number of elements of a set. In the case of a finite set, its cardinal number, or cardinality is therefore a natural number. For dealing with the case of infinite sets, the infinite cardinal numbers have been introduced, which are often denoted with the Hebrew letter (aleph) marked with subscript indicating their rank among the infinite cardinals.

<span class="mw-page-title-main">Cardinality</span> Definition of the number of elements in a set

In mathematics, cardinality describes a relationship between sets which compares their relative size. For example, the sets and are the same size as they each contain 3 elements. Beginning in the late 19th century, this concept was generalized to infinite sets, which allows one to distinguish between different types of infinity, and to perform arithmetic on them. There are two notions often used when referring to cardinality: one which compares sets directly using bijections and injections, and another which uses cardinal numbers. The cardinality of a set may also be called its size, when no confusion with other notions of size is possible.

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

In mathematics, an uncountable set, informally, is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger than aleph-null, the cardinality of the natural numbers.

<span class="mw-page-title-main">Cantor's diagonal argument</span> Proof in set theory

Cantor's diagonal argument is a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers – informally, that there are sets which in some sense contain more elements than there are positive integers. Such sets are now called uncountable sets, and the size of infinite sets is treated by the theory of cardinal numbers, which Cantor began.

In mathematics, transfinite numbers or infinite numbers are numbers that are "infinite" in the sense that they are larger than all finite numbers. These include the transfinite cardinals, which are cardinal numbers used to quantify the size of infinite sets, and the transfinite ordinals, which are ordinal numbers used to provide an ordering of infinite sets. The term transfinite was coined in 1895 by Georg Cantor, who wished to avoid some of the implications of the word infinite in connection with these objects, which were, nevertheless, not finite. Few contemporary writers share these qualms; it is now accepted usage to refer to transfinite cardinals and ordinals as infinite numbers. Nevertheless, the term transfinite also remains in use.

In mathematics, two sets or classes A and B are equinumerous if there exists a one-to-one correspondence (or bijection) between them, that is, if there exists a function from A to B such that for every element y of B, there is exactly one element x of A with f(x) = y. Equinumerous sets are said to have the same cardinality (number of elements). The study of cardinality is often called equinumerosity (equalness-of-number). The terms equipollence (equalness-of-strength) and equipotence (equalness-of-power) are sometimes used instead.

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" λ from another cardinal by repeated successor operations. These cardinals are sometimes called simply "limit cardinals" when the context is clear.

In mathematics, particularly in set theory, the beth numbers are a certain sequence of infinite cardinal numbers, conventionally written , where is the Hebrew letter beth. The beth numbers are related to the aleph numbers, but unless the generalized continuum hypothesis is true, there are numbers indexed by that are not indexed by .

In mathematical analysis, and applications in geometry, applied mathematics, engineering, and natural sciences, a function of a real variable is a function whose domain is the real numbers , or a subset of that contains an interval of positive length. Most real functions that are considered and studied are differentiable in some interval. The most widely considered such functions are the real functions, which are the real-valued functions of a real variable, that is, the functions of a real variable whose codomain is the set of real numbers.

In model theory, a branch of mathematical logic, the spectrum of a theory is given by the number of isomorphism classes of models in various cardinalities. More precisely, for any complete theory T in a language we write I(T, κ) for the number of models of T (up to isomorphism) of cardinality κ. The spectrum problem is to describe the possible behaviors of I(T, κ) as a function of κ. It has been almost completely solved for the case of a countable theory T.

Set theory of the real line is an area of mathematics concerned with the application of set theory to aspects of the real numbers.

In set theory, Cichoń's diagram or Cichon's diagram is a table of 10 infinite cardinal numbers related to the set theory of the reals displaying the provable relations between these cardinal characteristics of the continuum. All these cardinals are greater than or equal to , the smallest uncountable cardinal, and they are bounded above by , the cardinality of the continuum. Four cardinals describe properties of the ideal of sets of measure zero; four more describe the corresponding properties of the ideal of meager sets.

In mathematics, infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. Some of the things studied include continuous graphs and trees, extensions of Ramsey's theorem, and Martin's axiom. Recent developments concern combinatorics of the continuum and combinatorics on successors of singular cardinals.

<span class="mw-page-title-main">Real number</span> Number representing a continuous quantity

In mathematics, a real number is a number that can be used to measure a continuous one-dimensional quantity such as a distance, duration or temperature. Here, continuous means that pairs of values can have arbitrarily small differences. Every real number can be almost uniquely represented by an infinite decimal expansion.

In mathematics, the first uncountable ordinal, traditionally denoted by or sometimes by , is the smallest ordinal number that, considered as a set, is uncountable. It is the supremum of all countable ordinals. When considered as a set, the elements of are the countable ordinals, of which there are uncountably many.

In the mathematical field of set theory, the continuum means the real numbers, or the corresponding (infinite) cardinal number, denoted by . Georg Cantor proved that the cardinality is larger than the smallest infinity, namely, . He also proved that is equal to , the cardinality of the power set of the natural numbers.

In the mathematical discipline of set theory, a cardinal characteristic of the continuum is an infinite cardinal number that may consistently lie strictly between , and the cardinality of the continuum, that is, the cardinality of the set of all real numbers. The latter cardinal is denoted or . A variety of such cardinal characteristics arise naturally, and much work has been done in determining what relations between them are provable, and constructing models of set theory for various consistent configurations of them.

References

  1. "Transfinite number | mathematics". Encyclopedia Britannica. Retrieved 2020-08-12.
  2. 1 2 Weisstein, Eric W. "Continuum". mathworld.wolfram.com. Retrieved 2020-08-12.
  3. "Cantor theorem". Encyclopedia of Mathematics . EMS Press. 2001 [1994].
  4. 1 2 3 Stillwell, John (2002). "The continuum problem". American Mathematical Monthly. 109 (3): 286–297. doi:10.1080/00029890.2002.11919865. JSTOR   2695360. MR   1903582.
  5. 1 2 3 4 Johnson, D. L. (1998). "Cardinal Numbers". Chapter 6: Cardinal numbers. Elements of Logic via Numbers and Sets. Springer Undergraduate Mathematics Series. Springer London. pp. 113–130. doi:10.1007/978-1-4471-0603-6_6. ISBN   9781447106036.
  6. Gödel, Kurt (1940-12-31). Consistency of the Continuum Hypothesis. (AM-3). doi:10.1515/9781400881635. ISBN   9781400881635.
  7. Cohen, Paul J. (December 1963). "The Independence of the Continuum Hypothesis". Proceedings of the National Academy of Sciences. 50 (6): 1143–1148. Bibcode:1963PNAS...50.1143C. doi: 10.1073/pnas.50.6.1143 . ISSN   0027-8424. PMC   221287 . PMID   16578557.
  8. Cohen, Paul J. (January 1964). "The Independence of the Continuum Hypothesis, Ii". Proceedings of the National Academy of Sciences. 51 (1): 105–110. Bibcode:1964PNAS...51..105C. doi: 10.1073/pnas.51.1.105 . ISSN   0027-8424. PMC   300611 . PMID   16591132.
  9. 1 2 Was Cantor Surprised?, Fernando Q. Gouvêa, American Mathematical Monthly , March 2011.

Bibliography

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