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 $b$ is the image of $a$ under $j$:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle \(b_1,b_2,\ldots,b_n) = (j(a_1),j(a_2),\ldots,j(a_n)\)}

then $j$ is a homomorphism. If instead:

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

then $j$ is an embedding.