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!
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)
you have an if-then statement here. that is, an implication.
so you want to prove $\displaystyle P \implies Q$ for all $\displaystyle n \in \mathbb{N}$
where $\displaystyle P$ is the statement "$\displaystyle r < n$ and $\displaystyle f : \mathbb{N}(r) \mapsto \mathbb{N}(n)$" where $\displaystyle r \in \mathbb{N}$
and the statement $\displaystyle Q$ is "$\displaystyle f$ is not onto $\displaystyle \mathbb{N}(n)$"
Now, if the statement $\displaystyle P$ is false, then the implication $\displaystyle P \implies Q$ is always true.
The thing is, $\displaystyle P$ is false for the inductive step. since if we take $\displaystyle n = 1$ (which i am assuming is the first natural number by your definition), then there is no $\displaystyle r \in \mathbb{N}$ such that $\displaystyle r < n$. Thus the $\displaystyle 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 $\displaystyle \mathbb{N}(n)$ for some $\displaystyle n \in \mathbb{N}$
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)$\displaystyle \forall i \in N(r), f(i) \neq n+1$
2)$\displaystyle \exists i \in N(r), f(i) = n+1$
Case 1:
$\displaystyle \forall i \in N(r), f(i) \neq n+1$
Trivially not onto.
Case 2:
$\displaystyle \exists i \in N(r), f(i) = n+1$
Define a function g:N(r) --> N(n), such that
$\displaystyle \forall i \in N(r)[\text{ with }f(i)\neq n+1], g(i)=f(i) $.
$\displaystyle \forall i \in N(r)[\text{ with }f(i)=n+1], g(i)=n $.
By Induction Hypothesis on g, there exists a $\displaystyle m \in N(n)$, such that $\displaystyle \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?
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.