Express addition of natural numbers ($+$) in structure $(N;=;S;*)$ where $S(n)$ is n + 1

Question

Express addition of natural numbers ($+$) in structure $(N;=;S;\cdot)$ where $S(n)$ $\rightarrow$ $n + 1$

I need to exress operationd of addition in this structure. I tried to: $c = a + b = a * S(0) + b * S(0) $ but stucked. Also tried $a = S(a-1) = S(S(a-2))$, $S(a-1) * S(b-1) = ab $

Please help me a have to send the solution of this problem today.

Answer 1

Definition:

$m + 0 = m$

and

$m + S(n) = S(m+n)$

for all natural numbers $m,n\geq 0$.

Define $1 = S(0), 2=S(1), 3=S(2), \ldots$.

Then $n+1 = n+ S(0) = S(n+0) = S(n)$. This shows that $S$ is the successor function.

Moreover, for instance,

$1+1 = 1 + S(0) = S(1+0) = S(1) = 2$.

Answer 2

This is my interpretation of your question, as Alex stated in his comments; let me know if you mean something different.

Let $\mathcal{L}=\{S,\times\}$, and consider $\mathbb{N}$ as an $\mathcal{L}$-structure. Show that addition is definable in $\mathbb{N}$ – ie, find an $\mathcal{L}$-formula $\varphi(v_1,v_2,w)$ such that $\mathbb{N}\models\varphi(a_1,a_2,b)$ iff $b=a_1+a_2$, for any $a_1,a_2,b\in\mathbb{N}$.

To this end, first define $\psi(v_1,v_2,w)$ to be the following $\mathcal{L}$-formula: $$S(v_1\times w)S(v_2\times w)=S(w\times w\times S(v_1\times v_2)).$$ Expanding the left hand side of $\psi$ out in usual arithmetic notation gives $$(v_1w+1)(v_2w+1)=w^2v_1v_2+w(v_1+v_2)+1,$$ and doing the same for the right hand side gives $$w^2(v_1v_2+1)+1=w^2v_1v_2+w^2+1.$$ Thus we will have $\mathbb{N}\models\psi(a_1,a_2,b)$ if and only if $b^2=b(a_1+a_2)$. If $b$ is non-zero this reduces to $b=a_1+a_2$, as desired, but if $b=0$ it will hold for any $a_1,a_2\in\mathbb{N}$, so we have to handle this case differently.

Note for this that $0$ is definable, eg by the formula $\theta(u):=\neg\exists v(u=S(v))$. So, putting this together with $\psi$, we can define our desired $\varphi(v_1,v_2,w)$ by $$(\theta(v_1)\wedge\theta(v_2)\wedge\theta(w))\vee(\neg\theta(w)\wedge\psi(v_1,v_2,w)).$$ This formula is due to Julia Robinson, whose other work on definability you may be interested in if you enjoyed this problem. See here for instance for a nice reference, which gives an exposition of her remarkable result that $\mathbb{Z}$ is definable in $(\mathbb{Q},+,\times,0)$.