Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am independently working through Tao's Analysis I, and one of the exercises is to prove that every positive natural number has a unique predecessor. The actual lemma is (where $n++$ denotes the successor of $n$):

Let $a$ be a positive [natural] number. Then there exists exactly one natural number $b$ such that $b++=a$.

The hint given is to use induction, and the book uses the Peano axioms with $0\in\mathbb{N}$.

Here is my attempt at a proof, but I am not sure if I applied induction properly (I didn't seem to need the inductive hypothesis in proving the $k+1$ case), and I am even more unsure if uniqueness is proven:

The statement to prove is $(\forall a\not=0)(\exists!b)(b++=a)$, which is the same as $\forall a\exists!b(a\not=0\rightarrow (b++=a))$. Induction is used on $a$.

The basis step is to prove for $a=0$, which is $\exists!b(0\not=0\rightarrow (b++=0))$. Since the antecedent of the conditional is false, the statement is vacuously true. [But is $b$ unique...?]

For the inductive step, it is assumed that for an arbitrary $k$, $\exists!b(k\not=0\rightarrow (b++=k))$. Then $\exists!b((k++\not=0)\rightarrow (b++=k++))$ is to be derived. The second of these (the one being derived) can be rewritten as $(k++\not=0)\rightarrow (c++=k++)$, for some $c$.

$k++\not=0$ is true even without assuming it, since $0$ does not have a predecessor. But $c++=k++$ implies $c=k$ (because the successor function is injective), which shows that a [unique?] $c$ can be chosen such that it is equal to $k$. This closes the induction and thus every positive natural number has a unique successor.

My questions are: (1) Is this proof correct? (2) If the answer to the first question is 'no', is the general idea for the proof correct? (3) If the answers to both of the preceding questions are 'no', could someone point me in the right direction for a correct proof?

Any help would be appreciated. Thanks.

share|improve this question
1  
First line is incorrect, as the two statements are not equivalent (as you consider in the second paragraph, $b$ is not unique in this case). –  Alex Becker Feb 25 '12 at 6:09
3  
The proof doesn't make full sense. Something close to it will work. The logic seems flawed in the last paragraph. You want to prove that there is a unique $c$ such that $c++=k++$. In the next paragraph you write that $c++=k++$ implies that $c=k$. Are you assuming what you are trying to prove? It looks as if you are. But surely that's not what you have in mind. Also, I strongly advise that you completely separate the proof of existence of predecessor from the proof of uniqueness. Also, please use fewer symbols, you don't have full control of them. –  André Nicolas Feb 25 '12 at 6:21
    
@André Nicolas: Thanks. You are right that I am assuming my conclusion in trying to prove it. About separating proof of existence from proof of uniqueness, I read this post and must be misinterpreting it... –  russell11 Feb 25 '12 at 6:35
    
@russell11: I checked the course notes from your link. As would expect from someone as good as Tao, the arguments are rigorous, but mostly use ordinary language. –  André Nicolas Feb 25 '12 at 6:36
1  
@russell11: You are free to disregard. But uniqueness is trivial. Suppose that $x$ has predecessors $u$ and $v$. Then $u++=v++$, so by Axiom IV (if I recall Tao's numbering), $u=v$. The end. Now you can get rid of the $\exists$! that you are fond of but have difficulty handling. You cannot expect to prove things by symbol manipulation. –  André Nicolas Feb 25 '12 at 6:44

2 Answers 2

As you have almost discovered yourself, things begin to slip right from the start whan you rewrite $\forall(a\ne0)\exists!b(b{+}\!{+}=a)$ to $\forall a\exists!b(a\ne0\rightarrow (b{+}\!{+}=a))$. The latter claim is not true because $\exists!b(0\ne 0\rightarrow \cdots)$ is false; there is more than one $b$ such that $(0\ne 0\to \cdots)$ is true.

I can't actually follow your reasoning in the induction step, but something seems to have gone very wrong by the time you argue "because the successor function is injective". Isn't that part of what you're trying to prove?

Most formulations of Peano Arithmetic do contain an explicit axiom saying something like $x{+}\!{+}=y{+}\!{+}\to x=y$, but you're not quoting the exact axioms you're using, so I can only guess that this might also be true for your system. In that case, I think it would be clearer to prove by induction that every nonzero number has at least one predecessor. When the dust has settled you can then add in uniqueness from the axiom at your leisure.

Done properly that way, you indeed don't need the induction hypothesis during the induction step -- this is usually a sign of something being amiss, but in this particular case it is actually all right. You are still getting something from the induction principle in the induction step, namely the assumption that the $a$ you are proving things about in the induction step is actually a successor. That happens to be the very fact you set out to prove, which explains why you didn't need the induction hypothesis in order to make progress.

share|improve this answer

Do induction on B and find that 0++ = n <=> 1=n, i think this proves the base and also works for uniqueness using axtiom number4.

Then assume B++ = N and Prove (B++)++ = N++, Again using axiom (4) u have that B++ = N which is what u assumed. Thus it is correct

Not sure if this proof is correct, sorry if i confuse instead of help.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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