** Next:** Elementary combinatorics
** Up:** Countability
** Previous:** Countability
** Contents**

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:

- is an injection:
- If
, then
, thus
; in particular
.
- If
, then
and
. As
, we have
.
- If
, then
and
. As
,
and from the injectivity of it follows that
.

- is a surjection:
- If , then there exists a
,
such that
.
- 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.

*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