Cardinal number
|
|
In linguistics, cardinal numbers is the name given to number words that are used for quantity (one, two, three), as opposed to ordinal numbers, words that are used for order (first, second, third). See How to name numbers in English.
In mathematics, cardinal numbers, or cardinals for short, are numbers used to denote the size of a set. Since mathematics is often concerned with infinite objects, a study of cardinality tries to discuss the size of infinite sets. Perhaps counterintuitively, one of the most basic results is that not all infinite objects are of the same size, and there is a formal characterization of how some infinite objects are strictly smaller than other infinite objects. Concepts of cardinality are embedded in most branches of mathematics and are essential to their study. It is also an area studied for its own sake as part of set theory, particularly in trying to describe the properties of large cardinals.
| Contents |
History
The cardinal numbers were invented by Georg Cantor, when he was developing the set theory now called naive set theory in 1874–1884.
He first established cardinality as an instrument to compare finite sets; e.g. the sets {1,2,3} and {2,3,4} are not equal, but have the same cardinality.
Cantor invented the one-to-one correspondence, which easily showed that two finite sets had the same cardinality if there was a one-to-one correspondence between the members of the set. Using this one-to-one correspondence, he transferred the concept to infinite sets; i.e the set of natural numbers N = {1, 2, 3, ...}. He called these cardinal numbers transfinite cardinal numbers, and defined all sets that had a one-to-one correspondence with N to be denumerably infinite sets.
Naming this cardinal number <math>\aleph_0<math>, aleph-null, Cantor proved that many subsets of N have the same cardinality as N, even if this might be against intuition at first. He also proved that the set of all ordered pairs of natural numbers is denumerably infinite, and later that the set of all algebraic numbers (every member of the set is a set of numbers of its own <math>(a_0, a_1, ..., a_n),\;\; a_i \in \mathbb{N}<math>, like an extended ordered pair) is denumerably infinite.
At this point, in 1874, there was a curiosity whether all infinite sets are denumerably infinite, and what the use would be in that case.
But, later that year, Cantor succeeded in proving that there were higher-order cardinal numbers using the ingenious but simple Cantor's diagonal argument. This new cardinal number, called the cardinality of the continuum, was termed c by Cantor.
Cantor also developed a lot of the general theory of cardinal numbers; he proved that there is a transfinite cardinal number that is the smallest (<math>\aleph_0<math>, aleph-null) and that for every cardinal number, there is a next-larger cardinal (<math>\aleph_1, \aleph_2, \aleph_3, \cdots<math>).
The later continuum hypothesis suggests that c is the same as <math>\aleph_1<math>, but this has been found to be independent of the standard axioms of mathematical set theory; it can neither be proved nor disproved under the standard assumptions.
Motivation
In informal use, a cardinal number is what is normally referred to as a counting number. They may be identified with the natural numbers beginning with 0 (i.e. 0, 1, 2, ...). The counting numbers are exactly what can be defined formally as the finite cardinal numbers. Infinite cardinals only occur in higher-level mathematics and logic.
More formally, a non-zero number can be used for two purposes: to describe the size of a set, or to describe the position of an element in a sequence. For finite sets and sequences it is easy to see that these two notions co-incide, since for every number describing a position in a sequence we can construct a set which has exactly the right size, e.g. 3 describes the position of 'c' in the sequence <'a','b','c','d',...>, and we can construct the set {a,b,c} which has 3 elements. However when dealing with infinite sets it is essential to distinguish between the two --- the two notions are in fact different for infinite sets. Considering the position aspect leads to ordinal numbers, while the size aspect is generalized by the cardinal numbers described here.
The intuition behind the formal definition of cardinal is the construction of a notion of the relative size or "bigness" of a set without reference to the kind of members which it has. For finite sets this is easy; one simply counts the number of elements a set has. In order to compare the sizes of larger sets, it is necessary to appeal to more subtle notions.
A set Y is at least as big as, or greater than or equal to a set X if there is a one-to-one mapping from the elements of X to the elements of Y. A one-to-one mapping identifies each element of the set X with a unique element of the set Y. This is most easily understood by an example; suppose we have the sets X = {1,2,3} and Y = {a,b,c,d}, then using this notion of size we would observe that there is a mapping:
- 1 → a
- 2 → b
- 3 → c
which is one-to-one, and hence conclude that Y has cardinality greater than or equal to X. Note the element d has no element mapping to it, but this is permitted as we only require a one-to-one mapping, and not necessarily a one-to-one and onto mapping. The advantage of this notion is that it can be extended to infinite sets.
We can then extend this to an equality-style relation. Two sets X and Y are said to have the same cardinality if there exists a bijection between X and Y, or equivalently both a one-to-one mapping from X to Y and a one-to-one mapping from Y to X. We then write | X | = | Y |. The cardinal number of X itself is often defined as the least ordinal number a with | a | = | X |. This is called the von Neumann cardinal assignment; for this definition to make sense, it must be proved that every set has the same cardinality as some ordinal; this statement is the well-ordering principle. It is however possible to discuss the relative cardinality of sets without explicitly assigning names to objects.
The classic example used is that of the infinite hotel paradox, also called Hilbert's paradox of the Grand Hotel. Suppose you are an innkeeper at a hotel with an infinite number of rooms. The hotel is full, and then a new guest arrives. It's possible to fit the extra guest in by asking the guest who was in room 1 to move to room 2, the guest in room 2 to move to room 3, and so on, leaving room 1 vacant. We can explicity write a segment of this mapping:
- 1 ↔ 2
- 2 ↔ 3
- 3 ↔ 4
- ...
- n ↔ n+1
- ...
In this way we can see that the set {1,2,3,...} has the same cardinality as the set {2,3,4,...} since a bijection between the first and the second has been shown. This motivates the definition of an infinite set being any set which has a proper subset of the same cardinality; in this case {2,3,4,...} is a proper subset of {1,2,3,...}.
When considering these large objects, we might also want to see if the notion of counting order coincides with that of cardinal defined above for these infinite sets. It happens that it doesn't; by considering the above example we can see that if some object "one greater than infinity" exists, then it must have the same cardinality as the infinite set we started out with. It is possible to use a different formal notion for number, called ordinals, based on the ideas of counting and considering each number in turn, and we discover that the notions of cardinality and ordinality are divergent once we move out of the finite numbers.
It is provable that the cardinality of the real numbers is greater than that of the natural numbers just described. This can be visualized using Cantor's diagonal argument; classic questions of cardinality (for instance the continuum hypothesis) are concerned with discovering whether there is some cardinal between some pair of other infinite cardinals. In more recent times mathematicians have been describing the properties of larger and larger cardinals.
Since cardinality is such a common concept in mathematics, a variety of names are in use. Sameness of cardinality is sometimes referred to as equipotence, equipollence, or equinumerosity. It is thus said that two sets with the same cardinality are, respectively, equipotent, equipollent, or equinumerous.
Formal definition
Formally, the order among cardinal numbers is defined as follows: | X | ≤ | Y | means that there exists an injective function from X to Y. The Cantor-Bernstein-Schroeder theorem states that if | X | ≤ | Y | and | Y | ≤ | X | then | X | = | Y |. The axiom of choice is equivalent to the statement that given two sets X and Y, either | X | ≤ | Y | or | Y | ≤ | X |.
Formally, assuming the axiom of choice, cardinality of a set X is the least ordinal α such that there is a bijection between X and α. If the axiom of choice is not assumed and X does not have a well-ordering, the cardinality of X is defined to be the set of all sets which are equinumerous with X and have the least rank that a set equinumerous with X can have.
A set X is infinite, or equivalently, its cardinal is infinite, if there exists a proper subset Y of X with | X | = | Y |. A cardinal which is not infinite is called finite; it can then be proved that the finite cardinals are just the natural numbers, i.e., that a set X is finite if and only if | X | = | n | = n for some natural number n. It can also be proved that the cardinal <math>\aleph_0<math> (aleph-0, where aleph is the first letter in the Hebrew alphabet, represented א) of the set of natural numbers is the smallest infinite cardinal, i.e., that any infinite set admits a subset of cardinality <math>\aleph_0<math>. The next larger cardinal is denoted by <math>\aleph_1<math> and so on. For every ordinal a there is a cardinal number <math>\aleph_a<math>, and this list exhausts all cardinal numbers.
Cardinal arithmetic
We can define arithmetic operations on cardinal numbers that generalize the ordinary operations for natural numbers. If X and Y are disjoint, addition is given by the union of X and Y
- |X| + |Y| = |X ∪ Y|
The product of cardinals by the cartesian product
- |X| |Y| = |X × Y|
Exponentiation is given by
- |X||Y| = |XY|
where XY is defined as the set of all functions from Y to X. It can be shown that for finite cardinals these operations coincide with the usual operations for natural numbers. Furthermore, these operations share many properties with ordinary arithmetic:
- addition and multiplication of cardinal numbers is associative and commutative
- multiplication distributes over addition
- |X||Y| + |Z| = |X||Y| |X||Z|
- |X||Y| |Z| = (|X||Y|)|Z|
- (|X||Y|)|Z| = |X||Z| |Y||Z|
The addition and multiplication of infinite cardinal numbers (assuming the axiom of choice) is easy: if X or Y is infinite and both are non-empty, then
- |X| + |Y| = |X||Y| = max{|X|, |Y|}.
Note that 2| X | is the cardinality of the power set of the set X and Cantor's diagonal argument shows that 2| X | > | X | for any set X. This proves that there exists no largest cardinal. In fact, the class of cardinals is a proper class.
Further rules for exponentiation are as follows:
- |X|0 = 1 (in particular 00 = 1), see empty function
- 0|Y| = 0 if Y is not empty
- 1|Y| = 1
- |X| ≤ |Y| implies that |X||Z| ≤ |Y||Z|
- if |X| and |Y| are both finite and greater than 1, and Z is infinite, then |X||Z| = |Y||Z|
- if X is infinite and Y is finite and non-empty then |X||Y| = |X|.
The continuum hypothesis
The continuum hypothesis (CH) states that there are no cardinals strictly between <math>\aleph_0<math> and <math>2^{\aleph_0}<math>. The latter cardinal number is also often denoted by c; it is the cardinality of the continuum (the set of real numbers). In this case <math>2^{\aleph_0}<math> = <math>\aleph_1<math>. The generalized continuum hypothesis (GCH) states that for every infinite set X, there are no cardinals strictly between | X | and 2| X |. The continuum hypothesis is independent from the usual axioms of set theory, the Zermelo-Fraenkel axioms together with the axiom of choice (ZFC).
See also
References
- Hahn, Hans, Infinity, Part IX, Chapter 2, Volume 3 of The World of Mathematics. New York: Simon and Schuster, 1956.
- Halmos, Paul, 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).
External links
- http://web.archive.org/web/20010528181608/http://logweb.terrashare.com/text/logic/infini.txt
- http://www.ii.com/math/cardinals/
|
Topics in mathematics related to quantity | |
| Numbers | Natural numbers | Integers | Rational numbers | Constructible numbers | Algebraic numbers | Computable numbers | Real numbers | Complex numbers | Split-complex numbers | Bicomplex numbers | Hypercomplex numbers | Quaternions | Octonions | Sedenions | Superreal numbers | Hyperreal numbers | Surreal numbers | Nominal numbers | Ordinal numbers | Cardinal numbers | p-adic numbers | Integer sequences | Mathematical constants | Large numbers | Infinity |
da:Kardinaltal de:Kardinalzahl (Mathematik) he:עוצמה nl:Cardinaliteit it:Numero cardinale ja:基数 pl:Liczba kardynalna pt:Nmero cardinal ru:Мощность множества sl:kardinalno število sv:Kardinaltal