## SectionB.5Finite Sets

A set $X$ is said to be finite when either (1) $X=\emptyset\text{;}$ or (2) there exists positive integer $n$ and a bijection $f:[n]\bijection X\text{.}$ When $X$ is not finite, it is called infinite. For example, $\{a,\emptyset,(3,2),\posints\}$ is a finite set as is $\posints\times\emptyset\text{.}$ On the other hand, $\posints\times \{\emptyset\}$ is infinite. Of course, $[n]$ and $\bfn$ are finite sets for every $n\in\posints\text{.}$

In some cases, it may take some effort to determine whether a set is finite or infinite. Here is a truly classic result.

Suppose that the set $P$ of primes is finite. It is non-empty since $2\in P\text{.}$ Let $n$ be the unique positive integer for which there exists a bijection $f:[n]\rightarrow P\text{.}$ Then let

\begin{equation*} p=1+f(1)\times f(2)\times f(3)\times \dots\times f(n) \end{equation*}

Then $p$ is not divisible by any of the primes in $P$ but is larger than any element of $P\text{.}$ Thus, either $p$ is prime or there is a prime that does not belong to $P\text{.}$ The contradiction completes the proof.

Here's a famous example of a set where no one knows if the set is finite or not.

This conjecture is known as the Twin Primes Conjecture. Guaranteed $\text{A} ++$ for any student who can settle it!

When $X$ is a finite non-empty set, the cardinality of $X\text{,}$ denoted $|X|$ is the unique positive integer $n$ for which there is a bijection $f:[n]\bijection X\text{.}$ Intuitively, $|X|$ is the number of elements in $X\text{.}$ For example,

\begin{equation*} |\{(6,2), (8,(4,\emptyset)), \{3,\{5\}\}\}|=3. \end{equation*}

By convention, the cardinality of the empty set is taken to be zero, and we write $|\emptyset|=0\text{.}$

We note that the statement in Proposition B.11 is an example of “operator overloading”, a technique featured in several programming languages. Specifically, the times sign $\times$ is used twice but has different meanings. As part of $X\times Y\text{,}$ it denotes the cartesian product, while as part of $|X|\times |Y|\text{,}$ it means ordinary multiplication of positive integers. Programming languages can keep track of the data types of variables and apply the correct interpretation of an operator like $\times$ depending on the variables to which it is applied.

We also have the following general form of Proposition B.11:

\begin{equation*} |X_1\times X_2\times\dots\times X_n|= |X_1|\times |X_2|\times\dots\times |X_n| \end{equation*}