1
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Keep in mind that the word "homomorphism" means different things in different contexts, and the definition you linked to is irrelevant here. I assume that you are referring to a "graph homomorphism", but is your definition of a graph homomorphism correct? I don't see that it's consistent with the wikipedia definition here. $\endgroup$ – littleO Mar 16 '18 at 20:56
  • 4
    $\begingroup$ You will go much farther in your learning if you don't jump to concluding that something is "poorly defined" or "unreliable" because you don't understand it. $\endgroup$ – symplectomorphic Mar 16 '18 at 20:57
  • 1
    $\begingroup$ The question you linked is about the definition of homomorphism between algebraic objects (where the definition given there makes sense). Here you have a different type of object, and a different definition of homomorphism. $\endgroup$ – Tobias Kildetoft Mar 16 '18 at 20:58
  • 4
    $\begingroup$ But they are not really named the same. One is called a graph homomorphism, while the other is called a group homomorphism. When the context is clear we just abbreviate both of these to homomorphism to save time. $\endgroup$ – Tobias Kildetoft Mar 16 '18 at 21:00
  • 6
    $\begingroup$ One of the miseries of life is that everybody names things a little bit wrong, and so it makes everything a little harder to understand -- Feynman The word "homomorphism" always refers to a mapping that preserves some relevant structure. What that structure is depends on context. For clarity we could avoid using "homomorphism" by itself and always say "graph homomorphism" or "group homomorphism" or "ring homomorphism", etc. But we are too lazy to be so careful, and instead we just hope the meaning is clear from context. $\endgroup$ – littleO Mar 16 '18 at 21:04
3
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ I'm pretty confident the people who answered in the other question wrote answers assuming the OP was coming from a place of more understanding. They assumed the OP was providing an example and didn't take what the OP was saying literally. $\endgroup$ – Derek Elkins Mar 17 '18 at 5:41
  • 1
    $\begingroup$ @DerekElkins: I agree with you regarding what the other answerers assumed. On this issue, I have little to go on but the OP's actual words in his question and in his comments to the question, which taken together seem to indicate that he did literally mean what he wrote regarding homomorphism, and which give no indication that he understood the correct concept of homomorphism in the category of graphs. The other answerers could of course be right in their assumptions. Nonetheless, perhaps it is equally useful to have answers which under-assume as it is to have answers which over-assume. $\endgroup$ – Lee Mosher Mar 17 '18 at 15:29
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But is there "root" homomorphism, which is a father of all the "applied" homomorphisms? Does it have definition such that I can deduce applied versions from it? $\endgroup$ – Sereja Bogolubov Mar 16 '18 at 21:17
  • $\begingroup$ No, the only possible "root homomorphism" that I can think of would be functions between sets, i.e., morphisms in the category of sets. Most common mathematical objects are constructed with underlying sets, so most morphisms (including those between groups and graphs) share the common attribute of simply being functions between sets, in addition to having other distinctive characteristics. $\endgroup$ – Arbutus Mar 16 '18 at 21:24
  • $\begingroup$ But it still confusing. I kind of understand what you saying, I do understand monoid, groups, etc. homomorphisms definitions, but the thing I can't quite get is how mathematicians deal with "structure preservation" without having common understanding of what "structure preservation" is? What if I'll say that it is sufficient to preserve just vertices of graph? It would still preserve some structure, right? So technically, it could be understood as graph's homomorphism as well, though makes no sense... $\endgroup$ – Sereja Bogolubov Mar 16 '18 at 21:30
2
$\begingroup$

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.

$\endgroup$

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.