Definition:Embedding (Model Theory)

From ProofWiki
Jump to navigation Jump to search


Definition

Let $\mathcal M$ and $\mathcal N$ be $\mathcal L$-structures with universes $M$ and $N$ respectively.


$j: \mathcal M \to \mathcal N$ is an $\mathcal L$-embedding if and only if it is an injective map $M \to N$ which preserves interpretations of all symbols in $\mathcal L$; that is, such that:

  • $j \left({f^\mathcal M \left({a_1, \dots, a_{n_f} }\right)}\right) = f^\mathcal N \left({j \left({a_1}\right), \ldots, j \left({a_{n_f} }\right)}\right)$ for all function symbols $f$ in $\mathcal L$ and $a_1, \dots, a_{n_f}$ in $M$
  • $\left({a_1, \ldots, a_{n_R} }\right) \in R^\mathcal M \iff \left({j \left({a_1}\right), \dots, j \left({a_{n_R} }\right)}\right) \in R^\mathcal N$ for all relation symbols $R$ in $\mathcal L$ and $a_1, \dots, a_{n_R}$ in $M$
  • $j \left({c^\mathcal M}\right) = c^\mathcal N$ for all constant symbols $c$ in $\mathcal L$.


Partial Embedding

A common method of constructing isomorphisms and elementary embeddings in proofs is to recursively define them a finite number of elements at a time. For this purpose, it is useful to have a definition of embeddings using functions which are only defined on a subset of $M$:


Let $A \subseteq M$ be a subset of $M$.


$j: A \to \mathcal N$ is a partial $\mathcal L$-embedding if and only if it is an injective map $A \to N$ which preserves interpretations of all symbols in $\mathcal L$ applied to elements of $A$; that is, such that:

  • $j \left({f^\mathcal M \left({a_1, \dots, a_{n_f} }\right)}\right) = f^\mathcal N \left({j \left({a_1}\right), \ldots, j \left({a_{n_f} }\right)}\right)$ for all function symbols $f$ in $\mathcal L$ and $a_1, \dots, a_{n_f}$ in $A$;
  • $\left({a_1, \ldots, a_{n_R} }\right) \in R^\mathcal M \iff \left({j \left({a_1}\right), \dots, j \left({a_{n_R} }\right)}\right) \in R^\mathcal N$ for all relation symbols $R$ in $\mathcal L$ and $a_1, \dots, a_{n_R}$ in $A$;
  • $j \left({c^\mathcal M}\right) = c^\mathcal N$ for all constant symbols $c$ in $\mathcal L$.


Isomorphism

$j: \mathcal M \to \mathcal N$ is an $\mathcal L$-isomorphism if and only if it is a bijective $\mathcal L$-embedding.


Automorphism

$j: \mathcal M \to \mathcal N$ is an $\mathcal L$-automorphism if and only if it is an $\mathcal L$-isomorphism and $\mathcal M = \mathcal N$.


It is often useful to talk about automorphisms which are constant on subsets of $M$. So, there is a definition and a notation for doing so:

Let $A \subseteq M$ be a subset of $M$, and let $b \in M$.


An $\mathcal L$-automorphism $j$ is an $A$-automorphism if and only if $j \left({a}\right) = a$ for all $a\in A$.

An $\mathcal L$-automorphism $j$ is an $A, b$-automorphism if and only if it is an $\left({A \cup \left\{ {b}\right\} }\right)$-automorphism; that is: $j \left({a}\right) = a$ for all $a \in A$ and also $j \left({b}\right) = b$.