An elementary problem about binary relations

63 Views Asked by At

I am now trying to solve a research problem. I present its elementary special case so that you can participate in my research.

Find binary relations $f$ and $g$ on a set $U$ such that the following does not hold: $g\supseteq g\circ f\circ\overline{f^{-1}}$ (or prove that there are no such relations).

Here as usually $\circ$ is composition of binary relations: $q\circ p = \{ (x,z) \mid \exists y: (x,y)\in p,(y,z)\in q \}$, $p^{-1} = \{ (y,x) \mid (x,y)\in p \}$.

2

There are 2 best solutions below

0
On BEST ANSWER

Take both $f$ and $g$ to be equality on $U$; then $\langle x,y\rangle\in g\circ f\circ\overline{f^{-1}}$ iff there are $u,v\in U$ such that $x\ne u=v=y$, so $g\circ f\circ\overline{f^{-1}}=\overline g\nsubseteq g$.

0
On

I think that relation doesn't exist, cause $g\circ f\circ\overline{f^{-1}}\Leftrightarrow \{(a,d):\exists b,c:(a,b)\in \overline{f^{-1}} \wedge (b,c) \in f \wedge (c,d) \in g \} $ this means that, $dom(g) $ on right side is subset $dom(g) $ on left side.

$g\circ f\circ\overline{f^{-1}} \subset g$ because $g"\{f\circ\overline{f^{-1}}\} \subset g$