# Thread: Proof By Induction help!

1. ## Proof By Induction help!

I don't know where to start or how to do this proof. Can someone please help me?

Prove by induction on n that if r < n and f:N(r)--> N(n), then f is not onto N(n). (Where N is the natural numbers)

Thank you for your help!

2. Originally Posted by calcprincess88
I don't know where to start or how to do this proof. Can someone please help me?

Prove by induction on n that if r < n and f:N(r)--> N(n), then F is not onto N(n). (Where N is the natural numbers)

Thank you for your help!
The inductive step is true trivially by the falsity of the conditional. (you take the natural numbers to be 1,2,3,... or do you include 0? I have to ask these days. It doesn't make a difference in the inductive step though)

to continue, i need to know how you define something like N(n)

3. I don't understand what you mean.

4. Originally Posted by calcprincess88
I don't understand what you mean.
you have an if-then statement here. that is, an implication.

so you want to prove $P \implies Q$ for all $n \in \mathbb{N}$

where $P$ is the statement " $r < n$ and $f : \mathbb{N}(r) \mapsto \mathbb{N}(n)$" where $r \in \mathbb{N}$

and the statement $Q$ is " $f$ is not onto $\mathbb{N}(n)$"

Now, if the statement $P$ is false, then the implication $P \implies Q$ is always true.

The thing is, $P$ is false for the inductive step. since if we take $n = 1$ (which i am assuming is the first natural number by your definition), then there is no $r \in \mathbb{N}$ such that $r < n$. Thus the $r < n$ part of the first statement is false, which ends up making the whole statement true. thus, the inductive step holds.

Now i need to know how you define $\mathbb{N}(n)$ for some $n \in \mathbb{N}$

5. Ok. So i get what you are saying about the first part. But I still dont get what you are asking when you say to "define for some ." I think n is either a natural number or an integer. I'm not sure.

Thank you for your help so far!

6. Originally Posted by calcprincess88
Ok. So i get what you are saying about the first part. But I still dont get what you are asking when you say to "define for some ." I think n is either a natural number or an integer. I'm not sure.

Thank you for your help so far!
I'm just asking what do you mean when you write N(n). I am unfamiliar with the notation. i want to know what it implies. so that i can know how to continue

7. Originally Posted by calcprincess88
I don't know where to start or how to do this proof. Can someone please help me?

Prove by induction on n that if r < n and f:N(r)--> N(n), then f is not onto N(n). (Where N is the natural numbers)

Thank you for your help!
Induction Hypothesis: P(n):=" if r < n and f:N(r)--> N(n), then f is not onto N(n)"

Claim: P(n+1):=" if r < n+1 and f:N(r)--> N(n+1), then f is not onto N(n+1)"

There are two cases to consider:
1) $\forall i \in N(r), f(i) \neq n+1$

2) $\exists i \in N(r), f(i) = n+1$

Case 1:
$\forall i \in N(r), f(i) \neq n+1$
Trivially not onto.

Case 2:
$\exists i \in N(r), f(i) = n+1$
Define a function g:N(r) --> N(n), such that
$\forall i \in N(r)[\text{ with }f(i)\neq n+1], g(i)=f(i)$.
$\forall i \in N(r)[\text{ with }f(i)=n+1], g(i)=n$.
By Induction Hypothesis on g, there exists a $m \in N(n)$, such that $\forall i \in N(r), g(i) \neq m$. But then g(i) = f(i). So the conclusion follows.

Afterthought: I think this proof is not completely right. You can proceed in a similar manner. You have to take care of a small detail in case 2. Anyway can you spot the mistake?

8. Originally Posted by Jhevon
I'm just asking what do you mean when you write N(n). I am unfamiliar with the notation. i want to know what it implies. so that i can know how to continue
I think she means:
$N(n) = \{i \in \mathbb{N}: i \leq n\}$

9. Originally Posted by Isomorphism
I think she means:
$N(n) = \{i \in \mathbb{N}: i \leq n\}$
I thought so (though i probably would have used <, i don't know why, it's probably stupid), but I wasn't sure. I didn't want to go ahead and do something and make a fool out of myself...again...i've already done it a dozen times this week. People are going to start to wonder why i'm a helper.