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

We will take:(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.

(Pn): For all and in with , there is no one-to-one function

from to .

Suppose there is a one-to-one function from to where and .

Then belongs to as does . Then by definition of a one-to-one function ,

but , as does as this is the only element in , a contradiction, so there can be no

such function.

Part a shows that for all , there is no one-to-one function betweenb. Show that the base case (P2) is true.

and . Let and this is a proof that is true.

Suppose that for some P(n) is true and that P(n+1) is false.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.

Let be a one-to-one function between and , which

exists by supposition. Then the restriction of to is a one-to-one

function from to , but this contradict the supposition that P(n) is true.

Hence if P(n) is true so is P(n+1).

By b P(2) is true, by c if P(n) is true so is P(n+1), henced. Conclude that (Pn) is true for all n= 2.

by the principle of induction P(n) is true for all .

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

function from to and a one-to-one function from to .

If without loss of generality we may assume ,

and so there is no one-to-one function from to

and so they do not have the same cardinality.

(We may assume because either or

, and in the latter case the same argument goes through

but with and interchanged.)

RonL