Counting

We define .

Let be a set. If there exists a bijection between and , we say that has size or cardinality , and write .

Let . If there exists an injection from to , then .

Proof:
We use InductionInduction on . If the result is clear. Now suppose is an injection. Firstly, we know , so for some . We can then define an injection :

• If for every , then let for every .
• If for some , let (we know because is injective), and let for every .
  Then, from our induction hypothesis, we get that , so .

The contrapositive of the theorem above is called the pidgeonhole principle and says that if then there does not exist a injection from to .

Let be a set with size and . Then .

Proof:
There exists bijections and . This means and are injections from to and to , respectively, meaning and , so .

Let be finite, nonempty, disjoint sets. Then Proof:
We have , and since we have meaning .

Let be finite, nonempty, disjoint sets. Then