PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: Very high
cardinality (Definition)

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 $ 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 $ \vert A\vert \geq \vert B\vert$.

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 $ \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 “$ 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 $ \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:

  1. $ A$ is equipotent to $ A$.
  2. If $ A$ is equipotent to $ B$, then $ B$ is equipotent to $ A$.
  3. If $ A$ is equipotent to $ B$ and $ B$ is equipotent to $ C$, then $ A$ is equipotent to $ C$.
Proof. Respectively:
  1. The identity function on $ A$ is a bijection from $ A$ to $ A$.
  2. If $ f$ is a bijection from $ A$ to $ B$, then $ f^{-1}$ exists and is a bijection from $ B$ to $ A$.
  3. 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$.

$ \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 $ f$ is a bijection, and therefore $ \vert 2\mathbb{Z}\vert = \vert\mathbb{Z}\vert$.



"cardinality" is owned by yark. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: order (of a group), generalized continuum hypothesis, cardinal number, Dedekind-infinite

Other names:  size
Also defines:  equipotence, equipotent, equicardinality, equipollence, equipollent, equinumerosity

Attachments:
uniqueness of cardinality (Theorem) by mathcam
cardinality of disjoint union of finite sets (Theorem) by mathcam
Log in to rate this entry.
(view current ratings)

Cross-references: integers, even integers, identity function, class, cardinal number, equivalent, equality, bijection, onto, function, one-to-one, mappings, natural numbers, reals, Cantor diagonalization, infinite, numbers
There are 207 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 50211 times total.

Classification:
AMS MSC: 03E10 (Mathematical logic and foundations :: Set theory :: Ordinal and cardinal numbers)
Pending Errata and Addenda
None.
[ View all 9 ]
Discussion
Style: Expand: Order:
forum policy
Do proper classes have cardinalities? by archibal on 2004-02-12 23:21:49
This entry defines cardinality, as a concept, only for sets. Can it be extended to deal with proper classes? If so, do they vary in cardinality?
[ reply | up ]
Interact
post | correct | update request | add derivation | add example | add (any)