12.1: Finite Sets

Recall.

For \(m\in\mathbb{N}\) we have defined the counting set

\begin{equation*} \mathbb{N}_{<m} = \{n \in \mathbb{N} \vert n \lt m\} = \{ 0, \, 1, \, \ldots, \, m-1\} \text{.} \end{equation*}

Clearly, \(\mathbb{N}_{<m}\) contains exactly \(m\) elements. In fact, we have defined the number \(m\) to be the set \(\mathbb{N}_{<m}\text{.}\) (See Example 11.4.2.)

As the terminology implies, we will use these sets to count the elements of other sets. In particular, given a set \(A\text{,}\) if we can match up the elements of \(A\) with the elements of \(\mathbb{N}_{<m}\text{,}\) one for one, then \(A\) must also contain exactly \(m\) elements.

Definition: Finite Set

a set \(A\) for which there exists a bijection \(\mathbb{N}_{<m} \to A\) for some \(m \in \mathbb{N}\text{,}\) \(m \gt 0\)

Fact \(\PageIndex{1}\): Uniqueness of counting number

For finite set \(A\) there exists one unique natural number \(m\) for which a bijection \(\mathbb{N}_{<m} \to A\) exists.

Remark \(\PageIndex{1}\)

Suppose \(A\) is finite. While there is only one number \(m\) for which a bijection \(\mathbb{N}_{<m} \to A\) exists, there can be many such bijections, and the number of bijections increases as \(m\) increases.

Checkpoint \(\PageIndex{1}\)

Prove Fact \(\PageIndex{1}\).

Definition: Cardinality (of a finite set \(A\))

the unique natural number \(m\) for with a bijection \(\mathbb{N}_{<m} \to A\) exists

Definition: \(\vert A \vert\)

the cardinality of the finite set \(A\)

Definition: \(\text{card} A\)

alternative notation for the cardinality of the finite set \(A\)

Definition: \(\#\{\dots\}\)

alternative notation for the cardinality of the set defined by \(\{\dots\}\)

Example \(\PageIndex{1}\)

For \(\Sigma = \{a, b, \ldots, z\} \text{,}\) we have \(\vert \Sigma \vert = 26\text{.}\) Below are two example bijections \(\varphi,\psi: \mathbb{N}_{<26} \rightarrow \Sigma\) that verify this cardinality number.

Bijections \(\varphi,\psi: \mathbb{N}_{<26} \rightarrow \Sigma\) defined by a table of values.

\(\sigma\)	\(0\)	\(1\)	\(2\)	\(3\)	\(\cdots\)	\(24\)	\(25\)
\(\varphi(\sigma)\)	\(\text{a}\)	\(\text{b}\)	\(\text{c}\)	\(\text{d}\)	\(\cdots\)	\(\text{y}\)	\(\text{z}\)
\(\psi(\sigma)\)	\(\text{a}\)	\(\text{z}\)	\(\text{b}\)	\(\text{y}\)	\(\cdots\)	\(\text{m}\)	\(\text{n}\)

Cardinality of an empty set.

What about the empty set? Clearly we should have \(\vert \varnothing \vert = 0\text{.}\) But is this consistent with our definition of cardinality?

Definition: Empty Function

a function with domain \(\varnothing\)

If we accept the existence of empty functions \(\varnothing \to X\) for every set \(X\text{,}\) then the properties of such functions that we need in order to establish \(\vert \varnothing \vert = 0\) will be vacuously true.

Proposition \(\PageIndex{1}\): Properties of empty functions.

1. For every set \(X\text{,}\) an empty function \(\varnothing \to X\) is injective.
2. An empty function \(\varnothing \to \varnothing\) is a bijection.

Proof

You were asked to verify these statements in Exercise 10.7.12.

Corollary \(\PageIndex{1}\)

The cardinality of the empty set is \(0\text{.}\)

Proof.

We are required to demonstrate an example of a bijection \(\mathbb{N}_{<0} \to \varnothing\text{.}\) But

\begin{equation*} \mathbb{N}_{<0} = \{n \in \mathbb{N} \vert n \lt 0 \} = \varnothing \text{,} \end{equation*}
so Statement 2 of Proposition \(\PageIndex{1}\) tells that the empty function \(\mathbb{N}_{<0} \to \varnothing\) is indeed a bijection.