User:Zero sharp/Maps between structures

Maps between structures

Fix a language, $L$ and let $M$ and $N$ be two $L$-structures. For symbols from the language, such as a constant $c$, let $c^{M}$ be the interpretation of $c$ in $M$ and similarly for the other classes of symbols (functions and relations).

A map $j$ from the domain of $M$ to the domain of $N$ is a homomorphism if the following conditions hold:

1. for every constant symbol $c\in L$, we have $j(c^{M})=c^{N}$.
2. for every n-ary function symbol $f\in L$ and $a_{1},\ldots ,a_{n}\in M^{n}$, we have $j(f^{M}(a_{1},\ldots ,a_{n}))=f^{N}(j(a_{1}),\ldots ,j(a_{n}))$,
3. for every n-ary relation symbol $R\in L$ and $a_{1},\ldots ,a_{n}\in M^{n},$ we have $M\models R(a_{1},\ldots ,a_{n})\Rightarrow N\models R(j(a_{1}),\ldots ,j(a_{n}))$,

If in addition, the map $j$ is injective and the third condition is modified to read:

for every n-ary relation symbol $R\in L$ and $a_{1},\ldots ,a_{n}\in M^{n},$ we have $M\models R(a_{1},\ldots ,a_{n})\Leftrightarrow N\models R(j(a_{1}),\ldots ,j(a_{n})),$

then the map $j$ is an embedding (of $M$ into $N$).

Equivalent definitions of homomorphism and embedding are:

If for all atomic formulas $\phi$ and sequences of elements from $M$, ${\bar {a}}=(a_{1},a_{2},\ldots ,a_{n})$

$M\models \phi [{\bar {a}}]\Rightarrow N\models \phi [{\bar {b}}]$

where ${\bar {b}}$ is the image of ${\bar {a}}$ under $j$:

${\bar {b}}=(b_{1},b_{2},\ldots ,b_{n})=(j(a_{1}),j(a_{2}),\ldots ,j(a_{n}))=j({\bar {a}})$

then $j$ is a homomorphism. If instead:

$M\models \phi [{\bar {a}}]\Leftrightarrow N\models \phi [{\bar {b}}]$

then $j$ is an embedding.