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

810 Views Asked by At

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$

1

There are 1 best solutions below

1
On 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$$