Next: Elementary combinatorics Up: Countability Previous: Countability   Contents

# Finite sets

Definition 7.1.1   A set is finite if it verifies one of the following conditions:
(i)
; in this case, is a said to be of cardinality 0, and we write .
(ii)
There exists a natural number and a bijection ; in this case is said to be of cardinality and we write .

For example, is a finite set such that ; we define a bijection as follows:

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

Proposition 7.1.2   Let be a finite set. If is a subset of , then is a finite set and .

Proof. If , then the unique possibility is and the proposition is trivial. If and , the result is trivial too. Let us assume that (thus automatically ). Let and let be the bijection of Definition 1.1. Then:

Proposition 7.1.3   Let and be two finite sets. If , then is a finite set and .

Proof. If at least one of the sets and is empty, the result is trivial. Suppose that none of them is empty; we denote and ; bijections as announced in Definition 1.1 will be denoted respectively and . Now we define a mapping as follows:

The mapping is a bijection:
1. is an injection:
1. If , then , thus ; in particular .
2. If , then and . As , we have .
3. If , then and . As , and from the injectivity of it follows that .
2. is a surjection:
1. If , then there exists a , such that .
2. If , there exists a such that , therefore .

Corollary 7.1.4   Let and be any two finite sets. Then is a finite set and the following equation holds:

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

Proposition 7.1.5   Let be a finite set such that . Then .

Proof. We prove the proposition by induction on . If , then and , thus . Suppose that the required property is true for some non zero natural number. Now let be a set such that . Choose an element in . The subsets of can be dispatched into two classes: the class of subsets of to whom belongs and the class of subsets of to whom does not belong. On the one hand, a subset of which does not contain is completely determined by a subset of ; as , the induction hypothesis apply and there are such subsets. On the other hand, a subset of which contains is also determined by a subset of (it is equal to the union of the one-element set and a subset of ). Here too there are such subsets, by the induction hypothesis. Finally, the number of subsets of is equal to .

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 subsets, but one is empty, thus corresponds to no payment. The answer is 1023.

Next: Elementary combinatorics Up: Countability Previous: Countability   Contents
root 2002-06-10