Encyclopedia > Cardinality

Article Content

Cardinal number

Redirected from Cardinality

Cardinal numbers, or cardinals for short, are numbers used to denote the size of a mathematical set.

A natural 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. While in the finite world these two concepts coincide, when dealing with infinite sets one has to distinguish between the two. This idea was developed by Georg Cantor. The position aspect leads to ordinal numbers, which were also discovered by Cantor, while the size aspect is generalized by the cardinal numbers described here.

Two sets X and Y are said to have the same cardinality if there exists a bijection between X and Y; we then write | X | = | Y |. The cardinal number of X itself is often defined as the least ordinal number a with | a | = | X |. (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.)

Table of contents

Motivation

The intuitive idea of a cardinal is to create some 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, its necessary to appeal to more subtle notions.

A set Y is at least as big as a set X if there is a one-to-one mapping from the elements of X to the elements of Y. This is most easily understood by an example; suppose we have the sets X = {1,2,3} and Y = {5,6,7,8}, then using this notion of size we would observe that there is a mapping:

1 → 5

2 → 6

3 → 7

which is one-to-one, and hence conclude that Y has cardinality greater than or equal to X. The advantage of this notion is that it can be extended to infinite sets.

The classic example used is that of the infinite hotel paradox, also called Hilbert's paradox of the Grand Hotel. Suppose you are a 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. In this way we can see that the set {1,2,3,...} has the same cardinality as the set {2,3,4,...} since a one-to-one mapping from the first to 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 co-incides 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 is easily 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.

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

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 by the unicode character א) 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.

Note that without the axiom of choice there are sets which can not be well-ordered, and the definition of cardinal number given above does not work. It is still possible to define cardinal numbers (a mapping from sets to sets such that sets with the same cardinality have the same image), but it is slightly more complicated. One can also easily study cardinality without referring to cardinal numbers.

If X and Y are disjoint, the cardinal of the union of X and Y is called | X | + | Y |. We also define the product of cardinals by | X | × | Y | = | X × Y | (the product on the right hand side is the cartesian product). Also | X |^| Y | = | X^Y | where X^Y 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 |X|^|Z|
|X|^{|Y| x |Z|} = (|X|^|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 |}.

On the other hand, 2^| X | is the cardinality of the power set of the set X and Cantors 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.

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 set of real numbers, or the continuum, whence the name. 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).

Large cardinals

A cardinal is called a large cardinal if it belongs to a class of cardinals the existence of which (provably) cannot be proved within ZFC (assuming ZFC is consistent). Examples of large cardinals include:

External links

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia

Search over one million articles, find something about almost anything!