1
$\begingroup$

The problem is,

Prove that $n<m{++}\leq n{++}\iff m=n$.

Using only the followings,

  1. Peano Axioms (see the axioms here).

  2. Definition of Addition: Let $m$ be a natural number. We define, $0 + m = m$ and suppose we have inductively defined the addtion $n + m$ then we define, $(n{++})+m=(n+m){++}$. Where $n{++}$ is the successor of $n$.

  3. Commutativity, Associativity and Cancellation Laws of Addition.

  4. Definition of Positivity: A natural number $n$ is said to be positive if $n\neq 0$.

  5. Definition of $\ge$ and $>$: Let $m$ and $n$ be two natural numbers. We say $n\ge m$ or $m\le n$ if there exists some natural number $a$ such that $n=m+a$. We say $n>m$ or $m<n$ if $n\ge m$ (or $m\le n$) but $n\ne m$.

While trying to prove that for natural numbers $a$ and $b$ if $a<b$ then $a{++}\le b$ I found out that to prove that proposition I had to assume the fact that (speaking loosely) there exists no natural number between any natural number and its successor. I thought that this should be an axiom because even if it weren't true it wouldn't contradict the Peano Axioms. However, I am skeptic of my assertion and so I decided to post it as a problem. I will be glad if someone can show me a proof of this assertion using only the statements I have given.

Added:-

Note that, this question mainly focuses on the fact that whether the Peano Axioms are sufficient to let us conclude that, loosely speaking,

There exists no natural number in between a natural number and its successor.

And so we can claim that the natural number that the axioms are sufficient to construct our "wanted" natural numbers.

Please note that before adding any more answer to the question, please read the chain of comments below Sebastian G's answer.

$\endgroup$
11
  • $\begingroup$ This is best proved by induction. $\endgroup$
    – Thomas Andrews
    Dec 25, 2014 at 13:11
  • $\begingroup$ @ThomasAndrews: I tried but couldn't. Can you give a proof? $\endgroup$
    – user170039
    Dec 25, 2014 at 13:13
  • $\begingroup$ @drhab: If $n=1$ then $n{++}=2$. $\endgroup$
    – user170039
    Dec 25, 2014 at 13:34
  • $\begingroup$ No, $n++=2$ and it is not true that $n<m++$. @drhab $m++=m+1$, not $m+1+1$, a slight confusion. $++$ is used in some programming languages to indicate a single increment. $\endgroup$
    – Thomas Andrews
    Dec 25, 2014 at 13:34
  • $\begingroup$ @user170039 Are you sure? If $n=1$ then $n+=2$ and $n++=3$. $\endgroup$
    – drhab
    Dec 25, 2014 at 13:35

1 Answer 1

Reset to default
1
$\begingroup$

First prove by induction: $$ \begin{array}{ll}(1) && \forall n :n=0 \lor n=1 \lor n>1\\ (2) &&\forall n : n= 0 \lor \exists z : z++=n \end{array}$$

Let $P(n,m):= n<m++\leq n++ \Rightarrow m=n$

Now show the statement $\forall n\forall m P(n,m)$ by induction on $n$:

Base Case $(n=0)$: $\forall m P(0,m)$

Let $m$ be arbitrary and assume $0<m++\leq 0++=1$

By (1) $m++=1$ so $m=0$

Inductive step: $\forall m P(n,m) \Rightarrow \forall m P(n++,m)$

By inductive assumption we have $\forall m :n < m++ \leq n++ \Rightarrow m=n$.

We have to show $\forall m :n++ < m++ \leq (n++)++ \Rightarrow m=n++$

For that let m be arbitrary and assume $ n++ < m++ \leq (n++)++$

By commutativity of addition/cancellation laws: $ n < m \leq n++$

By (2) pick $z$ such that $z++=m$ (it is easily shown that $m \neq 0$)

But by inductive assumption $n < z++ \leq n++ $ implies $z = n$

Therefore $m=z++=n++$

$\endgroup$
17
  • $\begingroup$ I don't understand the sixth line. Instead of $m{++}$, I think it should be $(m{++}){++}$. $\endgroup$
    – user170039
    Dec 28, 2014 at 12:46
  • $\begingroup$ @user170039 No, Let $ P(n,m) = n < m++ \leq n++ \Rightarrow m=n$, you want to show $ \forall m \forall n P(n,m)$ I did this by showing $\forall m P(n,m)$ by induction over n. So the base case is $\forall m P(0,m)$ and the inductice step is $ \forall m P(n,m) \Rightarrow \forall m P(n++,m)$ $\endgroup$
    – abc
    Dec 28, 2014 at 14:55
  • $\begingroup$ If you apply induction on $n$ then $m$ must be fixed. Then the transition from $P(n,m)$ to $P(n{++},m)$ isn't very clear to me. It will be good if you can explain every step a bit elaborately. $\endgroup$
    – user170039
    Dec 29, 2014 at 4:25
  • $\begingroup$ @user170039 the transition goes from $\forall m P(n,m)$ to $\forall m P(n++,m)$ see edits $\endgroup$
    – abc
    Dec 29, 2014 at 5:00
  • $\begingroup$ Just one more question. How do you prove the base case of $(1)$? Let me elaborate what I have done. Basically $(1)$ equivalent to $\forall n: n=0\lor n\geq 0{++}$. "We apply induction on $n$. We let, $P(n):n=0\lor n\ge 0{++}$. Now note that $P(0)$ holds since in this case $n=0$. So now we inductively assume $P(n)$ to be true, i.e., $n=0\lor n\ge 0{++}$. To prove $P(n{++})$, i.e., $n{++}=0\lor n{++}\ge 0{++}$ we note that by Axiom 1.3 $a{++} \ne 0$." After that I can't proceed. Can you help? $\endgroup$
    – user170039
    Dec 29, 2014 at 5:47

You must log in to answer this question.