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

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 ...)


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$

Tags:

Model Theory

Related

When does polynomial equation have 2 similar roots? upper bound of outer measure on compact support of continuous function Prove $\int_0^1\frac{\ln x\ln(1+x)}{1-x}\ dx=\zeta(3)-\frac32\ln2\zeta(2)$ A property between "separable" and "second countable" Evaluating $ \lim_{x\to \infty} x \left({{\left(\frac{x}{x+1}\right)}^{x}-\frac{1}{e}}\right)$ Need help to understand the integral rules used solving the convolution of two functions Walking on an infinite grid What is GCD of $7^{3001}-1$ and $7^{3000}+1$? Probability Proof. $P(A | B) = P(A | B^c)$ Word metric on a finitely generated subgroup versus the word metric of its finitely generated parent Is the derivative of the unit normal vector parallel to the tangent vector? When calculating averages, why can we treat exploding die as if they're independent?

Recent Posts