If σ does not have any relation symbols, then h is a σ-embedding if and only if it is one-to-one. Let $A, B$ be $σ$-structures and let $h:A→B$ be a $σ$-homomorphism. Prove that if $σ$ does not have any relation symbols, then $h$ is a $σ$-embedding if and only if it is one-to-one.
Definition 1: A $σ$-embedding is a $σ$-homomorphism  for which $h$ is a $σ$-isomorphism from $A$ to $B’$ with $B’$ being the substructure of $B$ formed by $h[A]$.
Definition 2: A $σ$-isomorphism is a $σ$-homomorphism that has a 2-sided inverse $h^{-1}$, which is also a $σ$-homomorphism.
From those definitions, apparently the rest of the proof is trivial. However I'm not sure... First of all I'm confused about why it only needs to be one-to-one, why not onto? Is it because we excluded the relation symbols for which the property is only one sided?
 A: The map $h$ need not be onto for this problem as the definition of an embedding is that it is an isomorphism onto its image $h[A]$. The size of the "ambient" structure $B$ doesn't matter - only how $A$ relates to $h[A]$.
One side of this proof is easier. Suppose that $h$ is an embedding. Then it is an isomorphism onto $h[A]$, i.e. there is an inverse map $h^{-1}: h[A] \longrightarrow A$. Hence, if $h(a_1) = h(a_2)$ then $a_1=h^{-1}(h(a_1))=h^{-1}(h(a_2))=a_2$ and $h$ is one to one. Note here that we didn't need $h^{-1}$ to be a $\sigma$-homomorphism; this works equally well if we forget the $\sigma$-structure and consider these only as sets.
For the converse, suppose that $h$ is one to one. Then I claim that there is an inverse $h^{-1}: h[A] \longrightarrow A$. Indeed, it is not hard to see that there is a set map $h^{-1}$. For any $b \in h[A]$, there is a unique element $a \in A$ such that $h(a) = b$. This is precisely the definition of $h$ being one to one. Hence, we can simply define $h^{-1}(b) = a$ for $b \in h[A]$. We are not done yet, however, as we need to show that $h^{-1}$ is in fact a $\sigma$-homomorphism. And here is where we need to use the assumption that $\sigma$ has no relation symbols.
This assumption tells us that $\sigma$ consists solely of function symbols, so indeed let's let $f$ be an $n$-ary function symbol. Consider $h^{-1}(f(b_1, \dots, b_n))$ for $b_i \in h[A]$. Write $h(a_i) = b_i$ for all $i$. Then observe that
$$
\begin{align*}
h(h^{-1}(f(b_1, \dots, b_n))) &= f(b_1, \dots, b_n)\\
&= f(h(a_1), \dots, f(h(a_n)))\\
&=h(f(a_1, \dots, a_n)),
\end{align*}
$$
as we assumed that $h$ was a $\sigma$-homomorphism. Furthermore, as $h$ is one to one, this equation tells us that $h^{-1}(f(b_1, \dots b_n)) = f(a_1, \dots, a_n) = f(h^{-1}(b_1), \dots, h^{-1}(b_n))$. Thus, $h^{-1}$ is a $\sigma$-homomorphism and $h$ is a $\sigma$-embedding. This notation is a bit off in the case where $f$ is a $0$-ary function, i.e. a constant, but the same proof holds.
By the way, I think it's always good practice to try to break the conclusion by breaking the assumptions. That is, if we had relation symbols in $\sigma$ could we find counterexamples to this claim? Here's an example: take $\sigma$ to contain a single binary predicate $P$. Let $A$ and $B$ both equal $\mathbb N$ as sets. For the $\sigma$-structure $A$, we say that $P_A(a_1, a_2)$ iff $a_1 < a_2$. For the $\sigma$-structure $B$ we say that $P_B(b_1, b_2)$ is always true. Then the identity map $id: A \longrightarrow B$ is a $\sigma$-homomorphism and it is one to one, but it is not an embedding. Indeed, the inverse (which is still the identity) does not preserve $P$, as $P_B(1, 0)$ is true but $P_A(1, 0)$ is not.
A: Say we take two $\sigma$-structures $A$ and $B$ and $h\colon A\to B$ an injective $\sigma$-homomorphism.
Then $h(A)$ contains all constants in your signature and is closed under functions in your signature: if $x\in h(A)$, then $x=h(a)$ for some $a\in A$. If $f$ is a function symbol in your signature, then
$$f^B(x)=f^B(h(a))=h(f^A(a))$$
also belongs to $h(A)$.
So how would we go on to prove that the inverse $h^{-1}\colon h(A)\to A$ is a morphism? Well, of course it preserves the interpretation of constants. For a $1$-ary function symbol $f$, we have
$$h\circ f^A=f^B\circ h$$
so composing with $h^{-1}$ both on the left and on the right implies that
$$f^A\circ h^{-1}=h^{-1}\circ f^B$$
which means that $h^{-1}$ is also a $\sigma$-homomorphism. A similar argument holds for general $n$-ary function symbols.
But the problem is that the $\sigma$-homomorphism condition on a relation symbol $R$ (which I assume to be a binary relation just for simplicity) is that
$$(h\times h)(R^A)\subseteq R^B$$,
which only translates to
$$R^A\subseteq (h^{-1}\times h^{-1})(R^B).$$
The inclusion is on the opposite direction than the one that would be necessary for $h^{-1}$ to preserve $R$!!! That's where things could go awry.
For an specific example, take the signature $\sigma=(R)$ with only one binary relation symbols. Take your favourite set $X$ with at least two elements, and consider the two interpretations of $\sigma$ as follows:
$$A=(X,\mathrm{eq}),\qquad B=(X,\mathcal{P}(X)),$$
where "$\mathrm{eq}$" is the equality relation on $X$ and $\mathcal{P}(X)$ is the  finest relation on $X$ (everyone is related to everyone). Then the identity $A\to B$ is obviously a $\sigma$-homomorphism, but it is not a $\sigma$-isomorphism.
