# An equation with arbitrary binary relations

Let $f$, $g$, and $b$ are binary relations (on some set $\mho$).

Let the predicate $F$ be defined by the formula $F(a)\Leftrightarrow (a\circ f^{-1})\cap (g^{-1}\circ b)\ne\emptyset$ for every binary relation $a$ on $\mho$.

Does it necessarily exist a binary relation $z$ such that $F(a)\Leftrightarrow a\cap z\ne\emptyset$ for every $a$?

-
I don't understand what "$F(a)\Leftrightarrow \alpha\circ f^{-1}\cap g^{-1}\circ b\neq\emptyset$" means. Let $F(a)$ what? – Arturo Magidin Jan 24 '12 at 21:22
@Arturo Magidin: I clarified that $F$ is a predicate. – porton Jan 24 '12 at 21:24
If there are counter-examples, I am specifically interested about finite ones. – porton Jan 24 '12 at 21:26
Do you mean $(a\circ f^{-1})\cap (g^{-1}\circ b)\neq\varnothing$, or do you mean that $a\circ(f^{-1}\cap g^{-1})\circ b\neq\varnothing$? – Arturo Magidin Jan 24 '12 at 21:37
@Arturo Magidin: The first. I updated the question. – porton Jan 24 '12 at 21:40

Take $z=g^{-1}\circ b\circ f$.
If $a\cap z\neq\varnothing$, then there exist $x,y\in \mho$ with $(x,y)\in a$, and there exist $z,w\in\mho$ such that $(x,z)\in g^{-1}$, $(z,w)\in b$, and $(w,y)\in f$. Then $(x,y)\in a$ and $(y,w)\in f^{-1}$, so $(x,w)\in a\circ f^{-1}$; likewise, $(x,z)\in g^{-1}$ and $(z,w)\in b$, so $(x,w)\in g^{-1}\circ b$. Hence, $(a\circ f^{-1})\cap (g^{-1}\circ b) \neq \varnothing$.
Conversely, if $(c,d)\in (a\circ f^{-1})\cap (g^{-1}\circ b)$, then there exist $r,s\in\mho$ such that $(c,r)\in a$, $(r,d)\in f^{-1}$, $(c,s)\in g^{-1}$, and $(s,d)\in b$. Hence $(d,r)\in f$, $(c,d)\in g^{-1}\circ b$, so $(c,r)\in g^{-1}\circ b\circ f$; since $(c,r)\in a$, we have $a\cap g^{-1}\circ b\circ f\neq\varnothing$.
Hence, $a\cap z\neq\varnothing$ if and only if $(a\circ f^{-1})\cap(g^{-1}\circ b)\neq\varnothing$.
(If by $h\circ k$ you mean all pairs $(x,y)$ such that there exists $z$ with $(x,z)\in k$, $(z,y)\in h$, then the argument above should still work with the appropriate corrections.)