Exercises B.1-6

The 0-tuple is represented by ∅.
if x is an n-tuple, then (a, {a,x}) is an (n+1)-tuple

Exercises B.1-5

Because every element x in S has two choices (choose or not choose), the power set’s size is .

Exercises B.1-4

We can find a bijection function f from nature number to odd nature number.
Let

Exercises B.1-3

Let the set of union of all is S. We can prove the complement of S, by using |A| minus equation B.3. If x is in S’s complement, then x contributes 1 for this formula. If x is in k of subsets, then it contributes = 0. Hence the principle of inclusion and exclution is proved.

Proof by induction. 

Exercises B.1-2

Let
If then for some i, then .
If then for some i, then

Let
If then for all i, then .
If then for all i, then

Exercises B.1-1