Definition:Cardinality

From ProofWiki
Jump to navigation Jump to search

Definition

Two sets (either finite or infinite) which are equivalent are said to have the same cardinality.

The cardinality of a set $S$ is written $\card S$.


Cardinality of Finite Set

Let $S$ be a finite set.

The cardinality $\card S$ of $S$ is the number of elements in $S$.

That is, if:

$S \sim \N_{< n}$

where:

$\sim$ denotes set equivalence
$\N_{<n}$ is the set of all natural numbers less than $n$

then we define:

$\card S = n$


Cardinality of Infinite Set

Let $S$ be an infinite set.

The cardinality $\card S$ of $S$ can be indicated as:

$\card S = \infty$

However, it needs to be noted that this just means that the cardinality of $S$ cannot be assigned a number $n \in \N$.


It means that $\card S$ is at least $\aleph_0$ (aleph null).


Cardinality of Natural Numbers

When the natural numbers are defined as von Neumann construction of natural numbers, the cardinality function can be viewed as the identity mapping on $\N$.

That is:

$\forall n \in N: \card n := n$


Also defined as

Some authors, working to a particular mathematical agenda, do not discuss the cardinality of an infinite set, and instead limit their definition of this concept to the finite case.

Some others gloss over the definition for the cardinality of a finite set, perhaps on the understanding that the definition is trivial, and instead raise the concept only in the infinite case.


Also known as

Some authors prefer the term order instead of cardinality, particularly in the context of finite sets.

Georg Cantor used the term power and equated it with the term cardinal number, using the notation $\overline {\overline M}$ for the cardinality of $M$.

Some sources cut through all the complicated language and call it the size.


Some sources use $\map {\#} S$ (or a variant) to denote set cardinality. This notation has its advantages in certain contexts, and is used on occasion on this website.

Others use $\map C S$, but this is easy to confuse with other uses of the same or similar notation.

A clear but relatively verbose variant is $\Card \paren S$ or $\operatorname{card} \paren S$.

1968: A.N. Kolmogorov and S.V. Fomin‎: Introductory Real Analysis use $\map m A$ for the power of the set $A$.

Further notations are $\map n A$ and $\overline A$.


Examples

Cardinality $3$

Let $S$ be a set.

Then $S$ has cardinality $3$ if and only if:

\(\ds \exists x: \exists y: \exists z:\) \(\) \(\ds x \in S \land y \in S \land z \in S\)
\(\ds \) \(\land\) \(\ds x \ne y \land x \ne z \land y \ne z\)
\(\ds \) \(\land\) \(\ds \forall w: \paren {w \in S \implies \paren {w = x \lor w = y \lor w = z} }\)


That is:

$S$ contains elements which can be labelled $x$, $y$ and $z$
Each of these elements is distinct from the others
Every element of $S$ is either $x$, $y$ or $z$.


Let:

\(\ds S_1\) \(=\) \(\ds \set {-1, 0, 1}\)
\(\ds S_2\) \(=\) \(\ds \set {x \in \Z: 0 < x < 6}\)
\(\ds S_3\) \(=\) \(\ds \set {x^2 - x: x \in S_1}\)
\(\ds S_4\) \(=\) \(\ds \set {X \in \powerset {S_2}: \card X = 3}\)
\(\ds S_5\) \(=\) \(\ds \powerset \O\)


Cardinality of $S_1 = \set {-1, 0, 1}$

The cardinality of $S_1$ is given by:

$\card {S_1} = 3$


Cardinality of $S_2 = \set {x \in \Z: 0 < x < 6}$

The cardinality of $S_2$ is given by:

$\card {S_2} = 5$


Cardinality of $S_3 = \set {x^2 - x: x \in S_1}$

The cardinality of $S_3$ is given by:

$\card {S_3} = 2$


Cardinality of $S_4 = \set {X \in \powerset {S_2}: \card X = 3}$

The cardinality of $S_4$ is given by:

$\card {S_4} = 10$


Cardinality of $S_5 = \powerset \O$

The cardinality of $S_5$ is given by:

$\card {S_5} = 1$


Also see

  • Results about cardinality can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Cardinality&oldid=694235"