0

$n'$ denotes the successor of $n$. Forgive me if this seems utterly trivial (since the equivalence can be shown simply by using the order properties of $\mathbb{N}$, but I can't seem to get the proof right).

To show that $ \mathbf{1.}\ (\forall m<n \ P(m) \implies P(n))$ implies $ \mathbf{2.} \ (\forall m \leq n \ P(m) \implies P(n'))$, we note that by putting $n=n'$ in $\mathbf{1}$, we get

$$ (\forall m<n' \ P(m) \implies P(n'))$$

This is what we want, since $m < n' \iff m \leq n$, so we're done.

But to show $\mathbf{2} \implies \mathbf{1}$, I get stuck. If I use the same trick as before, by putting $n_{0} = n'$, I'm not sure how to deal with $\forall m \leq n \ P(m)$.

I realise also that I hadn't spelled out exactly details like whether $n =0$ or not, or else $m < n' \iff m \leq n$ doesn't hold.

$\mathsf{Note}$: In the paper I'm reading, it says that the equivalence can easily be shown by considering $ n \nleq 0 \land m < n' \iff n \neq 0 \land m \leq n \implies \exists m (n=m')$, but it still seems a bit cryptic to me.

Maxis Jaisi
  • 1,553

1 Answers1

1

Hint

Assuming 2, we have to prove that :

$\forall m \ [(m < n \land P(m)) \to P(n)]$.

So, assume : $m < n \land P(m)$ and we consider the case $n > 0$ (the case $n=0$ is trivial).

Thus, there exists $k$ such that $n=k'$ and $m < n=k'$ implies : $m \le k$.

Applying 1, from $m \le k \land P(m)$ we get : $P(k')$, i.e. $P(n)$.

Mauro ALLEGRANZA
  • 94,169