defining {1} with just n+k=l in $\Bbb{N}$ and proving identity is the only automorphism in that kind of structures

Question

Let $\mathscr A$ be a structure $<N, s^{\mathscr A}>$ for the predicate language without formal equality $\mathscr L$, having a predicate symbol s with an arity of 3, where $<n,k,l> \in s^\mathscr A \iff n+k=l$

Prove that:

1. Every of the sets {0}, {1}, {3}, {(n,k)|5 divides n-k} is definable in $\mathscr A$ with a formula from $\mathscr L$
2. the identity function is the only automorphism in $\mathscr A$

My Solution:

1. $\phi_0(x) \equiv \forall y s(x,y,y)$

Since I couldn't define {1} with just summation of two natural numbers my approach is to define a formula which defines a natural number multiplied some number of times:

$$ \mu_0(x,y) \equiv \exists z(\phi_0(z) \& s(x,z,y)) \\ \mu_1(x,y) \equiv \exists z(\phi_0(z) \& s(x,z,y)) \\ \mu_2(x,y) \equiv s(x,x,y) \\ ... \\ \mu_n(x, y) \equiv \exists z \mu_{n-1}(x,z) \& s(x,z,y) $$

And from there using $\mu_n$ I define the singleton set {1} $$ \phi_1(x) \equiv \forall y \mu_y(x,y) $$

Edit

The actual way to define {1} is by first defining the relation $\le$ and then using it. The previous way is not correct since n is a subscript and not a free variable. $$ \phi_{\le}(x, y) \equiv \exists k \ \ s(x,k,y) \\ \phi_1(x) \equiv \forall y \ \ \neg \phi_0(y) \implies phi_{\le}(x,y) $$

And having a formula for {1} I define the rest of the singleton sets in the following manner:

$$ \phi_2(x) \equiv \exists y \phi_1(y) \& s(y,y,x) \\ \phi_3(x) \equiv \exists y \exists z (\phi_2(y) \& \phi_1(z) \& s(y,z,x)) \\ \phi_5(x) \equiv \exists y \exists z (\phi_3(y) \& \phi_2(z) \& s(y,z,x)) \\ \phi_{strange}(n,k) \equiv \exists x \exists y \exists z(\phi_5(z) \& s(x,k,n) \& \mu_y(x,z)) \\ $$

For proving 2. I have a vague idea which I'm not sure is correct. First I prove inductively that every element is definable in the given structure.

• {0} - we already defined that using the formula $\phi_0$
• (Inductive Step) Assuming we have defined $\phi_n$ we can define $\phi_{n+1}$ like this $\phi_{n+1}(x) \equiv \exists y \exists z(\phi_n(y) \& \phi_1(z) \& s(y,z,x))$

From that we see that every element is definable in the structure $\mathscr A$

We know that if there's an automorphism h(a) s.t. $h(a) \neq a$, the element a is not definable in the structure. Then if we assume there's another automorphism different from the identity and pick any element we see that it's not definable, which leads to contradiction with the fact that we have defined every element in the structure.

My questions are:

• Is my solution so far correct, formal and rigorous enough?
• Is the definition for the multiplication formula correct and formal in the way I've defined it? I'm not sure I can define a formula in the given manner.
• Is my idea (sort of proof) for 2. correct, and if not how should I prove it?

Answer 1

I don't see how your $\mu_n$ function is supposed to work ...

Here is one way to define a predicate $\phi_1(x)$ that under the given interpretation wil only be true for $x=1$:

$$\phi_1(x) \equiv \forall y \forall z (s(y,x,z) \land \neg \phi_0(x) \land \neg \exists u \exists v \exists w (\neg \phi_0(u) \land \neg \phi_0(v) \land s(y,u,w) \land s(w,v,x)))$$