Understanding an example about homomorphism

49 Views Asked by At

enter image description here

Let $X=\left\{ a,b,c\right\}$ be a set and $R=\left\{ (a,b),(a,c)\right\}$ a relation on $X$; and let $Y=\left\{ u,v\right\}$ be a set and $S=\left\{ (u,v)\right\}$ a relation on $Y$.

A homomorphism is a map $f:X\to Y$ with the property $(f(x),f(y))\in S$ whenever $(x,y)\in R$.

Any homomorphism must take $a$ to $u$ and $b$ and $c$ to $v$.

My question is: If it was take $a$ to $v$ and $b$ and $c$ to $u$ then is it homomorphism? If no, why?

1

There are 1 best solutions below

4
On BEST ANSWER

A homomorphism needs to preserve existing edges, but it has no problems adding new edges, or "merging points" if conditions are right.

Since both $b$ and $c$ are maximal elements with the same minimum as the only point below them, mapping both of them to $v$ is indeed a homomorphism.

On the other hand, if we map $a$ to $v$, and both $b$ and $c$ to $u$, then we don't have a homomorphism, since $a\mathrel{R}b$, but $v\not\mathrel{S}u$ which means $f(a)\not\mathrel{S}f(b)$. And this means that $f$ will not be a homomorphism.

You might argue that if we reverse the order then it works, and you'd be correct. And this property is sometimes called an anti-homomorphism; or an order-reversing function.