|
|
|
|
|
Cardinality is a notion of the size of a set which does not rely on numbers. It is a relative notion. For instance, two sets may each have an infinite number of elements, but one may have a greater cardinality. That is, in a sense, one may have a ``more infinite'' number of elements. See Cantor diagonalization for an example of how the reals have a greater cardinality than the natural
numbers.
The formal definition of cardinality rests upon the notion mappings between sets:
Cardinality 1 The cardinality of a set $A$ is greater than or equal to the cardinality of a set $B$ if there is a one-to-one function (an injection) from $B$ to $A$ . Symbolically, we write $|A| \geq |B|$ .
and
Cardinality 2 Sets $A$ and $B$ have the same cardinality if there is a one-to-one and onto function (a bijection) from $A$ to $B$ . Symbolically, we write $|A| = |B|$ .
It can be shown that if $|A| \geq |B|$ and $|B| \geq |A|$ then $|A| = |B|$ . This is the Schröder-Bernstein Theorem.
Equality of cardinality is variously called equipotence, equipollence, equinumerosity, or equicardinality. For $|A| = |B|$ , we would say that ``$A$ is equipotent to $B$ '', ``$A$ is equipollent to $B$ '', or ``$A$ is equinumerous to $B$ ''.
An equivalent definition of cardinality is
Cardinality (alt. def.) 1 The cardinality of a set $A$ is the unique cardinal number $\kappa$ such that $A$ is equinumerous with $\kappa$ . The cardinality of $A$ is written $|A|$ .
This definition of cardinality makes use of a special class of numbers, called the cardinal numbers. This highlights the fact that, while cardinality can be understood and defined without appealing to numbers, it is often convenient and useful to treat cardinality in a ``numeric'' manner.
Some results on cardinality:
- $A$ is equipotent to $A$ .
- If $A$ is equipotent to $B$ , then $B$ is equipotent to $A$ .
- If $A$ is equipotent to $B$ and $B$ is equipotent to $C$ , then $A$ is equipotent to $C$ .
Proof. Respectively:
- The identity function on $A$ is a bijection from $A$ to $A$ .
- If $f$ is a bijection from $A$ to $B$ , then $f^{-1}$ exists and is a bijection from $B$ to $A$ .
- If $f$ is a bijection from $A$ to $B$ and $g$ is a bijection from $B$ to $C$ , then $f \circ g$ is a bijection from $A$ to $C$ .

The set of even integers $2\Z$ has the same cardinality as the set of integers $\Z$ : if we define $f\colon 2\Z \to \Z$ such that $f(x) = \frac{x}{2}$ , then $f$ is a bijection, and therefore $|2\Z| = |\Z|$ .
|
"cardinality" is owned by yark. [ full author list (2) | owner history (1) ]
|
|
(view preamble | get metadata)
Cross-references: integers, even integers, identity function, useful, class, cardinal number, equivalent, equality, theorem, bijection, onto, function, one-to-one, mappings, natural numbers, reals, Cantor diagonalization, elements, infinite, numbers
There are 221 references to this entry.
This is version 21 of cardinality, born on 2001-11-19, modified 2008-06-22.
Object id is 963, canonical name is Cardinality.
Accessed 61578 times total.
Classification:
| AMS MSC: | 03E10 (Mathematical logic and foundations :: Set theory :: Ordinal and cardinal numbers) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|