1
$\begingroup$

In Terence Tao's Analyis Volume One. He presents that following Lemma. I would like to know if the argument presented below is correct? For your ease i have presented the relevant Peano's axiom as presented in Tao's Volume.

Axiom 2.4. Different natural numbers must have different successors; i.e., if $n, m$ are natural numbers and $n \neq m$, then $n++ \neq m++$. Equivalently, if $n++ = m++$, then we must have $n = m$.

Lemma $2.2.10$. Let $a$ be a positive number. Then there exists exactly one natural number $b$ such that $b\text{++} =a$.

Prior to proceeding with the argument let us first reformulate the statement of Lemma $\textbf{2.2.10}$ to say that. Given any natural number $a$ if $a$ is positive then there exists a unique natural number $b$ such that $b\text{++} = a$.

Proof. We construct the proof by recourse to mathematical Induction on $a$. For $a = 0$ the statement in question is vacuously true since $a$ is $0$ and therefore not positive.

Now assume that the claim in question is true for an arbitrary natural number $k$. Consider first the case where $k=0$. then choosing $b = 0$ would imply that $b\text{++}= 1$ as required. In addition if $\alpha\text{++}= 1$ for some arbitrary natural number $\alpha$ then axiom $\textbf{2.4}$ would imply $\alpha = b$ demonstrating the uniqueness of $b$.

Now consider the case where $k$ is positive. Since $k$ is positive using the inductive hypothesis we may choose a unique $\beta$ such that $\beta\text{++} = k$. Now assume that $k++$ is positive and choose $b = k$ evidently $b++ = k++$ as required. Now assume for an arbitrary natural number $\alpha$ that $\alpha++ = k++$ as in the previous case use of axiom $\textbf{2.4}$ yields $\alpha = k = b$. This completes the inductive step.

$\blacksquare$

$\endgroup$
  • 1
    $\begingroup$ Does Tao really use $++$ to signify successor? You usually don't see it in mathematics. $\endgroup$ – Arthur Apr 1 '18 at 19:57
  • $\begingroup$ @Arthur Yes it does represent the successor $\endgroup$ – Atif Farooq Apr 1 '18 at 19:58
1
$\begingroup$

All good, but the inductive step can be done a bit simpler:

All we need to show is that there is a unique $a$ such that $a++=k++$. Well, clearly this is true for $a=k$, and so there is at least one, and for any $b$ for which $b++=k++$, we have by axiom 2.4 that $b=a$, and so this $a(=k)$ is unique.

In other words, we don't use the inductive hypothesis, and so don't even need to spell it out. As such, you also don't need to separate the '$k=0$' case from the '$k$ is positive' case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.