next up previous contents
Next: Elementary combinatorics Up: Countability Previous: Countability   Contents

Finite sets

Definition 7.1.1   A set $ E$ is finite if it verifies one of the following conditions:
(i)
$ E= \emptyset$; in this case, $ E$ is a said to be of cardinality 0, and we write $ \vert E\vert=0$.
(ii)
There exists a natural number $ n$ and a bijection $ \phi: \; \{1,
\dots , n \} \longrightarrow E$; in this case $ E$ is said to be of cardinality $ n$ and we write $ \vert E\vert=n$.

For example, $ E=\{ a,b,c,d \}$ is a finite set such that $ \vert E\vert=4$; we define a bijection $ \phi: \{ 1, \dots, 4 \} \longrightarrow E$ as follows:

$\displaystyle \begin{matrix}
 1 \mapsto a \\  
 2 \mapsto b \\  
 3 \mapsto c \\  
 4 \mapsto d
 \end{matrix}$    

For a non empty set, the bijection $ \phi$ counts the number of elements in the set.

Proposition 7.1.2   Let $ E$ be a finite set. If $ A$ is a subset of $ E$, then $ A$ is a finite set and $ \vert A\vert \leq \vert E\vert$.

Proof. If $ E= \emptyset$, then the unique possibility is $ A=\emptyset$ and the proposition is trivial. If $ E \neq \emptyset$ and $ A=\emptyset$, the result is trivial too. Let us assume that $ A \neq \emptyset$ (thus automatically $ E \neq \emptyset$). Let $ n=\vert E\vert$ and let $ \phi$ be the bijection of Definition 1.1. Then: $ \qedsymbol$

Proposition 7.1.3   Let $ A$ and $ B$ be two finite sets. If $ A \cap B = \emptyset$, then $ A \cup B$ is a finite set and $ \vert A \cup B\vert=\vert A\vert+\vert B\vert$.

Proof. If at least one of the sets $ A$ and $ B$ is empty, the result is trivial. Suppose that none of them is empty; we denote $ p=\vert A\vert$ and $ q=\vert B\vert$; bijections as announced in Definition 1.1 will be denoted respectively $ \phi_A : \; \{1,2, \dots ,p \} \longrightarrow A$ and $ \phi_B: \; \{1,2, \dots ,q \} \longrightarrow B$. Now we define a mapping $ \psi: \{1,2, \dots ,p+q \} \longrightarrow A \cup B$ as follows:

\begin{displaymath}\begin{cases}
 \text{For } 0 \leq k \leq p, \; \psi (k)= \phi...
...} p+1 \leq k \leq p+q, \; \psi (k) = \phi_B (k-p).
 \end{cases}\end{displaymath}    

The mapping $ \psi$ is a bijection:
  1. $ \psi$ is an injection:
    1. If $ 0 \leq k_1 < k_2 \leq p$, then $ \phi_A (k_1) < \phi_A
(k_2)$, thus $ \psi (k_1) < \psi (k_2)$; in particular $ \psi (k_1) \neq
\psi (k_2)$.
    2. If $ 0 \leq k_1 \leq p < k_2 \leq p+q$, then $ \psi (k_1) \in
A$ and $ \psi (k_2) \in B$. As $ A \cap B = \emptyset$, we have $ \psi (k_1) \neq
\psi (k_2)$.
    3. If $ p+1 \leq k_1 < k_2 \leq p+q$, then $ \psi (k_1)=\phi_B
(k_1-p)$ and $ \psi (k_2)=\phi_B (k_2-p)$. As $ k_1 \neq k_2$, $ k_1-p
\neq k_2-p$ and from the injectivity of $ \phi_B$ it follows that $ \psi (k_1) \neq
\psi (k_2)$.
  2. $ \psi$ is a surjection:
    1. If $ x \in A$, then there exists a $ k \in \{ 1, \dots, p \}$, such that $ \psi (k)=\phi_A (k)=x$.
    2. If $ x \in B$, there exists a $ k \in \{ 1, \dots , q \}$ such that $ \phi_B (k)=x$, therefore $ \psi(q+k) = x$.
$ \qedsymbol$

Corollary 7.1.4   Let $ A$ and $ B$ be any two finite sets. Then $ A \cup B$ is a finite set and the following equation holds:

$\displaystyle \vert A \cup B\vert=\vert A\vert+\vert B\vert-\vert A \cap B\vert.$    

When counting the elements of $ A$ then the elements of $ B$, we count twice the elements of the intersection; therefore we need to substract $ A \cap B$. We leave to the reader the task of writing a rigorous proof.

Proposition 7.1.5   Let $ E$ be a finite set such that $ \lvert E\rvert =n$. Then $ \lvert\mathcal{P}(E)\rvert =2^n$.

Proof. We prove the proposition by induction on $ n$. If $ n=0$, then $ E= \emptyset$ and $ \mathcal{P}(\emptyset)= \{ \emptyset \}$, thus $ \lvert E\rvert =0 \Rightarrow
\lvert\mathcal{P}(E)\rvert =1=2^0$. Suppose that the required property is true for some non zero natural number. Now let $ E$ be a set such that $ \lvert E\rvert =n+1$. Choose an element $ a$ in $ E$. The subsets of $ E$ can be dispatched into two classes: the class of subsets of $ E$ to whom $ a$ belongs and the class of subsets of $ E$ to whom $ a$ does not belong. On the one hand, a subset of $ E$ which does not contain $ a$ is completely determined by a subset of $ E \setminus \{ a \}$; as $ \lvert E
\setminus \{ a \}\rvert =n$, the induction hypothesis apply and there are $ 2^n$ such subsets. On the other hand, a subset of $ E$ which contains $ a$ is also determined by a subset of $ E \setminus \{ a \}$ (it is equal to the union of the one-element set $ \{ a \}$ and a subset of $ E \setminus \{ a \}$ ). Here too there are $ 2^n$ such subsets, by the induction hypothesis. Finally, the number of subsets of $ E$ is equal to $ 2^n+2^n=2 \cdot 2^n
= 2^{n+1}$. $ \qedsymbol$

We will see later another proof of Proposition 1.5.

Example 7.1.6   In some country the currency is named the ``selah''; it is divided into 100 cents. A child has a wallet containing the following coins: one-half, one cent, 2 cents, 5 cents, 10 cents, 20 cents, 50 cents, one selah, two selahs and five selahs (exactly one of each). How many different sums can he pay without need to get change? The wallet contains 10 different coins. Each sum is determined by a subset of the set of coins in the wallet. There are $ 2^10=1024$ subsets, but one is empty, thus corresponds to no payment. The answer is 1023.


next up previous contents
Next: Elementary combinatorics Up: Countability Previous: Countability   Contents
root 2002-06-10