Confused: examples of homomorphism from $(\Bbb N,+)$ to $(\Bbb Z,+)$ and from $(\Bbb N,<)$ to $(\Bbb Z,<)$

Question

I am confused about the concept of homomorphism, in particular my lecturer asks us to give examples, which I find myself unable to. Could anyone help please?

According to Hodges' Shorter Model Theory, a homomorphic function $f$ between structures $A$ and $B$ that share signature $L$ (ie. same set of relation and function symbols) is one which preserves functions and relation symbols:

1) For each constant in $L$, $f(c^A)=c^B$

2) For each tuple $\bar a$ from $A$ and relation symbol $R$ of $L$, if $\bar a\in R^A$ then $f(\bar a)\in R^B$

3) For each function symbol $F$ of $L$ and tuple $\bar a$, if $\bar a\in R^A$ then $f(F^A(\bar a))=F^B(f(\bar a))$

So I am guessing one simple example would be, if $A$ and $B$ both have domain of all human, and $=$ is the only symbol, then a homomorphic $f$ would map 'Obama' from $A$ to 'Obama' to $B$ (as per 1) regarding constant symbols)?

But then my lecturer asks us to come up with examples of homomorphic functions between the following:

a) from $(\Bbb N,+)$ to $(\Bbb Z,+)$

b) from $(\Bbb N,<)$ to $(\Bbb Z,<)$

I think I have difficulty understanding 2) and 3) - because I am not even sure what am I supposed to answer here.

I would say that a function $f$ is homomorphic if it maps $+/<$ to $+/<$ respectively; but I am sure the answer is not that simple. In particular, I am not sure:

• Why do $\Bbb N$ and $\Bbb Z$ make a difference? Does it matter that if domains are $\Bbb N$?

• $+$ and $<$ are the only symbols in the signature, so are they the only symbols we need $f$ to be concerned with, or do we also need to worry about other symbols that built on these, e.g. $-$?

Answer 1

For your second question, a theorem or exercise down the road will be to show that if you preserve the "basic" operations/relations then you also preserve those "built up" from them. This winds up being an induction on complexity, which is a technique you'll use all the time here.

Let's look at your first case. For clarity, I'm going to write "$\oplus$" for the symbol we're using for addition, "$+^\mathcal{N}$" for the usual addition on naturals, "$+^\mathcal{Z}$" for the usual addition on integers, and "$\mathcal{N}$" and "$\mathcal{Z}$" for the structures in the language $\{\oplus\}$ with their respective domains being $\mathbb{N}$ and $\mathbb{Z}$ and their respective interpretations of $\oplus$ being "$+^\mathcal{N}$" and "$+^\mathcal{Z}$."

We want an example of an $f$ with the following properties (where for ease of reading I've bolded the important bits):

• $f$ is a function from $\mathbb{N}$ to $\mathbb{Z}$,

• [stuff about relation symbols, but we don't have any of those, so we don't care],

• [stuff about constant symbols, but we don't have any of those, so we don't care], and

• for each pair $x,y\in\mathbb{N}$ of inputs, we have $$f(x+^\mathcal{N}y)=f(x)+^\mathcal{Z}f(y)$$ [and stuff about all other function symbols, but we don't have any other function symbols, so we're done caring].

At this point it's a good idea to see a non-example. Consider the function $$f:\mathbb{N}\rightarrow\mathbb{Z}: x\mapsto x+^\mathcal{Z}17.$$

This is not a homomorphism: we have $$f(2+^\mathcal{N}3)=22\quad\mbox{but}\quad f(2)+^\mathcal{Z}f(3)=39.$$

• Note that the $f$ above makes sense: whenever $x$ is in the domain of $f$, $x$ is a natural number, as is $17$, so $x+^\mathcal{Z}17$ is a natural number and hence also an integer, or element of the codomain. I could have also written "$x+^\mathcal{N}17$" as well, but that would have had the possibly-confusing feature of using a "left-hand-side" operation on the "right-hand-side" - while it would still be correct, it would probably be more annoying.

---

Now what about an actual homomorphism?

Well, there's an obvious map from $\mathbb{N}$ to $\mathbb{Z}$ which preserves basically everything - the identity map! Checking that this is in fact a homomorphism feels silly, but it's perfectly valid. Note that this isn't always an option:

• Maybe we want a homomorphism from a structure $\mathcal{A}$ to a structure $\mathcal{B}$, but the underlying set of $\mathcal{A}$ is not a subset of the underlying set of $\mathcal{B}$. In this case the identity map isn't even a map from $\mathcal{A}$ to $\mathcal{B}$, let alone a "good" one.

• Or maybe the underlying sets are appropriately related, but the structure isn't. For instance, consider the language consisting of a single binary operation symbol $*$, and the structures with the same domain $\mathbb{Z}$ but where $*$ is interpreted as addition in one and multiplication in the other. The identity map is a function from one structure to the other, but it's not a homomorphism since e.g. $2+3\not=2\times 3$.

Now: can you find a non-identity homomorphism from $\mathbb{N}$ to $\mathbb{Z}$? (HINT: think about the even integers ...)

Answer 2

Note: I might be missing something since the question is tagged model-theory. Please downvote and leave comments accordingly.

---

For every $m \in \Bbb Z$ there exists one and only one homomorphism mapping $(\Bbb N,+)$ to $(\Bbb Z,+)$ such that

$\tag 1 1 \mapsto m$

It sounds like the OP's definition of a homomorphism between two ordered sets is any increasing function, but if that is not the correct interpretation, we'll just 'throw in' the decreasing functions.

OK, three are many, many increasing functions from $(\Bbb N,\lt)$ to $(\Bbb Z,\lt)$. In fact, when I try to imagine them all I get a headache that has the power of the continuum. Imagine walking on $\Bbb Z$ in a fixed direction starting from any initial spot, and whenever you feel like it, shouting out the next successive natural number (you are allowed to stop walking and call out multiple natural numbers for that $\Bbb Z$ number point).

Every homomorphism from $(\Bbb N,+)$ to $(\Bbb Z,+)$ is monotonic, so you can come up with easy/structured examples of order preserving mappings.

Here is an order preserving mapping that doesn't preserve the addition operation:

$\tag 2 k \mapsto 2^k$