2
$\begingroup$

Here are some definitions that I found in some lecture notes about mathematical logic:

Definition 1. Given two models M and M', an isomorphism of M into M' is a function h such that h is a homomorphism of M into M' and h is one-to-one.

A homomorphism is defined as follows:

Definition 2. Given two models M and M', a homomorphism of M into M' is a function h that maps M into M' such that h preserves the relations and functions and such that for each individual constant a, h([a]M) = [a]M'.

But according to my previous readings in mathematical logic definition 2 is the definition of an isomorphism, not that of a homomorphism!

The lecture notes also include the following definition:

definition 3: Two models M and M' are isomorphic iff there is an isomorphism of M onto M', that is, an isomorphism that maps M onto M'.

But I thought that in definition 1 M and M' can be called isomorphic!

I'm getting very confused about the definition of a homomorphism, an isomorphism and related notions. Could someone help me getting out of trouble?

Thank you so much!

Fish

$\endgroup$
  • 1
    $\begingroup$ First, you should learn to use $\LaTeX$ on this site via MathJax. It's hard to know how to interpret things like h([a]M). Presumably that's suppose to be something like $h(a^M)$? $\endgroup$ – Alex Kruckman Mar 3 '17 at 20:53
  • 1
    $\begingroup$ Second, Definition 2 is imprecise: what does it mean exactly that $h$ preserves the relations? Let's say $R$ is a binary relation. Do we require that $M\models R(a,b)$ implies $M'\models R(h(a),h(b))$? Or, stronger, that $M\models R(a,b)$ if and only if $M'\models R(h(a),h(b))$? $\endgroup$ – Alex Kruckman Mar 3 '17 at 20:56
  • $\begingroup$ I'm sorry about the symbols but I can't use Latex (in general, not only on this site). I should definitely learn! I know that definition 2 is imprecise but it's my fault (I had to shorten it because there were so many symbols!). $\endgroup$ – Fishermansfriend Mar 4 '17 at 13:17
  • $\begingroup$ I have a complementary worry: in the same lecture notes the definitions above are followed by this theorem: If h is an isomorphism of M onto M', s is an assignment in M and s' is an assignment in M' such that for every variable x, [x]M',s'= h([x]M,s), then s satisfies a formula A iff s' satisfies a formula A. Would this theorem hold also for a homomorphism of M into M'? $\endgroup$ – Fishermansfriend Mar 4 '17 at 13:32
3
$\begingroup$

