I'm learning logic so please help me check these questions. In particular, I got stuck at number $6$ and $7$.
Let $L=\{ \cdot \}$ and let $M$ be the L-structyure whose underlying set is $\mathbb{N}$ (the nonnegative integers) and where the binary function $\cdot$ is interpreted as the multiplication.
1) Show that there is a formula $\phi_0[x]$ such that $M \vDash \phi_0[x]$ if and only if $a=0$.
Attempt: $\phi_0[x]=\forall y(y\cdot x \simeq x)$
2) Show that there is a formula $\phi_1[x]$ such that $M \vDash \phi_1[x]$ if and only if $a=1$.
Attempt: $\phi_1[x]=\forall y(y\cdot x \simeq y)$
3) Show that there is a formula $\phi_{prime}[x]$ such that $M\vDash \phi_{prime}[a]$ if and only if $a$ is prime.
Attempt: A prime number $p$ is a number that has only two distinct divisors, $1$ and $p$. So first I define division: $\tau[u,v] = \exists k(u\cdot k = v)$, and this formula is to be understood as $u | v$. Then I define $\phi_{prime}[x]= \forall y((\neg (y \simeq \phi_1[x]) \wedge \neg(y\simeq x) \rightarrow \neg \tau[y,x])$.
4) Show that if an automorphism $\sigma$ of $M$ satisfies $\sigma(p) = p$ for all prime numbers $p$, then $\sigma$ is the identity.
Attempt: We use the Fundamental Theorem of Arithmetic. Let $n \in \mathbb{N}$. Then write $n= p_1^{e_1}...p_s^{e_s}$. Then $\sigma(n)=\sigma(p_1^{e_1}...p_s^{e_s})= (\sigma(p_1))^{e_1}...(\sigma(p_s))^{e_s}=p_1^{e_1}...p_s^{e_s}=n$, and so $\sigma$ is the identity.
5)Find all automorphisms of $M$.
Attempt: The claim is that the identity is the unique automorphism of $M$. By (3), all primes are definable in $(\mathbb{N}, \cdot)$, and any automorphism fixes them. By (4), the automorphism is the identity map.
6) Show that the only two elements of $M$ such that there exists a formula $\phi_n$ such that $M \vDash \phi_n[a]$ if and only if $a=n$ are $0$ and $1$.
Attempt: Isn't this a contradiction because of (3)? I don't understand the difference between (3) and (6). Could someone please help me explain and give me a hint how to solve it?
7) Show that there is no formula $\psi[x,y,z]$ such that $M \vDash \psi[a,b,c]$ if and only if $c=a+b$.
Attempt: I scratched my head for an hour and couldn't see any direction...
Any help would be much appreciated!
(1), (2), (3), and (4) are correct.
However, there is one big problem, which occurs both in your puzzlement with (3) vs. (6), and in your answer to (5): the distinction between a set of elements being definable, and individual elements being definable.
Just because a set of elements (like, the set of primes) is definable, does not mean that each (or even any!) of its elements is definable. For example, the whole domain of a structure is always definable (via "$x=x$"), but surely you don't believe that every element of a structure is always definable!
(If you prefer to talk about definable sets instead of definable elements, note that an element is definable iff its singleton is a definable set. So, the point is: just because a set is definable, does not mean that all its subsets are definable!)
This resolves the tension between (3) and (6). It also means your answer to (5) is wrong. Indeed, I claim that there are lots of automorphisms! HINT: think about what happens if you "permute" the primes . . .
Meanwhile, for (7), here's a hint: remember that the truth value of a formula on a tuple can't be changed by applying an automorphism to that tuple. So, for example, consider the instance "$2+3=5$" of the putative formula $\varphi$: do you see how to construct an automorphism $\alpha$ such that $\alpha(2)+\alpha(3)\not=\alpha(5)$?
Re: (7), note that the answer I outlined above is a coarse analysis: basically, we're saying that all formulas are "automorphism-invariant," so any property which is not invariant under automorphisms can't be defined by a formula. However, this isn't sharp: there are lots of times where we have an automorphism-invariant property which is not defined by a formula!
For example, if we consider the structure consisting of the natural numbers with addition only (instead of multiplication only - the theory of this is called Presburger arithmetic, while that of the structure you're considering in the OP is Skolem arithmetic), then there are no nontrivial automorphisms (exercise), so every relation is automorphism-invariant. On the other hand, there are only countably many definable relations, but uncountably many relations total (exercise), so clearly "most" relations are undefinable. (For example, it turns out multiplication is not definable!) How can we prove this?
In such cases a finer analysis is needed: one standard tool here is quantifier elimination, and another is Ehrenfeucht-Fraisse games. But this is a very different topic, so I'll stop here.