# 4.5: Finite Cardinality

• Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
• Google and Massachusetts Institute of Technology via MIT OpenCourseWare

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$

( \newcommand{\kernel}{\mathrm{null}\,}\) $$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\id}{\mathrm{id}}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\kernel}{\mathrm{null}\,}$$

$$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$

$$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$

$$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$

A finite set is one that has only a finite number of elements. This number of elements is the “size” or cardinality of the set:

Definition $$\PageIndex{1}$$

If A is a finite set, the cardinality of $$A$$, written $$|A|$$, is the number of elements in $$A$$.

A finite set may have no elements (the empty set), or one element, or two elements, ... , so the cardinality of finite sets is always a nonnegative integer.

Now suppose $$R : A \rightarrow B$$ is a function. This means that every element of $$A$$ contributes at most one arrow to the diagram for $$R$$, so the number of arrows is at most the number of elements in $$A$$. That is, if $$R$$ is a function, then

$\nonumber |A| \geq \text{#arrows.}$

If $$R$$ is also surjective, then every element of $$B$$ has an arrow into it, so there must be at least as many arrows in the diagram as the size of $$B$$. That is,

$\nonumber \text{#arrows} \geq |B|.$

Combining these inequalities implies that if $$R$$ is a surjective function, then $$|A| \geq |B|$$.

In short, if we write $$A$$ surj $$B$$ to mean that there is a surjective function from $$A$$ to $$B$$, then we’ve just proved a lemma: if $$A$$ surj $$B$$ for finite sets $$A$$, $$B$$, then $$|A| \geq |B|$$. The following definition and lemma lists this statement and three similar rules relating domain and codomain size to relational properties.

Definition $$\PageIndex{2}$$

Let $$A$$, $$B$$ be (not necessarily finite) sets. Then

1. $$A$$ surj $$B$$ iff there is a surjective function from $$A$$ to $$B$$.
2. $$A$$ inj $$B$$ iff there is a injective total from $$A$$ to $$B$$.
3. $$A$$ bij $$B$$ iff there is a bijective from $$A$$ to $$B$$.

Lemma 4.5.3. For finite sets $$A$$, $$B$$:

1. If $$A$$ surj $$B$$, then $$|A| \geq |B|$$.
2. If $$A$$ inj $$B$$, then $$|A| \leq |B|$$.
3. If $$A$$ bij $$B$$, then $$|A| =|B|$$.

Proof. We’ve already given an “arrow” proof of implication 1. Implication 2. follows immediately from the fact that if $$R$$ has the [$$\leq 1$$ out], function property, and the [$$\geq 1$$ in], surjective property, then $$R^{-1}$$ is total and injective, so $$A$$ surj $$B$$ iff $$B$$ inj $$A$$. Finally, since a bijection is both a surjective function and a total injective relation, implication 3. is an immediate consequence of the first two. $$\quad \blacksquare$$

Lemma 4.5.3.1. has a converse: if the size of a finite set, $$A$$, is greater than or equal to the size of another finite set, $$B$$, then it’s always possible to define a surjective function from $$A$$ to $$B$$. In fact, the surjection can be a total function. To see how this works, suppose for example that

\begin{aligned} A &= \{a_0, a_1, a_2, a_3, a_4, a_5\} \\ B &= \{b_0, b_1, b_2, b_3.\} \end{aligned}

Then define a total function f W A ! B by the rules $$f : A \rightarrow B$$ by the rules

$\nonumber f(a_0) ::= b_0, f(a_1) ::= b_1, f(a_2) ::= b_2, f(a_3) = f(a_4) = f(a_5) ::= b_3$

More concisely,

$\nonumber f(a_i) ::= b_{min(i, 3)},$

for $$0 \leq i \leq 5$$. Since 5 $$\geq$$ 3, this $$f$$ is a surjection.

So we have figured out that if $$A$$ and $$B$$ are finite sets, then $$|A| \geq |B|$$ if and only if $$A$$ surj $$B$$. All told, this argument wraps up the proof of a theorem that summarizes the whole finite cardinality story:

Theorem $$\PageIndex{4}$$

[Mapping Rules] For finite sets, $$A$$, $$B$$,

$\label{4.5.1}|A| \geq |B| \textit{ iff } A \text{ surj } B,$

$\label{4.5.2} |A| \leq |B| \textit{ iff } A \text{ inj } B,$

$\label{4.5.3} |A| = |B| \textit{ iff } A \text{ bij } B.$

## How Many Subsets of a Finite Set?

As an application of the bijection mapping rule (\ref{4.5.3}), we can give an easy proof of:

Theorem 4.5.5. There are 2n subsets of an n-element set. That is,

Theorem $$\PageIndex{5}$$

There are $$2^n$$ subsets of an n-element set. That is,

$\nonumber |A| = n \textit{ implies } |\text{pow}(A)| = 2^n.$

For example, the three-element set $$\{a_1, a_2, a_3\}$$ has eight different subsets:

$\nonumber \begin{array}{cccc} & \emptyset & \{a_1\} & \{a_2\} & \{a_1, a_2\} \\ & \{a_3\} & \{a_1, a_3\} & \{a_2, a_3\} & \{a_1, a_2, a_3\} \end{array}$

Theorem 4.5.5 follows from the fact that there is a simple bijection from subsets of $$A$$ to $$\{0 1\}^n$$, the n-bit sequences. Namely, let $$a_1, a_2, \ldots, a_n$$ be the elements of $$A$$. The bijection maps each subset of $$S \subseteq A$$ to the bit sequence $$(b_1, b_2, \ldots, b_n)$$ defined by the rule that

$\nonumber b_i = 1 \textit{ iff } a_i \in S.$

For example, if $$n = 10$$, then the subset $$\{a_2, a_3, a_5, a_7, a_{10}\}$$ maps to a 10-bit sequence as follows:

subset: { $$a_2$$, $$a_3$$, $$a_5$$, $$a_7$$, $$a_{10}$$}

sequence: (0, 1, 1, 0, 1, 0, 1, 0, 0, 1)

Now by bijection case of the Mapping Rules 4.5.4.(\ref{4.5.3}),

$\nonumber |\text{pow}(A)| = |\{0, 1\}^n |.$

But every computer scientist knows6 that there are $$2^n$$ n-bit sequences! So we’ve proved Theorem 4.5.5!

6In case you’re someone who doesn’t know how many n-bit sequences there are, you’ll find the $$2^n$$ explained in Section 14.2.2.

This page titled 4.5: Finite Cardinality is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer (MIT OpenCourseWare) .