Bijections and Finite Sets: Proof by If And Only If

Here's a proof that requires a bit of subtlety...

Prove that a nonempty set $T_{1}$ is finite if and only if there is a bijection from  $T_{1}$ onto a finite set  $T_{2}$.

We can use the following:

• Definition     (a)  The empty set is said to have zero elements.
• (b)  If $n\in \mathbb{N}$,  a set S is said to have n elements if there exists a bijection from the set         $\mathbb{N}_{n}$ := {1, 2, ..., n} onto S.
• (c)  A set S is said to be finite if it is either empty or has n elements for some $n\in \mathbb{N}$.
• (d) A set S is said to be infinite if it is not finite.

Step 1: If
Assume there is a bijection from $T_{1}$ onto $T_{2}$. We're given that $T_{2}$ is finite. We know that by definition, every element of one set is paired with exactly one element of the other set, and every element of the other set is paired with exactly one element of the first set ($T_{1}$). Since $T_{2}$ is finite, $T_{1}$ is finite.

Step 2: Only If
Assume $T_{1}$ is finite set, which is nonempty as described in the original problem statement. This means that by the definition above, $T_{1}$ has n elements for some $n\in \mathbb{N}$ and there exists a bijection from the set $\mathbb{N}_{n}$ := {1, 2, ..., n} onto $T_{1}$. Let's call that bijection f.

We also are given that $T_{2}$ is a finite set. Assuming that $T_{2}$ is not empty, we know by the definition above that there exists a bijection from the set $\mathbb{N}_{n}$ := {1, 2, ..., n} onto $T_{2}$. Let's call that bijection g.

The composition $g\circ f$ would map $T_{1}$ into $T_{2}$, and since the composition of two bijections is a bijection, $g\circ f$ is a bijection from $T_{1}$ onto $T_{2}$.

QED 

Exponents and Factorials: Mathematical Induction Proof

Easy one here...

Prove that $2^{n}< n!$ for all $n\geq 4$, $n\in \mathbb{N}$.

Step 1: Show P(4) is true.
Our base case is k = 4. $2^{4}<4!$ $\Rightarrow 16 < 24$. OK.

Step 2: Show that (if we assume P(k) is true), P(k+1) is true. (Induction hypothesis). This means we should have $2^{k+1}<(k+1)!$.

$$2^{k+1}<(k+1)!$$
can be rewritten as
$$2\cdot2^{k}<(k+1) k!$$

For $k\geq 4$, 2 < k + 1, and by the induction hypothesis, we assume $2^{k}< k!$, so we can see that
$$2^{n}< n!$$
for all $n\geq 4$, $n\in \mathbb{N}$

QED