# Applied Combinatorics

## 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*}