5
$\begingroup$

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.

  • 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).2012-02-25
  • 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.2012-02-25
  • 0
    @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](http://math.stackexchange.com/a/15465/25699) and must be misinterpreting it...2012-02-25
  • 0
    @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.2012-02-25
  • 0
    You went wrong at the very beginning. ($\forall a \ne 0)(\exists! b)(b++=a)$, is not the same as $\forall a \exists ! b(a \ne 0 \rightarrow (b++=a))$. It should be $\forall a(a \ne 0 \rightarrow (\exists !b(b++=a)))$.2012-02-25
  • 2
    @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.2012-02-25
  • 0
    @André Nicolas: Okay. So for existence, I need to prove for arbitrary positive $a$ that there is a $b$ such that $b++=a$. The base case follows from $0\not=0$. Then I induct on $a$ by assuming for arbitrary positive $a$ there is a $b$ with $b++=a$ and deriving that there is also some $c$ with $c++=a++$ for $a++$. If I choose $c=a$ for $c$, then since the successor operation is a function, $c++=a++$. This closes induction. For uniqueness, I just use what you said.---Is this reasoning correct?2012-02-25
  • 0
    @russell11: It is better not to say anything like "follows from $0\ne 0$". Sounds funny. Maybe instead "For $b=0$, there is nothing to prove." Then "If the result holds for $b$ (or even if it doesn't), it holds for $b{}+{}+$, since this is a successor of $b$." Don't mention injective, unless the word is used in an axiom, which it isn't. Anyway, you are just proving existence.2012-02-25

4 Answers 4