Why do mathematicians understand structure preservation in a such a way?

Question

This question is about homomorphism and it's definition, which still feels kind of weird and unreliable to me.

To be more obvious, let's take graph $G = (Vertices(G), Edges(G))$. Then homomorphism of $G$ to somewhat graph $G'$ consists of two independent functions: $vrt : Vertices(G) \mapsto Vertices(G')$, $edg : Edges(G) \mapsto Edges(G')$. As such, in this particular case, homomorphism itself becomes a complicated object: it can be decomposed into some simpler primitives and thus one has to define certain rule how to apply those primitives to $G$ in order to get $G'$. Formally it looks somewhat like: $$(\forall v_G \in Vertices(G) : vrt(v_G) \in Vertices(G')) \land (\forall e_G \in Edges(G) : edg(e_G) \in Edges(G')) \tag{1}$$ Observation #1: I can't see how it follows from the homomorphism's definition. There is no $(\circ)$ given explicitly; what kind of operation is it? Which are the elements of that operation? Can someone show me why $(vrt, edg)$ definitions follow from that?

Observation #2: I see homomorphism cares not to degrade existing structure, at the same time saying literally nothing about upgrading it? Since homomorphism is complicated object on it's own right, it can preserve existing structure and add something, which does not exist in the original one. And (1) requirement from the above would hold indeed. In order to ensure no upgrading took place, one should extend (1) to: $$\text{vertices of the G did not degrade} \land \text{edges of the G did not degrade} \land \text{all the vertices of the G' came from the G} \land \text{all the edges of the G' came from the the G} \tag{2}$$ where:

• vertices of the G did not degrade = $(\forall v_G \in Vertices(G) : vrt(v_G) \in Vertices(G'))$;
• edges of the G did not degrade = $(\forall e_G \in Edges(G) : edg(e_G) \in Edges(G'))$
• all the vertices of the G' came from the G = $\not \exists v_{G'} \in vrt(G') : \forall v_G \in vrt(G) : vrt(v_G) \not = v_{G'}$
• all the edges of the G' came from the G = $\not \exists e_{G'} \in edg(G') : \forall e_G \in edg(G) : edg(e_G) \not = e_{G'}$

---

As a conclusion. I don't have any teacher to learn math, I do it only with help of the books published online and this platform. And for me it feels like homomorphism is both: 1) extraordinary important, 2) poorly defined idea. At the first sight it seems rigorous, but the deeper one dig, the sloppier it becomes. It feels like mathematicians just don't bother to redefine loosed things: whenever it comes down to somewhat specific structures, like graphs or monoid, or whatever else, homomorphism emerges not as direct consequence of the $F(g \circ f) = F(g) \bullet F(f)$, but as something intuitive, something like "we all understand that to preserve such-and-such particular structure, one has to fulfill following requirements". And yet I haven't seen "no-upgrade" requirement (observation #2), which seems quite valuable.

So, please, help me get deeper into math. What's wrong with my understanding?

Answer 1

The definition of homomorphism from your other question that you linked to is not the general definition of homomorphism. It is instead the definition of homomorphism in a very, very specific context namely: the context of a set equipped with a binary operation.

That definition DOES work for groups, because a group is a set equipped with a binary operation satisfying three basic laws: associativity, identity, and inverse. There are also other types of mathematical structures which that definition works for, for example a monoid which is a set equipped with a binary operation satisfying two laws: associativity and identity.

However, that definition DOES NOT work for graphs, because a graph is not a set equipped with a binary operation. There is no "$\circ$" nor "$\bullet$" nor any other kind of binary operator in the definition of graphs.

Your question did not include the full definition of a graph, so I'll add what's missing (which has nothing to do with binary operators): a graph $G$ is a pair of subsets $(\text{Vertices}(G),\text{Edges}(G))$ equipped with a pair of functions $i_G : \text{Edges}(G) \to \text{Vertices}(G)$ and $t_G : \text{Edges}(G) \to \text{Vertices}(G)$. Intuitively, for each $E \in \text{Edges}(G)$, the notation $i_G(E) \in \text{Vertices}(E)$ stands for the initial vertex of the edge $E$, and $t_G(E) \in \text{Vertices}(E)$ stands for the terminal vertex of the edge $E$.

If you want to define homomorphisms between graphs, then you need to define them using the natural structures of graphs, not the structures from some unrelated category of mathematics such as sets equipped with a binary operation. Here's the proper definition:

Given graphs $G,G'$, a homomorphism from $G$ to $G'$ consists of two functions $vrt : \text{Vertices}(G) \to \text{Vertices}(G')$ and $edg: \text{Edges}(G) \to \text{Edges}(G')$, which satisfy the following properties:

• For each $e \in \text{Edges}(G)$, $$i_{G'}(edg(e)) = vrt(i_{G}(e)) $$ and $$t_{G'}(edg(e)) = ver(t_G(e)) $$

In words, this says the initial vertex in $G'$ of the image of each edge $e$ of $G$ must equal the image of the initial vertex in $G$ of $e$, and the terminal vertex in $G'$ of the image of $e$ must equal the image of the terminal vertex in $G$ of $e$.

To summarize, the two functions $vrt$ and $edg$ in the definition of a graph homomorphism are not independent from each other, as your question indicates. They are constrained to preserve the existing structure of a graph. That structure has nothing to do with binary operators. Instead that structure, in a graph $G$, consists of the "initial endpoint function" $i_T(E)$ and the "terminal endpoint function" $t_G(E)$.

Answer 2

Perhaps this is only a partial answer, but it seems to me that your misunderstanding might be that the term 'homomorphism' depends on what category you're talking about. For example, graph homomorphisms refer to morphisms in the category of graphs, where as group homomorphisms refer to morphisms in the category of groups. If you could define a group structure on your graph then you could view your graph as an object in the category of groups, and then speak of group homomorphisms from your graph to other groups. But without a group structure, the term 'group homomorphism' doesn't make sense when speaking of graphs, just as the term 'group homomorphism' doesn't make sense when speaking of a general set without a group structure. The definition of morphism depends on the ambient category.

Answer 3

In general, perhaps the best advice is to be skeptical but open minded. Observe what the standard notion of morphism does for you in each mathematical context, and observe the analogies between them. In fact, the analogies are so strong that eventually people invented whole subjects to deal with them, category theory, universal algebra. But these general abstract theories are definitely not the place to start learning mathematics.

I think if you just take the examples of theories that seem to concern you at the moment, you can identify two rather different sorts: There are algebraic structures like groups, rings, modules, etc. and there are relational structures such as graphs and partially ordered sets. Perhaps it would help you to make this distinction.

For the algebraic examples, a morphism is always a map, not necessarily injective or surjective, that preserves the algebraic operation or operations. For example, for rings there are two operations $\cdot$ and $+$, and the requirement is $\phi(x\cdot y) = \phi(x)\cdot \phi(y)$ and $\phi(x + y) = \phi(x) + \phi(y)$. (Frequently, one works with rings with multiplicative identity, and requires in addition that $\phi$ take the identity of one ring to the identity of the other. You already see from this that there are choices to be made; there are different theories depending on these choices.)

For graphs, there are also many slightly different flavors: graphs with only single edges allowed, graphs with multiple edges allowed, directed graphs, and more. Each of these would require a slightly different notion of structure preserving map. The simplest flavor would be graphs with only single edges between vertices (and possibly loops). This is the flavor treated in the wikipedia article https://en.wikipedia.org/wiki/Graph_homomorphism. In this case the graph consists of the vertex set and a relation $e(x,y)$ which is symmetric but neither transitive nor reflexive. Namely $e(x, y)$ holds if there is an edge connecting vertices $x$ and $y$. Now a graph homomorphism is a map on vertices which preserves the relation: $e(x, y)$ implies $e(\phi(x), \phi(y))$.

As soon as one allows more complicated setups, say graphs with multiple edges, then one has to invent a more complicated way both to describe what a graph is and what a morphism is. But the idea should still be that edges get mapped to edges. You could just start with this intuitive idea yourself and work out how to formalize this.

Now if you really want to make an effort, you could bring the algebraic examples and the relational examples under one roof, e.g by viewing an operation as a relation, $R(x, y, z)$ holds if $x\cdot y = z$. Now the homomorphism property would translate to $R(x, y, z)$ implies $R(\phi(x), \phi(y), \phi(z))$. For me, this does absolutely nothing to help me understand groups or rings.