You're right that these definitions are confusing. Is it possible that they've been translated from another language? It seems to me that Definition 1 is defining what I would call an embedding (though missing the condition of reflecting isomorphisms - unless that's contained in Definition 2). Definition 2 is defining homomorphism, though imprecisely, as I noted in my comment, and Definition 3 is defining isomorphism. Here are the proper/standard definitions:

Let $A$ and $B$ be $L$-structures, and let $h\colon A\to B$ be a function.

$h$ is a homomorphism if:

  1. $h$ preserves constants: For every constant symbol $c$ in $L$, $h(c^A) = c^B$.
  2. $h$ preserves functions: For every $n$-ary function symbol $f$ in $L$, and for all $a_1,\dots,a_n\in A$, $h(f^A(a_1,\dots,a_n)) = f^B(h(a_1),\dots,h(a_n))$.
  3. $h$ preserves relations: For every $n$-ary relation symbol $R$ in $L$, and for all $a_1,\dots,a_n\in A$, if $(a_1,\dots,a_n)\in R^A$, then $(h(a_1),\dots,h(a_n))\in R^B$.

$h$ is an embedding if:

  1. $h$ is a homomorphism.
  2. $h$ is injective.
  3. $h$ reflects relations: For every $n$-ary relation symbol $R$ in $L$, and for all $a_1,\dots,a_n\in A$, if $(h(a_1),\dots,h(a_n))\in R^B$, then $(a_1,\dots,a_n)\in R^A$.

[Note that reflecting relations is the dual of preserving relations. Note also that injectivity is equivalent to reflecting $=$; for all $a,b\in A$, if $h(a) = h(b)$, then $a = b$. Of course, all functions preserve $=$.]

$h$ is an isomorphism if:

  1. $h$ is an embedding.
  2. $h$ is surjective.

Equivalently, $h$ is an isomorphism if it is an invertible homomorphism (whose inverse is also a homomorphism).

$A$ and $B$ are isomorphic if there is an isomorphism $h\colon A\to B$.

Note that if $h$ is an embedding, then $A$ is isomorphic to a substructure of $B$ (namely the image of $h$).


In the comments you ask:

I have a complementary worry: in the same lecture notes the definitions above are followed by this theorem: If h is an isomorphism of M onto M', s is an assignment in M and s' is an assignment in M' such that for every variable x, [x]M',s'= h([x]M,s), then s satisfies a formula A iff s' satisfies a formula A. Would this theorem hold also for a homomorphism of M into M'?

No: Consider the language $L = \{\leq\}$, and let $h$ be the inclusion of the linear order $(\mathbb{N},\leq)$ into the linear order $(\mathbb{Z},\leq)$. Then $h$ is a homomorphism (even an embedding), but it does not preserve truth of the formula $\varphi(x) = \forall y\, x\leq y$. Indeed, $\mathbb{N}\models \varphi(0)$, but $\mathbb{Z}\not\models \varphi(h(0))$.

A map which preserves and reflects truth of formulas is called an elementary embedding, and the theorem in your notes says that every isomorphism is an elementary embedding (in the language of your notes, every isomorphism of $M$ onto $M'$ is an elementary embedding, but the example above shows that an "isomorphism of $M$ into $M'$", i.e. an embedding, need not be an elementary embedding).

However, there are elementary embeddings which are not isomorphisms; for example, the inclusion $(\mathbb{Q},\leq)\to (\mathbb{R},\leq)$ is an elementary embedding which is not surjective.

To sum up:

homomorphisms $\subseteq$ embeddings $\subseteq$ elementary embeddings $\subseteq$ isomorphisms

homomorphisms preserve atomic formulas, embeddings preserve and reflect atomic formulas, elementary embeddings preserve and reflect all formulas, and isomorphisms do all of the above and are bijective. In between homomorphisms and elementary embeddings, you can have fun defining many other classes of maps by picking a class of formulas and asking that the maps preserve/reflect/both the formulas in that class.

$\endgroup$
  • 1
    $\begingroup$ I suspect the question is quoting from a rather old source. In olden times, "isomorphism" was often used to mean what is now called "embedding", i.e., isomorphisms were not required to be surjective. $\endgroup$ – Andreas Blass Mar 3 '17 at 23:46
  • $\begingroup$ @AndreasBlass That's very interesting! I've never seen it used that way, but maybe I haven't been reading enough historical sources. $\endgroup$ – Alex Kruckman Mar 3 '17 at 23:59
  • $\begingroup$ One advantage of being old is that what others call historical sources include the textbooks that I learned from. In this case, Zariski & Samuel's "Commutative Algebra," which was one of the textbooks for the algebra class I took in my first semester of graduate school (fall, 1966), distinguishes between "isomorphisms into" and "isomorphisms onto". (Of course two structures are called isomorphic only when there's an isomorphism onto.) $\endgroup$ – Andreas Blass Mar 4 '17 at 0:25
  • $\begingroup$ @Alex Kruckman If I asked about my "complementary worry" (cf. the comment above) it's because I have some other lecture notes (from the same author) where it is said that the theorem "i'm worried about" holds for what you define as being an embedding (but with no "reflects relations" condition). My author (who in these other lecture notes writes in Italian) uses the expression "immersione isomorfa". All this is quite puzzling! $\endgroup$ – Fishermansfriend Mar 4 '17 at 18:20

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.