2
$\begingroup$

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 $m1$. 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 $11$. If $p^+=1$, we are done. So suppose $k^{p^+}>1$. Then since $11$ for all $p$, since $p^+\neq 0$. Then from $1

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

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.

  • 3
    I'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
  • 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

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
    Thanks 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
  • 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

  • 0
    Thanks 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