Proposition B.7.
If \(X\) be a non-empty finite set, then there is a unique positive integer \(n\) for which there is a bijection \(f:[n]\bijection X\text{.}\)
Section B.5 Finite 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.
Proposition B.8.
The set \(P\) of primes is infinite.
Proof.
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.
Conjecture B.9.
It is conjectured that the following set is infinite:
\begin{equation*}
T=\{n\in\posints:n \text{ and } n+2 \text{ are both
primes } \}.
\end{equation*}
This conjecture is known as the Twin Primes Conjecture. Guaranteed \(\text{A} ++\) for any student who can settle it!
Proposition B.10.
Let \(X\) and \(Y\) be finite sets. If there exists an injection \(f:X\injection Y\) and an injection \(g:Y \injection X\text{,}\) then there exists a bijection \(h:X \bijection Y\text{.}\)
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{.}\)
Proposition B.11.
If \(X\) and \(Y\) are finite non-empty sets, then \(|X\times Y| =|X|\times |Y|\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*}
Theorem B.12.
- There is a bijection between any two of the following infinite sets \(\posints\text{,}\) \(\ints\) and \(\rats\text{.}\)
- There is an injection from \(\rats\) to \(\reals\text{.}\)
- There is no surjection from \(\rats\) to \(\reals\text{.}\)
