Added to Favorites

Popular Searches

Definitions

- This article describes cardinal numbers in mathematics. For cardinals in linguistics, see Names of numbers in English.

In mathematics, cardinal numbers, or cardinals for short, are generalized numbers used to measure the cardinality (size) of sets. For finite sets, the cardinality is given by a natural number, which is simply the number of elements in the set. There are also transfinite cardinal numbers that describe the sizes of infinite sets.

Cardinality is defined in terms of bijective functions. Two sets have the same cardinal number if and only if there is a bijection between them. In the case of finite sets, this agrees with the intuitive notion of size. In the case of infinite sets, the behavior is more complex. A fundamental theorem due to Georg Cantor shows that it is possible for infinite sets to have different cardinalities, and in particular the set of real numbers and the set of natural numbers do not have the same cardinal number. It is also possible for a proper subset of an infinite set to have the same cardinality as the original set, something that cannot happen with proper subsets of finite sets.

There is a transfinite sequence of cardinal numbers:

- $0,\; 1,\; 2,\; 3,\; cdots,\; n,\; cdots\; ;\; aleph\_0,\; aleph\_1,\; aleph\_2,\; cdots,\; aleph\_\{alpha\},\; cdots.$

Cardinality is studied for its own sake as part of set theory. It is also a tool used in branches of mathematics including combinatorics, abstract algebra, and mathematical analysis.

Cantor identified the fact that one-to-one correspondence is the way to tell that two sets have the same size, called "cardinality", in the case of finite sets. Using this one-to-one correspondence, he applied the concept to infinite sets; e.g. the set of natural numbers N = {0, 1, 2, 3, ...}. He called these cardinal numbers transfinite cardinal numbers, and defined all sets having a one-to-one correspondence with N to be denumerable (countably infinite) sets.

Naming this cardinal number $aleph\_0$, aleph-null, Cantor proved that any unbounded subset of N has the same cardinality as N, even if this might appear at first view, to run contrary to intuition. He also proved that the set of all ordered pairs of natural numbers is denumerable (which implies that the set of all rational numbers is denumerable), and later proved that the set of all algebraic numbers is also denumerable. Each algebraic number z may be encoded as a finite sequence of integers which are the coefficients in the polynomial equation of which it is the solution, i.e. the ordered n-tuple $(a\_0,\; a\_1,\; ...,\; a\_n),;\; a\_i\; in\; mathbb\{Z\},$ together with a pair of rationals $(b\_0,\; b\_1)$ such that z is the unique root of the polynomial with coefficients $(a\_0,\; a\_1,\; ...,\; a\_n)$ that lies in the interval $(b\_0,\; b\_1)$.

In his 1874 paper, Cantor proved that there exist higher-order cardinal numbers by showing that the set of real numbers has cardinality greater than that of N. His original presentation used a complex argument with nested intervals, but in an 1891 paper he proved the same result using his ingenious but simple diagonal argument. This new cardinal number, called the cardinality of the continuum, was termed c by Cantor.

Cantor also developed a large portion of the general theory of cardinal numbers; he proved that there is a smallest transfinite cardinal number ($aleph\_0$, aleph-null) and that for every cardinal number, there is a next-larger cardinal $(aleph\_1,\; aleph\_2,\; aleph\_3,\; cdots)$.

