I've just started learning mathematical logic. Could you please give me some feedback and hints for the following problem? I know that an automorphism is a monomorphism (hence injective) and surjective map from a set to itself. Also, in all structures, equality is always given.
Let $M_0=(\mathbb{N},<)$ and $M_1=(\mathbb{Z},<)$. 1) Show that for any automorphism $f$ of $M_0$, we have $f(0) = 0$.
Attempt: Suppose $f(0)>0$ (which is possible since $f(0)$ is just a number. Then there exists a number $a \in \mathbb{N}$ such that $f(a) < f(0)$ (this is due to surjectivity). But since $f$ is an monomorphism, this would imply, by definition of monomorphism, that a < 0. This is a contradiction. Hence $f(0)=0$
2) Show that $M_0$ has a unique automorphism.
Attempt: The standard way to show uniqueness is to assume there are two automorphisms $f_1$ and $f_2$ and show that they match up at every input. This has been shown true for $0$. But I got stuck at showing for the other numbers. Please give me some hints.
3) Show that for any $n \in \mathbb{Z}$, the function $f_n: x \rightarrow x+n$ is an automorphism of $M_1$.
Attempt: My question is that our structure is not given addition, so how come this question makes sense? Once I can make sense of this, checking that the function is an automorphim is just a routine check of the definitions. Is this thinking correct or is there some hidden corner that I need to be aware of?
4) Show that if $\sigma$ is an automorphism of $M_1$, then there is $n \in \mathbb{Z}$ such that $\sigma = f_n$.
Attempt: Let $a,b \in \mathbb{Z}$ and suppose that $a < b$. Then $\sigma(a)<\sigma(b)$ by the property of monomorphism. Then I want to define addition in this structure. But I don't think it's possible... If we have addition, then it's easy to define inequalities, but the other way around just seem not possible to me.
Any help would be appreciated. Thanks!
Your proof for (1) is right. For (3), the definition of $f$ takes place outside the structure: it's no problem that $f$ is defined in terms of an operation which isn't part of $M_1$.
For (2) and (4), you want to think inductively. For instance, for (2), you want to show that every automorphism of $M_0$ is the identity; so given a nontrivial automorphism $f$, consider the least element moved by $f$ and try to get a contradiction. For (4), let $f:M_1\rightarrow M_1$ be an automorphism, and let $f(0)=n$; you want to show that $f(x)=x+n$ in general. To do this, argue by induction (in two directions: going "up" and "down" from zero). Similarly to (3), note that the arguments you use here are invoking structure which $M_0$ and $M_1$ can't really "see", but that's fine - this argument is taking place in (basically) the set-theoretic universe around $M_0$ and $M_1$.