Skip to main content

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 \ge 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.
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} \)
Figure 12.1.5. Bijections \(\funcdef{\varphi,\psi}{\natnumlt{26}}{\Sigma} \) defined by a table of values.

Cardinality of an empty set.

What about an empty set? Clearly we should have \(\card{\emptyset} = 0 \text{,}\) but is this consistent with our definition of cardinality? By definition, to verify \(\card{\emptyset} = 0 \) we require a bijection \(\natnumlt{0} \to \emptyset \text{,}\) but
\begin{equation*} \natnumlt{0} = \setdef{n \in \N}{n \lt 0} = \emptyset \end{equation*}
as well.
empty function
a function with domain \(\emptyset \)
Do empty functions even exist? It is difficult to think of such a function in terms of an input-output rule, but remember that technically a function is defined by its graph. (See the formal definition of function in Subsection 10.1.3.) Since \(\emptyset \cartprod X = \emptyset \) for every set \(X \text{,}\) there exists a unique function \(\emptyset \to X \text{,}\) namely the function whose graph is \(\emptyset \text{.}\) And because of the empty nature of this graph, the facts required to establish \(\card{\emptyset} = 0 \) will be vacuously true.

Remark 12.1.6. Empty codomain.

While functions with empty domain exist, note that it is not possible to have a function with empty codomain, except in the case that the domain is empty as well.

Proof.

We are required to demonstrate an example of a bijection \(\natnumlt{0} \to \emptyset \text{.}\) As \(\natnumlt{0} = \emptyset \text{,}\) Statement 2 of Proposition 12.1.7 tells that the empty function \(\natnumlt{0} \to \emptyset \) is the required bijection.
PrevTopNext