# Definition:Cardinality

## Contents

## 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:

\(\displaystyle \exists x: \exists y: \exists z:\) | \(\) | \(\displaystyle x \in S \land y \in S \land z \in S\) | |||||||||||

\(\displaystyle \) | \(\land\) | \(\displaystyle x \ne y \land x \ne z \land y \ne z\) | |||||||||||

\(\displaystyle \) | \(\land\) | \(\displaystyle \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:

\(\displaystyle S_1\) | \(=\) | \(\displaystyle \set {-1, 0, 1}\) | |||||||||||

\(\displaystyle S_2\) | \(=\) | \(\displaystyle \set {x \in \Z: 0 < x < 6}\) | |||||||||||

\(\displaystyle S_3\) | \(=\) | \(\displaystyle \set {x^2 - x: x \in S_1}\) | |||||||||||

\(\displaystyle S_4\) | \(=\) | \(\displaystyle \set {X \in \powerset {S_2}: \card X = 3}\) | |||||||||||

\(\displaystyle S_5\) | \(=\) | \(\displaystyle \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

- 1915: Georg Cantor:
*Contributions to the Founding of the Theory of Transfinite Numbers*... (previous) ... (next): First Article: $\S 1$: The Conception of Power or Cardinal Number: $(3)$ - 1964: Steven A. Gaal:
*Point Set Topology*... (previous) ... (next): Introduction to Set Theory: $2$. Set Theoretical Equivalence and Denumerability - 1966: Richard A. Dean:
*Elements of Abstract Algebra*... (previous) ... (next): $\S 0.2$ - 1968: A.N. Kolmogorov and S.V. Fomin:
*Introductory Real Analysis*... (previous) ... (next): $\S 2.5$: The power of a set - 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): Appendix $\text{A}.2$: Cartesian Products and Relations - 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): Chapter $1$: Sets and mappings: $\S 1.3$: Mappings - 1994: Martin J. Osborne and Ariel Rubinstein:
*A Course in Game Theory*... (previous) ... (next): $1.7$: Terminology and Notation - 1996: John F. Humphreys:
*A Course in Group Theory*... (previous) ... (next): Chapter $5$: Cosets and Lagrange's Theorem: Proposition $5.8$ Notation - 1996: H. Jerome Keisler and Joel Robbin:
*Mathematical Logic and Computability*... (previous) ... (next): Appendix $\text{A}.6$: Cardinality - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next): Entry:**cardinal number (cardinality)** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next): Entry:**cardinal number (cardinality)** - 2010: Raymond M. Smullyan and Melvin Fitting:
*Set Theory and the Continuum Problem*(revised ed.) ... (previous) ... (next): Chapter $1$: General Background: $\S 5$ The continuum problem - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next): Entry:**cardinality**

- 1972: A.G. Howson:
*A Handbook of Terms used in Algebra and Analysis*... (previous) ... (next): $\S 4$: Number systems $\text{I}$: A set-theoretic approach

- 2005: René L. Schilling:
*Measures, Integrals and Martingales*... (previous) ... (next): $2.3$ - 2008: Paul Halmos and Steven Givant:
*Introduction to Boolean Algebras*... (previous) ... (next): Appendix $\text{A}$: Set Theory: Cardinality - 2012: M. Ben-Ari:
*Mathematical Logic for Computer Science*(3rd ed.) ... (previous) ... (next): Appendix $\text{A}.5$: Definition $\text{A}.25$