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

Composition Of Two Bijections Is a Bijection: Proof

A common exercise from an "Introduction To Real Analysis" course is to show that

1. if $f: A\rightarrow B$ is a bijection, and
2. if $g: B\rightarrow C$ is a bijection

then the composite $g\circ f$ is a bijective map of A onto C.

We just need to show that $g\circ f: A\rightarrow C$ is one to one and onto.

$$g\circ f = g(f(x))$$
$$f(x)=y     (y\in B)$$
$$g(y)=z    (z\in C)$$

First, show the composite is injective (one to one):
by 1, we know that $f(x_{1})=f(x_{2})$ means $x_{1}=x_{2}$ (f is one to one - injective).
by 2, we know that $g(f(x_{1}))=g(f(x_{2}))$ means $f(x_{1})=f(x_{2})$ (g is one to one - injective).

a) So, we see that $g(f(x_{1}))=g(f(x_{2}))$ means that  $x_{1}=x_{2}$, which means that $g\circ f$ is       an injective (one to one) map of A onto C.

Second, show the composite is surjective (onto):
by 1, we know that for any $b\in B$ there exists at least one $x\in A$ such that $f(x)=b$.
by 2, we know that for any $c\in C$ there exists at least one $b\in B$ such that $g(b)=c$.

b) So, we see that for any$c\in C$ there exists at least one  $x\in A$ such that $g(f(x))=c$, which means that    $g\circ f$ is a surjective (onto) map of A onto C.

With the results a) and b) we see that the composite $g\circ f$ is indeed a bijective map of A onto C.

QED