Each natural number is equal to the set of all natural numbers less than it

elementary-number-theoryelementary-set-theoryproof-verification

Please check my proof that each natural number is equal to the set of all natural numbers less than it.


Let $\mathbb N$ is the set of natural numbers by Von Neumann construction (https://www.wikiwand.com/en/Natural_number#/Formal_definitions).

We define addition operator on $\mathbb N$ by setting $a + 0 = a$ and $a + S(b) = S(a + b)$ for all $a, b\in \mathbb N$. Hence, $S(a)=a+1=a\cup \{a\}$. We also define order $\leq$ as follows $$b\leq a\iff \exists c\in\mathbb N \text{ such that }b+c=a$$Hence $b<a\iff b\leq a$ and $b\neq a$.

Lemma: $m\leq n\iff m<n+1$

Let $T=\{n\in\mathbb N\mid m\leq n\iff m<n+1\}$. It's clear that $0\in T$. Assume that $n\in T$, then $m\leq n\iff m<n+1$ for all $m\in\mathbb N$. It's trivial that $p\leq n+1\implies p<n+2$. Now we prove the converse $p<n+2\implies p\leq n+1$.

If $p=0$, then $p<n+2\implies b\leq n+1$. If $p>0$, then $p=m+1$ for some $m\in\mathbb N$. Thus $p<n+2\implies m+1<n+2\iff m<n+1\implies m\leq n$ [Since $n\in T$] $\implies m+1\leq n+1\implies p\leq n+1$. Thus $n+1\in T$.

By principle of induction, the theorem is proved. $\Box$

Let $T=\{n\in\mathbb N\mid n=\{m\in\mathbb N\mid m<n\}\}$. It's clear that $0=\varnothing\in T$ by vacuity. Assume that $n\in T$, then $n=\{m\in\mathbb N\mid m<n\}$. Thus $n+1=n\cup \{n\}=\{m\in\mathbb N\mid m<n\}\cup \{n\}=
$ $\{m\in\mathbb N\mid m\leq n\}=\{m\in\mathbb N\mid m<n+1\}$ [By the Lemma]. Thus $n+1\in T$. By principle of induction, the theorem is proved. $\Box$

Best Answer

The proof itself seems right, but there is no need for induction for the lemma:

$m\le n\implies m<n+1$: either $m=n<n+1$ or $m<n<n+1$

$m\le n\impliedby m<n+1$: $$m<n+1\overset{def}{\iff}\exists c>0(m+c=n+1)\\\implies\exists c>0(m+c-1=n)\\\implies \exists k\ge 0(m+k=n)\overset{def}{\iff} m\le n$$