1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ An elementary embedding is in intresting cases not onto. $\endgroup$ – André Nicolas Dec 25 '14 at 14:18
  • $\begingroup$ Could someone please elaborate on this? Clearly, I've misunderstood something fundamental about this, and my book is NOT very helpful. How do these three concepts relate to each other? (From the viewpoint of logic). $\endgroup$ – JuliusL33t Dec 25 '14 at 16:00
  • $\begingroup$ Or maybe someone could recommend some reading? I'm following Shawn Hedmans A First Course In Logic, and I'm not at all satisfied $\endgroup$ – JuliusL33t Dec 25 '14 at 16:07
  • $\begingroup$ What is a literal embedding? $\endgroup$ – bof Dec 25 '14 at 18:14
  • 1
    $\begingroup$ In a language with no relation symbols except $=$, any injection from one infinite set into another is an elementary embedding. $\endgroup$ – bof Dec 25 '14 at 18:16
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is nice! Thanks! I'm starting to intuit this stuff like this: embeddings are structure-preserving in the weakest possible sense. They preserve only the rawest forms of truths about a structure, while elementary embeddings are more like "chunks" of the original structure. In the onto case, there is only one chunk to speak of, and thats the whole structure, so theyre essentially the same. Is this about right? $\endgroup$ – JuliusL33t Dec 29 '14 at 21:50
  • 1
    $\begingroup$ I'm not sure the "chunks" intuition is a good one. Speaking informally, suppose we have a map $f:A\to B$, and take a few elements $a_1,\dots,a_n$ from $A$. If $f$ is an embedding, then truths about these elements and how they relate to one-another are preserved. But if $f$ is an elementary embedding, then truths about these elements and how they relate to the rest of $A$ (or, maybe better, how they sit inside $A$) are preserved. This is what changes when you require preservation of formulas that include quantifiers. $\endgroup$ – Alex Kruckman Jan 5 '15 at 1:49
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Anent your first example, there is no elementary embedding of $\mathbb N$ into $\mathbb N+\omega$, as those two structures are not even elementarily equivalent. It works if you replace $\omega$ with $\mathbb Z$. Anent your second example, how can an isomorphism not be an elementary embedding? $\endgroup$ – bof Dec 25 '14 at 18:13
  • $\begingroup$ @bof: Sorry! I have been drinking on Christmas morning! You are correct and I have edited the post. I confused $\omega$ and $\mathbb{Z}$ and for the second topic, I meant elementary substructure, which is a different concept. $\endgroup$ – Kyle Dec 25 '14 at 18:37
  • $\begingroup$ I think it is worth noting that an isomorphism is an elementary embedding; in fact, an elementary embedding is an isomorphism iff it is onto. $\endgroup$ – tomasz Dec 26 '14 at 0:13
  • $\begingroup$ As written, your definition of isomorphism looks like the definition of homomorphism... you either need to say that $F$ is surjective or invertible, and you probably need to clarify what "preserve" means for relation symbols (i.e. preserve and reflect). Also, just a note that condition 2 in the definition of elementary embedding implies condition 1: If $a \neq b$, but $F(a) = F(b)$, then $F$ does not preserve the truth of the formula $\lnot (x = y)$ on $a$ and $b$. $\endgroup$ – Alex Kruckman Dec 26 '14 at 5:46
  • 1
    $\begingroup$ @Kyle: I still don't think your definition of isomorphism is enough: e.g. a language with a unary relation $R$, and two models with a given set $X$, in the first, the relation is identically false and the second, it is identically true. If $i$ is the identity, then $R(x) \implies R(i(x))$ is vacuously true, but $i$ is not an isomorphism. $\endgroup$ – Hurkyl Dec 26 '14 at 5:59
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Better. Still tho, I'm not sure I get it. Look at proposition 2.57: Let M and N be V-structures. If the function f : M → N is onto, then f is a literal embedding if and only if f is an elementary embedding. Now I give you two (finite) graphs, $G$ and $H$, and an surjective literal embedding $g: G \to H$. This embedding will preserve all atomic formulas, and the whole of $H$ is covered, so whatever vertices were adjacent in $G$ will be so in $H$ also, so this is a bijection, i.e. isomorphism, and an elementary embedding. Is there no difference in the finite case? only in the infinite case?? $\endgroup$ – JuliusL33t Dec 25 '14 at 21:16
  • $\begingroup$ Even in the infinite case, if $g$ is surjective then they automatically have the same cardinality, no matter how big! What the hell is the difference??? $\endgroup$ – JuliusL33t Dec 25 '14 at 21:26
  • $\begingroup$ How about this: I get that just because we have an elementary embedding, it need not hold that it is onto, but would it be true to claim that if it is an elementary embedding and is onto, then it is an isomorphism? $\endgroup$ – JuliusL33t Dec 25 '14 at 21:37
  • $\begingroup$ By the function $g$ above, i mean of course the identity function, sorry for spamming the comment section :( $\endgroup$ – JuliusL33t Dec 25 '14 at 21:44
  • $\begingroup$ @JuliusL33t - for the infinite case, consider $\mathbb Q_>$ and $\mathbb R_>$ above: the issue is exactly with cardinality : we cannot "biject" the second in the first one ... $\endgroup$ – Mauro ALLEGRANZA Dec 26 '14 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.