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)

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)

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)

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.