His continuum hypothesis is the proposition that c is the same as $aleph\_1$, 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.

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 coincide, 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 an injective (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

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. By the Schroeder-Bernstein theorem, this is equivalent to there being 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 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 explicitly write a segment of this mapping:

- 1 ↔ 2

- 2 ↔ 3

- 3 ↔ 4

- ...

- n ↔ n+1

- ...

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 can be proved 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.

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 Dedekind-infinite if there exists a proper subset Y of X with | X | = | Y |, and Dedekind-finite if such a subset doesn't exist. The finite cardinals are just the natural numbers, i.e., a set X is finite if and only if | X | = | n | = n for some natural number n. Any other set is infinite. Assuming the axiom of choice, it can be proved that the Dedekind notions correspond to the standard ones. It can also be proved that the cardinal $aleph\_0$ (aleph-0, where aleph is the first letter in the Hebrew alphabet, represented $aleph$) of the set of natural numbers is the smallest infinite cardinal, i.e. that any infinite set has a subset of cardinality $aleph\_0.$ The next larger cardinal is denoted by $aleph\_1$ and so on. For every ordinal α there is a cardinal number $aleph\_\{alpha\},$ and this list exhausts all infinite cardinal numbers.

We can define arithmetic operations on cardinal numbers that generalize the ordinary operations for natural numbers. 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.

If the axiom of choice holds, every cardinal κ has a successor κ^{+} > κ, and there are no cardinals between κ and its successor. For finite cardinals, the successor is simply κ+1. For infinite cardinals, the successor cardinal differs from the successor ordinal.

If X and Y are disjoint, addition is given by the union of X and Y. If the two sets are not already disjoint, then they can be replaced by disjoint sets, i.e. replace X by X×{0} and Y by Y×{1}.

- $|X|\; +\; |Y|\; =\; |\; X\; cup\; Y|.$

Zero is an additive identity κ + 0 = 0 + κ = κ.

Addition is associative (κ + μ) + ν = κ + (μ + ν).

Addition is commutative κ + μ = μ + κ.

Addition is non-decreasing in both arguments:

- $(kappa\; le\; mu)\; rightarrow\; ((kappa\; +\; nu\; le\; mu\; +\; nu)\; mbox\{\; and\; \}\; (nu\; +\; kappa\; le\; nu\; +\; mu)).$

If the axiom of choice holds, addition of infinite cardinal numbers is easy. If either $kappa$ or $mu$ is infinite, then

- $kappa\; +\; mu\; =\; max\{kappa,\; mu\},.$

The product of cardinals comes from the cartesian product.

- $|X|cdot|Y|\; =\; |X\; times\; Y|$

κ·0 = 0·κ = 0.

κ·μ = 0 $rightarrow$ (κ = 0 or μ = 0).

One is a multiplicative identity κ·1 = 1·κ = κ.

Multiplication is associative (κ·μ)·ν = κ·(μ·ν).

Multiplication is commutative κ·μ = μ·κ.

Multiplication is non-decreasing in both arguments: κ ≤ μ $rightarrow$ (κ·ν ≤ μ·ν and ν·κ ≤ ν·μ).

Multiplication distributes over addition: κ·(μ + ν) = κ·μ + κ·ν and (μ + ν)·κ = μ·κ + ν·κ.

If the axiom of choice holds, multiplication of infinite cardinal numbers is also easy. If either κ or μ is infinite and both are non-zero, then

- $kappacdotmu\; =\; max\{kappa,\; mu\}.$

Exponentiation is given by

- $|X|^$
> = left|X^Yright|

- κ
^{0}= 1 (in particular 0^{0}= 1), see empty function.

- If 1 ≤ μ, then 0
^{μ}= 0.

- 1
^{μ}= 1.

- κ
^{1}= κ.

- κ
^{μ + ν}= κ^{μ}·κ^{ν}.

- κ
^{μ·ν}= (κ^{μ})^{ν}.

- (κ·μ)
^{ν}= κ^{ν}·μ^{ν}.

- (1 ≤ ν and κ ≤ μ) $rightarrow$ (ν
^{κ}≤ ν^{μ}) and

- (κ ≤ μ) $rightarrow$ (κ
^{ν}≤ μ^{ν}).

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 no largest cardinal exists (because for any cardinal κ, we can always find a larger cardinal 2^{κ}). In fact, the class of cardinals is a proper class.

Neither roots nor logarithms can be defined uniquely for infinite cardinals.

All the remaining propositions in this section assume the axiom of choice:

- If κ and μ are both finite and greater than 1, and ν is infinite, then κ
^{ν}= μ^{ν}.

- If κ is infinite and μ is finite and non-zero, then κ
^{μ}= κ.

If 2 ≤ κ and 1 ≤ μ and at least one of them is infinite, then:

- Max (κ, 2
^{μ}) ≤ κ^{μ}≤ Max (2^{κ}, 2^{μ}).

Using König's theorem, one can prove κ < κ^{cf(κ)} and κ < cf(2^{κ}) for any infinite cardinal κ, where cf(κ) is the cofinality of κ.

The logarithm of an infinite cardinal number κ is defined as the least cardinal number μ such that κ ≤ 2^{μ}. Logarithms of infinite cardinals are useful in some fields of mathematics, for example in the study of cardinal invariants of topological spaces, though they lack some of the properties that logarithms of positive real numbers possess.

- Counting
- Names of numbers in English
- Large cardinal
- Nominal number
- Ordinal number
- Serial number
- The paradox of the greatest cardinal
- Aleph number
- Beth number

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

- Cardinality at ProvenMath formal proofs of the basic theorems on cardinality.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday September 25, 2008 at 13:36:42 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday September 25, 2008 at 13:36:42 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.