0
$\begingroup$

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$?

  • 0
    @Arturo Magidin: The first. I updated the question.2012-01-24

1 Answers 1

1

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