Fact 12.1.1. Uniqueness of counting number.
For finite set \(A\) there exists one unique natural number \(m\) for which a bijection \(\natnumlt{m} \to A\) exists.
Section 12.1 Finite sets
Recall.
For \(m\in\N\) we have defined the counting set
\begin{equation*}
\natnumlt{m} = \setdef{n \in \N}{n \lt m} = \{ 0, \, 1, \, \dotsc, \, m-1\} \text{.}
\end{equation*}
Clearly, \(\natnumlt{m}\) contains exactly \(m\) elements. In fact, we have defined the number \(m\) to be the set \(\natnumlt{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 \(\natnumlt{m}\text{,}\) one for one, then \(A\) must also contain exactly \(m\) elements.
- finite set
- a set \(A\) for which there exists a bijection \(\natnumlt{m} \to A\) for some \(m \in \N\text{,}\) \(m \gt 0\)
Remark 12.1.2.
Suppose \(A\) is finite. While there is only one number \(m\) for which a bijection \(\natnumlt{m} \to A\) exists, there can be many such bijections, and the number of bijections increases as \(m\) increases.
Checkpoint 12.1.3.
Prove Fact 12.1.1.
- cardinality (of a finite set \(A\))
- the unique natural number \(m\) for which a bijection \(\natnumlt{m} \to A\) exists
- \(\card{A}\)
- the cardinality of the finite set \(A\)
- \(\cardop A\)
- alternative notation for the cardinality of the finite set \(A\)
- \(\ncardop\{\dots\}\)
- alternative notation for the cardinality of the set defined by \(\{\dots\}\)
Example 12.1.4.
For \(\Sigma = \ShortEngAlphabet\text{,}\) we have \(\card{\Sigma} = 26\text{.}\) Below are two example bijections \(\funcdef{\varphi,\psi}{\natnumlt{26}}{\Sigma}\) that verify this cardinality number.
| \(\sigma\) | \(0\) | \(1\) | \(2\) | \(3\) | \(\cdots\) | \(24\) | \(25\) |
| \(\varphi(\sigma)\) | \(\mathrm{a}\) | \(\mathrm{b}\) | \(\mathrm{c}\) | \(\mathrm{d}\) | \(\cdots\) | \(\mathrm{y}\) | \(\mathrm{z}\) |
| \(\psi(\sigma)\) | \(\mathrm{a}\) | \(\mathrm{z}\) | \(\mathrm{b}\) | \(\mathrm{y}\) | \(\cdots\) | \(\mathrm{m}\) | \(\mathrm{n}\) |
Cardinality of an empty set.
What about the empty set? Clearly we should have \(\card{\emptyset} = 0\text{.}\) But is this consistent with our definition of cardinality?
- empty function
- a function with domain \(\emptyset\)
If we accept the existence of an empty function \(\emptyset \to X\) for every set \(X\text{,}\) then the properties of such functions that we need in order to establish \(\card{\emptyset} = 0\) will be vacuously true.
Proposition 12.1.6. Properties of empty functions.
- For every set \(X\text{,}\) an empty function \(\emptyset \to X\) is injective.
- An empty function \(\emptyset \to \emptyset\) is a bijection.
Proof.
You were asked to verify these statements in Exercise 10.7.12.
Corollary 12.1.7.
The cardinality of the empty set is \(0\text{.}\)
Proof.
We are required to demonstrate an example of a bijection \(\natnumlt{0} \to \emptyset\text{.}\) But
\begin{equation*}
\natnumlt{0} = \setdef{n \in \N}{n \lt 0} = \emptyset \text{,}
\end{equation*}
so Statement 2 of Proposition 12.1.6 tells that the empty function \(\natnumlt{0} \to \emptyset\) is indeed a bijection.
