The cardinality $\mid A\mid$ of a finite set

Throughout this page $\mathbb{N}$ is the set of von Neumann naturals (The natural numbers $\mathbb{N}$ (von Neumann)): $0=\mathrm{\varnothing }$, $\sigma (n)=n\cup \{n\}$, and $n=\{m\in \mathbb{N}:m<n\}$ is itself the set of its predecessors, the order being the additive order of Order on the natural numbers identified with membership in On $\mathbb{N}$ the order is membership: $m<n⟺m\in n$. Write $A\approx B$ when a bijection $A\to B$ exists (Equinumerous sets, $A\approx B$ and $A⪯B$, Injection, surjection, bijection). A set $A$ is finite when $A\approx n$ for some $n\in \mathbb{N}$ (Finite, countably infinite, countable, uncountable).

Definition. Let $A$ be a finite set. Then there is exactly one $n\in \mathbb{N}$ with $A\approx n$, and we write

$\mid A\mid :=\text{that }n,$

the cardinality, or number of elements, of $A$. The notation $\mid A\mid$ is defined for finite $A$ only, and its value is a natural number.

Why exactly one, which is the whole content of the definition. At least one such $n$ exists: that is literally what "$A$ is finite" says. At most one exists: if $A\approx n$ and $A\approx m$ with $n,m\in \mathbb{N}$, then $n\approx A$, because the inverse of a bijection is a bijection, and hence $n\approx m$, because a composition of bijections is a bijection (Injection, surjection, bijection); and $n\approx m$ forces $n=m$ by claim 3 of The pigeonhole principle on $\mathbb{N}$. So $\mid A\mid$ names a single natural number and not a family of choices.

Four consequences, proved here because everything on this page uses them.

(a) $\mid n\mid =n$ for every $n\in \mathbb{N}$. The identity map ${\mathrm{i}\mathrm{d}}_n$ is a bijection $n\to n$, so $n\approx n$; thus $n$ is finite and the unique natural equinumerous with it is $n$ itself.

(b) $\mid \mathrm{\varnothing }\mid =0$, and a finite $A$ satisfies $\mid A\mid =0$ if and only if $A=\mathrm{\varnothing }$. Since $0=\mathrm{\varnothing }$, part (a) gives $\mid \mathrm{\varnothing }\mid =0$. Conversely, if $\mid A\mid =0$ then there is a bijection $f:A\to \mathrm{\varnothing }$; were some $a\in A$, the value $f(a)$ would be an element of $\mathrm{\varnothing }$, and $\mathrm{\varnothing }$ has none, so $A=\mathrm{\varnothing }$.

(c) Transport along a bijection. If $A$ is finite and $f:A\to B$ is a bijection, then $B$ is finite and $\mid B\mid =\mid A\mid$. Indeed $B\approx A$ through $f^{-1}$ and $A\approx \mid A\mid$, so $B\approx \mid A\mid$ by transitivity.

(d) Equality of cardinalities is equinumerosity. For finite $A$ and $B$: $\mid A\mid =\mid B\mid$ if and only if $A\approx B$. If the cardinalities agree then $A\approx \mid A\mid =\mid B\mid \approx B$; conversely $A\approx B$ gives $\mid B\mid =\mid A\mid$ by (c).

The natural numbers $\mathbb{N}$ (von Neumann)

Order on the natural numbers

On $\mathbb{N}$ the order is membership: $m<n⟺m\in n$

Equinumerous sets, $A\approx B$ and $A⪯B$

Injection, surjection, bijection

Finite, countably infinite, countable, uncountable

The pigeonhole principle on $\mathbb{N}$

• $\mathbb{N}$ contains $0$ here, and that is not a detail. Every index range on this page starts at $0$, a one-element set has cardinality $1=\{0\}$, and $\mid A\mid$ is never a positive-integer-only object. A statement about $\mid A\mid$ that is true only for $\mid A\mid \ge 1$ must say so.

• $\mid A\mid$ is a natural number, not a cardinal number. The theory of cardinals (Cardinal (initial ordinal) and cardinality ↗) is developed much later in the library and nothing here uses it, or any cardinal arithmetic: the pointer is orientation only. What makes the notation legitimate at this point in the reading order is exactly claim 3 of The pigeonhole principle on $\mathbb{N}$, and nothing more.

• What the definition does not supply. It asserts that some bijection $A\to \mid A\mid$ exists; it does not single one out, and nothing in the library does. Two sets can have equal cardinality with no distinguished bijection between them, which is the point of the counterexample on this page's companion.