Elementary embeddings vs isomorphisms

Question

I'm trying to get a better handle on the concepts of literal embeddings, elementary embeddings and isomorphisms, as the show up in logic. This is the problem:

It seems to me, (and is, according to my book), that literal embeddings are necessarily functions that are one-to-one. Furthermore, if the functions are onto, then the concepts of literal embeddings and elementary embeddings coincide. So if I give you a function $f: M \to N $, where $M,N$ are structures, that is literal embedding that is onto, then it is also an elementary embedding, and preserves all formulas.

Question: How is this different from the concept of isomorphisms? Isn't by definition an isomorphism between two structures a function that is onto and one to one? I'm trying to think of an example of a function that is an elementary (and literal) embedding, but not an isomorphism, but no success so far.

Thanks in advance.

Answer 1

I believe the concept which you call "literal embedding" is more frequently just called "embedding". Here's what I mean by "embedding", to be safe:

Definition: Let $M$ and $N$ be $L$-structures. A map $f:M\to N$ is an embedding if for all atomic formulas $\varphi(\overline{x})$ and $\overline{a}\in M$, $M\models \varphi(\overline{a})$ if and only if $N\models \varphi(f(\overline{a}))$.

The key facts are:

1. Every isomorphism is an elementary embedding.
2. Every elementary embedding is an embedding.
3. If an embedding is onto, then it is an isomorphism.

So for onto maps, the notions of isomorphism, embedding, and elementary embedding coincide. However, the point of the definitions of embeddings and elementary embeddings is to consider maps which are not onto.

In your comments to Mauro Allegranza's post, you ask about finite structures. It turns out that if $f:M\to N$ is an elementary embedding between finite structures $M$ and $N$, then $f$ is an isomorphism. As with many concepts of first-order logic, you have to look to infinite structures to get nontrivial examples.

Answer 2

Partial Answer: I have learned these concepts differently. Here are the definitions that I use (these definitions can be found in Chang and Keisler).

Elementary Embedding: Suppose $M$ and $N$ are $\mathscr{L}$-structures. Then $F$ is an elementary embedding from models $M \to N$ if

1) $F$ is injective

2) For any $\varphi(\bar{x})$ in $\mathscr{L}$ with $n$ free variables, we have that if $M \models \varphi(a_1,...,a_n)$, then $N \models \varphi(f(a_1),...,f(a_n))$.

Example: Consider $\mathbb{N}$ and $\mathbb{N+ Z}$ in the language $\mathscr{L}=\{<\}$. Letting $f=id_{\mathbb{N}}$, we obtain an elementary embedding of $\mathbb{N}$ into $\mathbb{N + Z}$.

Isomorphism: Suppose $M$ and $N$ are $\mathscr{L}$ structures. Then $F$ is an isomorphism iff $F$ is a bijection which satisfies the following:

1) for each $n-placed$ relation $R$ of $M$ and the corresponding relation $R'$ in $N$, we have $R(a_1,...,a_n)$ if and only if $R'(f(a_1),...,f(a_n))$

2) For each $m-$placed function $G$ of $M$ and corresponding function symbol $G'$ in $N$, we have $f(G(a_1,...,a_n))=G'(f(a_1),...,f(a_m))$

3) For each constant $c$ in $M$ and corresponding constant symbol $c'$ in $N$ we have that $f(c)=c'$.

Example: Consider $\mathbb{Z}$ and $2\mathbb{Z}$ in the language $\mathscr{L}=\{+,<\} $. Notice that there is an isomorphism $F: \mathbb{Z} \to 2\mathbb{Z}$ defined by $F(x)=2x$. However, $2\mathbb{Z}$ is not an elementary substructure of $\mathbb{Z}$ (which is another important topic).

Remark: I have always viewed Elementary Embeddings as (strong) injective homomorphisms. I've never heard of Elementary Embeddings as onto functions. I actually have never heard of literal embeddings. I hope this helps. If you would like more clarification/examples, just ask.

Answer 3

Rif to Shawn Hedman, A first course in logic : An Introduction to Model Theory, Proof Theory, Computability, and Complexity (2004), page 80.

I think there are some misprints ...

Literals are defined for propositional calculus [page 28] :

Definition 1.51 A literal is an atomic formula or the negation of an atomic formula [...].

For first order logic, see the Definition 2.1 of atomic formula [page 55].

Referring to Example 2.51, page 80, they are graphs [see page 66]; thus, the only atomic formulae are like $R(x,y)$ where the relation $R$ express the fact that vertices $x,y$ are adjacent.

According to :

Definition 2.49 Let $\mathcal V$ be a vocabulary and let $M, N$ be $\mathcal V$-structures. A function $f : M \to N$ preserves the $\mathcal V$-formula $\varphi(\overline x)$ if, for each tuple $\overline a$ of elements in $M$, $M \vDash \varphi(\overline a)$ implies $N \vDash \varphi(f(\overline a))$.

In the example above, we have to correct two misprints : in the formulae defining $g : M \to N$ we have to replace $f$ with $g$ and the final statement must be : Then $f$ is a literal embedding and $g$ is not.

You can check that if $M \vDash R(a_1,a_2)$, then $N \vDash R(f(a_1), f(a_2))$, for any $a_1,a_2 \in M$.

For $g$ instead, we have that $R(B,C)$ holds in $M$, while $R(e,d)=R(g(B), g(C))$ does not hold in $N$, because $B,C$ are adjacent in graph $M$ while $e,d$ are not adjacent in $N$.

For the relation between the three concepts in issue, consider Example 2.52 :

Let $id : \mathbb N_< \to \mathbb Z_<$ be the identity function defined by $id(x) = x$. This is a literal embedding.

In the language with the only binary predicate $<$, the atomic formulae are like $x < y$, and it is true that if $\mathbb N_< \vDash n < m$, then $\mathbb Z_< \vDash n < m$.

Since $\mathbb N_< \vDash ¬∃x(x < 0)$ and $\mathbb Z_< \vDash ∃x(x < 0)$ this embedding does not preserve the formula $¬∃x(x < y)$, and so it is not an elementary embedding [in $\mathbb N$ there are no numbers less than $0$, while in $\mathbb Z$ we have that $-1 < 0$].

The identity function from $\mathbb Q_<$ to $\mathbb R_<$, on the other hand, is an elementary embedding [this will be proved in Chapter 5]

but it is not an isomorphism, because the two structure have not the same cardinality.