1. ## induction help please

Let Nk= {1,2,…,k} be a finite set with k elements. This problems shows that if n, r elements of N with n > r, then there is no one-to-one function from Nn to Nr. We prove this by induction on n ≥ 2 for the following statement.
(Pn): For all r with 1 ≤ r < n, there is no one-to-one function from Nn to Nr.
a. The first step covers the general case when r=1 and any n>r.
Prove that if n > r=1, then there is no one-to-one function from Nn to Nr.
b. Show that the base case (P2) is true.
c. Assume the induction hypothesis (Pn) is true and prove that (Pn+1) is true.
Hint: If r ≥ 2 and f: Nn+1 to Nr were one-to-one, then the restriction of f to Nn into Nr \ {f(n+1)} would be one-to-one. You may also use the fact that there is a bijection from Nr \{f(n+1)} to Nr-1.
d. Conclude that (Pn) is true for all n≥ 2.
e. Prove that if n,r is an element of N with n not = r, then Nn does not have the same cardinality as Nr.

2. This is fairly easy, as you are lead by the hand through the proof:

(Pn): For all r with 1 ≤ r < n, there is no one-to-one function from Nn to Nr.

Let Nk= {1,2,…,k} be a finite set with k elements. This problems shows that if n, r elements of N with n > r, then there is no one-to-one function from Nn to Nr. We prove this by induction on n = 2 for the following statement.
(Pn): For all r with 1 = r < n, there is no one-to-one function from Nn to Nr.

a. The first step covers the general case when r=1 and any n>r.
Prove that if n > r=1, then there is no one-to-one function from Nn to Nr.
We will take:

(Pn): For all $n$ and $r$ in $\mathbb{N}$ with $1 \leq r < n$, there is no one-to-one function
from $N_n$ to $N_r$.

Suppose there is a one-to-one function $f_{n,r}$ from $N_n$ to $N_r$ where $r=1$ and $n>r$.
Then $1$ belongs to $N_n$ as does $2$. Then by definition of a one-to-one function $f_{n,r}(1) \neq f_{n,r}(2)$,
but $f_{n,r}(1) = 1$, as does $f_{n,r}(2)$ as this is the only element in $N_r$, a contradiction, so there can be no
such function.

b. Show that the base case (P2) is true.
Part a shows that for all $n>1$, there is no one-to-one function between
$N_n$ and $N_1$. Let $n=2$ and this is a proof that $P(2)$ is true.

c. Assume the induction hypothesis (Pn) is true and prove that (Pn+1) is true.
Hint: If r = 2 and f: Nn+1 to Nr were one-to-one, then the restriction of f to Nn into Nr \ {f(n+1)} would be one-to-one. You may also use the fact that there is a bijection from Nr \{f(n+1)} to Nr-1.
Suppose that for some $n \geq 2$ P(n) is true and that P(n+1) is false.
Let $f_{n+1,r}$ be a one-to-one function between $N_{n+1}$ and $N_r, r, which
exists by supposition. Then the restriction of $f_{n+1,r}$ to $N_n$ is a one-to-one
function from $N_n$ to $N_r$, but this contradict the supposition that P(n) is true.
Hence if P(n) is true so is P(n+1).

d. Conclude that (Pn) is true for all n= 2.
By b P(2) is true, by c if P(n) is true so is P(n+1), hence
by the principle of induction P(n) is true for all $n \geq 2$.

e. Prove that if n,r is an element of N with n not = r, then Nn does not have the same cardinality as Nr.
Two sets $A$ and $B$ have the same cardinality if there exits a one-to-one
function from $A$ to $B$ and a one-to-one function from $B$ to $A$.

If $n \neq r$ without loss of generality we may assume $n>r$,
and so there is no one-to-one function from $N_n$ to $N_r$
and so they do not have the same cardinality.

(We may assume $n>r$ because either $n>r$ or
$r>n$, and in the latter case the same argument goes through
but with $n$ and $r$ interchanged.)

RonL