For $m,n\in \omega, m \leq n$ imply $\exists ! p\in \omega\ s.t\ m+p=n$

Question

For a set $A$, we define $A^+:=A\cup\{A\}$

When we define, $$0=\emptyset,\ 1=0^+,\ 2=1^+,\ \cdots$$ set of natural number $\omega$ is defined as $$\omega=\{0,1,2,\cdots\}$$

The order $"\leq"$ is defined as $$a\leq b \ iif \ a\in b \ or \ a=b$$

When $\gamma_m:\omega\rightarrow\omega$ defined by following condition:

1. $\gamma_m (0)=m$ 2. $\gamma_m (n^+) =(\gamma_m (n))^+$

Addition is defined as $$m+n=\gamma_m (n)$$ In this setting how can we prove: $m,n\in \omega, m \leq n$ imply $\exists ! p\in \omega\ s.t\ m+p=n$

Answer 1

I will prove the following assertion:

For any natural numbers $m$ and $n$:

(a) $m<n$ if, and only if, there exists $p\in\omega,\;p\not=0$, such that $m+p=n$

(b) $m\leq n$ if, and only if, there exists $p\in\omega$ suc that $m+p=n$

Demonstration:

(a) $\;\Longrightarrow)\;$Let $m$ be a fixed natural number, and let

$$A=\{n\in\omega|\text{ if }m<n\text{ then there exists }p\in\omega\text{ different from zero, such that }m+p=n\}$$

We will prove by indution that $A=\omega$.

1. $0\in A$; there is no $m\in\omega$ such that $m<0$, and since the antecedent is false, the conditional is true.

2. Suppose that $n$ is a natural number that belongs to $A$. Let $m<n^+$. Then $m<n$ or $m=n$. If $m<n$, by the induction hypothesis, there exists $p\in\omega$, different from zero, such that $m+p=n$. Therefore, $m+p^+=(m+p)^+=n^+$, and $p^+\not=0$, so $n^+\in A$. On the other hand, if $m=n$, then choosing $p=1=0^+$, we have that $m+1=m+0^+=(m+0)^+=m^+=n^+$ and $1\not=0$. So we again conclude that $n^+\in A$, and by the principle of induction, $A=\omega$.

$\Longleftarrow)\;$Suppose that there exists $p\in\omega$, different from zero, such that $m+p=n$

Lemma: For each $m,n\in\omega$, if $n\not=0$, we have that $m<m+n$

Demonstration: By induction over $n$. There is nothing to prove if $n=0$, because the antecedent is false. Now, let $n\in\omega$ such that if $n\not=0$, then $m<m+n$. We have to prove that if $n^+\not=0$, then $m<m+n^+$. There is no $n$ such that $n^+=0$, and:

• If $n=0$,

$$m<m^+=(m+0)^+=m+0^+$$

• If $n\not=0$, by the induction hypothesis, $m<m+n$ and $m+n<(m+n)^+=m+n^+$

$\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\square$

Following the previous lemma, if $m+p=n$ with $p\not=0$, we have that $m<m+p=n$ and $m<n$, and the statement of a) is finally proved

(b) $\;\Longrightarrow)\;$If $m\leq n$, then $m<n$ or $m=n$. If $m<n$, then by a), there exists $p\not=0$ such that $m+p=n$. If $m=n$, then $m+0=m=n$, and $p=0$.

$\Longleftarrow)\;$Suppose that there exists $p\in\omega$ such that $m+p=n$. If $p=0$, then $n=m+p=m+0=m$, and $m=n$, so $m\leq n$. If $p\not=0$, by the statement of a), $m<n$, and $m\leq n$.

$\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\square$

I leave to you the uniqueness of such $p\in\omega$ (although I will publish it in the near future).