# Definition:Cardinality

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

- 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$. Sets - 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 - 1979: John E. Hopcroft and Jeffrey D. Ullman:
*Introduction to Automata Theory, Languages, and Computation*... (previous) ... (next): Chapter $1$: Preliminaries: $1.4$ Set Notation: Infinite sets - 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):**cardinal number (cardinality)** - 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 - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**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 - 2012: M. Ben-Ari:
*Mathematical Logic for Computer Science*(3rd ed.) ... (previous) ... (next): Appendix $\text{A}.5$: Definition $\text{A}.25$ - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next):**cardinality**

This page may be the result of a refactoring operation.As such, the following source works, along with any process flow, will need to be reviewed. When this has been completed, the citation of that source work (if it is appropriate that it stay on this page) is to be placed above this message, into the usual chronological ordering.In particular: Determine whether there is a separate definition for infinite cardinality.If you have access to any of these works, then you are invited to review this list, and make any necessary corrections.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{SourceReview}}` from the code. |

- 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