Systematizing graph morphisms

Question

Trying to systematize possible notions of graph morphisms I came about the following classification:

A morphism $f$ which sends a graph $G$ to another graph $G'$ is – first of all – supposed to be a function $f:V_G\rightarrow V_{G'}$ from the vertex-set of $G$ to the vertex-set of $G'$, that has to fulfill one or more conditions of the form

$$\phi(x,y) \rightarrow \phi(x',y')$$

or of the form

$$\phi(x',y') \rightarrow \phi(x,y)$$

Here $\phi(\cdot,\cdot)$ is either

• $\cdot = \cdot$
• $R(\cdot,\cdot)$, that means "$\cdot$ is related to $\cdot$",
• a negation of one of the former
• or any formula with two free variables of the first-order language with signature $\lbrace R, = \rbrace$ (called appropriate formula)

$\phi(x,y) \rightarrow \phi(x',y')$ is to be read

$$(\forall x,y \in V_G)\ \phi(x,y) \rightarrow \phi(f(x),f(y))$$

which is equivalent to

$$(\forall x,y \in V_{G})\ \phi(x,y)\rightarrow (\exists x',y' \in V_{G'})\ \phi(x',y') \wedge f(x)=x' \wedge f(y)=y'$$

$\phi(x',y') \rightarrow \phi(x,y)$ instead is to be read

$$(\forall x',y' \in V_{G'})\ \phi(x',y')\rightarrow (\exists x,y \in V_G)\ \phi(x,y) \wedge f(x)=x' \wedge f(y)=y'$$

Now look at the following specific restrictions:

1. $x\neq y \rightarrow x' \neq y'$ ($f$ is injective)
2. $x'=y' \rightarrow x = y$ ($f$ is surjective)
3. $R(x,y) \rightarrow R(x',y')$ ($f$ is a weak homomorphism)
4. $R(x',y') \rightarrow R(x,y)$ ($f$ is a strong homomorphism)
5. $x=y \rightarrow x' = y'$ ($f$ is a function)
6. $x'\neq y' \rightarrow x \neq y$ ($f$ is bijective)

The last two conditions seem to be unnecessary, i.e. definable.

Combinations of the other ones yield:

• embeddings: strong + injective

• elementary embeddings: for every appropriate formula $\phi$

$$\phi(x,y) \rightarrow \phi(x',y')$$

which implies for every appropriate formula $\phi$

$$\phi(x',y') \rightarrow \phi(x,y)$$

I would like to learn to what extent this classification is complete.

Answer 1

First of all, this classification can be done for any first order language and is not special to graphs. I think your interpretation of $\phi(x', y') \to \phi(x, y)$ is a bit unnatural since it implies the existence of preimage whenever $\phi(x', y')$ holds.

You can do the classification like this. First, you deal only with functions. The function can of course be injective, surjective, or bijective. Then you can look for “structure preservation”. We'll say that $f$ preserves the operation $O$ of arity $n$ if $f(O(x_1, … x_n)) = O(f(x_1), … f(x_n))$. And $f$ preserves the relation $R$ of arity $n$ if $R(x_1, …, x_n) \implies R(f(x_1), …, f(x_n))$. That's your condition 3. And $f$ reflects the relation $R$ if $R(f(x_1), …, f(x_n)) \implies R(x_1, …, x_n)$. That's like your condition 4. but does not force you to have preimages of related elements of the codomain. Also note that there is no difference between preservation and reflection of an operation (and that's why homomorphisms of algebraic structures ale always strong, so bijective homomorphism is an isomorphism).

A function between two first order structures of the same type is a homomorphism if it preserves all operations and relations. And it's a strong homomorphism if it also reflects the relations (your condition 4. doesn't imply preservation of R). It's an embedding if it's injection and strong homomorphism and isomorphism if it's bijective and strong homomorphism (that's equivalent to categorical notion of isomorphism since its inverse exists). Yes, and elementary embedding mean injection which preserves all parametric formulas (which implies being homomorphism if = is in the language). Also you can say endomorphism for homomorphism when domain and codomain is the same and automorphism for isomorphism in that case. Sometimes injective homomorphism can be called monomorphism and surjective homomorphism can be call epimorphism, but these notions differ from categorical ones in general.