Counting and Cardinality
1. Bijections
The mathematical notion of the “size” of a set is captured by the concept of a bijection, also known as a 1-1 correspondence. Any two sets whose elements can be put into 1-1 correspondence are considered to have the same size (formally, we say that they have the same cardinality.)
Definition
We say that a nonempty set \(X\) is finite when there exists \(N \in {\mathbb N}\) and a bijection \(\phi : X \rightarrow \{1,\ldots,N\}\). Otherwise we say that the set is infinite (i.e., not finite). If there exists a bijection \(\phi \ : \ X \rightarrow \mathbb{N}\), we say that \(X\) is countably infinite. A set is called countable when it's empty, finite, or countably infinite.
2. Cardinality of finite sets
Theorem
When \(X\) is a nonempty finite set, there is a unique \(N \in {\mathbb N}\) for which there exists a bijection \(\phi \ : \ X \rightarrow \{1,\ldots,N\}\). This \(N\) is called the cardinality of \(X\) and sometimes denoted \(\#X\).
Proof
3. Supremum and Infimum of Finite Sets
A key property of finite sets from the standpoint of analysis is that they must always contain their supremum and infimum:
Theorem
Given any nonempty finite set \(E \subset {\mathbb R}\), \(E\) must always be bounded above and below, and the supremum and infimum must be contained in \(E\). In this case, we simply call the supremum of \(E\) the maximum of \(E\) and call the infimum of \(E\) the minimum of \(E\).
Proof