Back to the index. Or to the chambers

This article has 17 links. View as Cloud or List.

Number Equivalence Of Forcing Notions Bijection Identity Map Mapping Infinite Surjective Real Number Integer Function Class Cardinal Number Equality Injective Function Natural Number Even Number Cantors Diagonal Argument

Loading ...

Planetmath Browser (2008—2009)

BSD licence | A django site

All articles taken from PlanetMath.org snapshot under CC-BY-SA licence.

→ The original article on PlanetMath.org

Other Formats: LaTeX

New! You can click on formulas to copy the LaTeX source to your clipboard. | Math Videos

Cardinality

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

is greater than or equal to the cardinality of a set

if there is a one-to-one function (an injection) from

. Symbolically, we write $\vert A\vert \geq \vert B\vert$ .

and

Cardinality 2 Sets

and

have the same cardinality if there is a one-to-one and onto function (a bijection) from

. Symbolically, we write $\vert A\vert = \vert B\vert$ .

It can be shown that if $\vert A\vert \geq \vert B\vert$ and $\vert B\vert \geq \vert A\vert$ then $\vert A\vert = \vert B\vert$ . This is the Schröder-Bernstein Theorem.

Equality of cardinality is variously called equipotence, equipollence, equinumerosity, or equicardinality. For $\vert A\vert = \vert B\vert$ , we would say that “ is equipotent to ”, “ is equipollent to ”, or “ is equinumerous to ”.

An equivalent definition of cardinality is

Cardinality (alt. def.) 1 The cardinality of a set

is the unique cardinal number $\kappa$ such that

is equinumerous with $\kappa$ . The cardinality of

is written $\vert A\vert$ .

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.

Results

Some results on cardinality:

is equipotent to .
If is equipotent to , then is equipotent to .
If is equipotent to and is equipotent to , then is equipotent to .

Proof. Respectively:

The identity function on is a bijection from to .
If is a bijection from to , then $f^{-1}$ exists and is a bijection from to .
If is a bijection from to and is a bijection from to , then $f \circ g$ is a bijection from to .

$\qedsymbol$

Example

The set of even integers $2\mathbb{Z}$ has the same cardinality as the set of integers $\mathbb{Z}$ : if we define $f\colon 2\mathbb{Z}\to \mathbb{Z}$ such that $f(x) = \frac{x}{2}$ , then is a bijection, and therefore $\vert 2\mathbb{Z}\vert = \vert\mathbb{Z}\vert$ .

1	Equality
1	Real Number
1	Cardinal Number
1	Surjective
1	Class
1	Function
1	Natural Number
1	Mapping
1	Even Number
1	Identity Map
1	Equivalence Of Forcing Notions
1	Infinite
1	Injective Function
1	Integer
1	Number
1	Bijection
3	Cantors Diagonal Argument