2
$\begingroup$

So I want to prove that for natural numbers $m,n,k$, if $k$ is no $0$ or $1$, and if $m, then $k^m. I jotted down the following proof, but I'm not sure how acceptable it is. I only have use of basic set theoretic properties of the naturals with addition, multiplication, and powers. I also have use of cancellation.

Let $ K=\{k\in\omega\ |\ k^m

Since $m there exists a $p^+\in\omega$ such that $m+p^+=n$. Consider $2$. I claim $2^{p^+}>1$. Now $p^+\neq 0$, since $0$ is not in the range of the successor. If $p^+=1$, then from the work above, $2^1=2>1$. Suppose then that $2^{p^+}>1$. Then $2^{p^{++}}=2^{p^+}\cdot 2>1$. This follows by transitivity since $1<2^{p^+}$, and $1<2$ implies $2^{p^+}\cdot 1<2^{p^+}\cdot 2$, that is $2^{p^+}<2^{p^{++}}$. Then from $1<2^{p^+}$ we have $2^m=2^m\cdot 1<2^m\cdot 2^{p^+}=2^{m+p^+}=2^n$, so $2\in K$. By the same reasoning we can show that any $k\neq 0,1$ is in $K$. If $k\neq 0,1$, then $1. Again, I claim $k^{p^+}>1$. If $p^+=1$, we are done. So suppose $k^{p^+}>1$. Then since $1, we have $k^{p^+}=k^{p^+}\cdot 1, so $1 by transitivity, and so $k^{p^+}>1$ for all $p$, since $p^+\neq 0$. Then from $1 we have $k^m\cdot 1, so $k\in K$, and the result follows.

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 seems to have little to do with showing $(k^+)^m<(k^+)^n$, since I don't know how to distribute powers. Thanks for any constructive criticism.

3 Answers 3

0

I think for natural numbers since $k\ge 1$, $k^{n-m}$ should be greater than 1. Then it should be automatic.

  • 0
    You mean k>1, as $1^x=1$ for any number $x$.2011-03-14
1

I assume you have something like $k^0 = 1$, $ k^a \cdot k = k^{a^+}$, if $0 and $1 then $a < a \cdot b$, and the typical properties of order such as if $a and $b then $a and if $a and $b=c$ then $a. In this case you also have $0 < 1 < k$.

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.

  • 0
    I 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
1

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 then we have $m or $m=n$. Previously I showed that $k^n. In case $m=n$ that suffices. In case $m by the induction hypothesis we have $k^m. But $k^n and we are done.

  • 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. $F$or 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, so I used induction on $k$ etc.2011-03-14