# Homomorphism between structures in first order logic

Let $\sigma =\{R,f,c\}$ be first order logic where $R$ is a unary relation symbol, $f$ a binary function symbol and $c$ a constant symbol. Let $\mathcal{M}=(\mathbb{N}_0,\phi)$ and $\mathcal{N} = (\mathbb{R},\psi)$ be $\sigma$-structures, so that $\phi(R) = \{n \in \mathbb{N}_0 : (\exists k \in \mathbb{N}_0) \ n =8k +3\}$ is a unary relation on the set of nonnegative natural numbers, $\phi(f)(x,y) = x+2y$ is a binary function on the set of nonnegative natural numbers, $\phi(c) = 1$, whereas $\psi(R) =\{x \in \mathbb{R} : x > 9\}$ is a unary relation on the set of real numbers, $\psi(f)(x,y) = x + x·y$ is a binary function on the set of real numbers and $\psi(c) = 2$. Is there a homomorphism form the $\sigma$-structure $\mathcal{M}$ to the $\sigma$-structure $\mathcal{N}$?

Sorry I don't know how to write the set of natural or real numbers nicely. I've tried defining the rule for the homomorphism function but can't find it and don't really have a method to prove its existence other than finding the homomorphism.

• Is No the set of natural numbers (starting at 0) and the R in the structure N the set of reals? When you write "M=(N0,ϕ) i N = (R,ψ)" is the "i" supposed to be an "and"? – Andrés E. Caicedo Jan 31 '18 at 20:27
• If that is the case, and $\pi$ is a homomorphism, you should be able to compute $\pi(3)$ (since $3=\phi(f)(1,1)$). That should be enough for you to see the answer. – Andrés E. Caicedo Jan 31 '18 at 20:32
• (As a general observation, it is really bad form to use the same variable $R$ in the same sentence to mean different things. You are using it to denote both the set of reals (I think) and the unary relation symbol in your language. Also, one does not say that $\sigma$ is a first-order logic. Instead, $\sigma$ is typically called a signature, or a vocabulary, or even a language.) – Andrés E. Caicedo Jan 31 '18 at 20:34

As suggested by Andrés Caicedo, there is no homomorphism from the $\sigma$-structure $\mathcal{M}$ to the $\sigma$-structure $\mathcal{N}$.
The proof is by contradiction. Suppose there were such an homomorphism $h \colon \mathbb{N}_0 \to \mathbb{R}$ and consider $3 \in \mathbb{N}_0$. Then, $3 \in \phi(R)$ because $3 = 8 \cdot 0 + 3$. Note that $\phi(f)(1,1) = 1 + 2 \cdot 1 = 3$ and $\psi(f)(2,2) = 2 + 2 \cdot 2 = 6$. Since $h$ would preserve the interpretation of $f$ and $c$, we would have \begin{align} h(1) &= h(\phi(c)) = \psi(c) = 2 & h(3) &= h\big(\phi(f)(1,1)\big) = \psi(f)\big(h(1),h(1)\big) = \psi(f)(2,2) = 6. \end{align} Now, $h(3) \notin \psi(R)$ because $h(3) = 6 \not> 9$. Summing up, $3 \in \phi(R)$ but $h(3) \notin \psi(R)$, which is impossible because $h$ should preserve $R$.