So I want to prove that for natural numbers $m,n,k$, if $k$ is no $0$ or $1$, and if $m Let
$$
K=\{k\in\omega\ |\ k^m Since $m All in all, this approach seems very ugly. Is there a way to clean it up? I wanted to use the time tested method of induction, but assuming $k^m
If $m
3 Answers
I think for natural numbers since $k\ge 1$, $k^{n-m}$ should be greater than 1. Then it should be automatic.
-
3I'm working in the early stages of constructing that naturals with set theory, so I'm afraid that approach doesn't work. – 2011-03-14
-
0You mean $k>1$, as $1^x=1$ for any number $x$. – 2011-03-14
I assume you have something like $k^0 = 1$, $ k^a \cdot k = k^{a^+}$, if $0
First you want to show that $0 < k^m$. You have the initial step $0 < 1 = k^0$ (adjust this if instead you have $k^1 = k$) and the inductive step $0 < k^m < k^m \cdot k = k^{m^+}$. Then for the main hypothesis you have the initial step $k^m < k^m \cdot k = k^{m^+}$ and the inductive step $k^m < k^n < k^n \cdot k = k^{n^+}$ for $m
-
0Thanks Henry, I'm a little confused by which variable to induct on. Do I induct on $m$ and then $n$, and leave $k$ fixed? I guess my original approach treated $m$ and $n$ as fixed, and inducted on $k$. – 2011-03-14
-
0I am sure it is easier to vary $m$ and then $n$ while leaving $k$ fixed, and I think you did so in your version. It is difficult to compare $k^a$ and $(k+1)^b$ until you have a lot more tools, such as binomial expansion or logarithms. – 2011-03-14
The idea is to show that for $k\geq2$ we have $k^{m^+}>k^m$. For that you need to show that $m\cdot k>m$ for $k\geq2$ and $m\geq1$. And to show that you need to show that $m+n>m$ for $n\geq1$.
Let's start with the last one, $m+n>m$ for $n\geq1$: We work with induction on $n$. For $n=1$ $m+n=m+1=m^+$. By the definition of the natural numbers you have $m\in m^+$ so it's true. Now assume that it's true for $n$. For $n^+$ we have $m+n^+=(m+n)^+$. Now $(m+n)<(m+n)^+$. By the induction hypothesis we have $m Now let's show that $m\cdot k>m$ for $k\geq2$ and $m\geq1$ : We work with induction on $k$. For $k=2$ we have $m\cdot2=m\cdot1+m=m+m$. From the previous result (and since $m\geq1$) we have $m+m>m$ and thus $m\cdot2>m$. Assume that it's true for $k$. We have $m\cdot k^+=m\cdot k+m$. By the previous result $m\cdot k+m>m\cdot k$, By the induction hypothesis we have $m\cdot k>m$. Therefore $m\cdot k^+=m\cdot k+m>m\cdot k>m$ and we are done. We can now show that $k\geq2$ we have $k^{m^+}>k^m$: We have $k^{m^+}=k^m\cdot k$. Since $k\geq2$ from the previous result we get $k^m\cdot k>k^m$ which is what we want. Finalizing the proof let's show what you want by induction on $n$. If $n=0$ then the sentence is vacuously true. Assume that it's true for $n$. If $m
-
0Thanks Apostolos for spelling it out for me. I'm not too comfortable yet on choosing what to induct on when there are multiple variables. – 2011-03-14
-
0@Bdubs: A *usually* (as in not always) helpful advice is to first try induction on the variables that appear at the rightmost of terms and after the $<$. This is because of the way arithmetic operations and the $<$ relation are defined. For example my reasoning here was to first perform induction on $n$. By trying that I figured out that the problem was reduced to showing $m
$k$ etc. – 2011-03-14