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
    I don't understand what "$F(a)\Leftrightarrow \alpha\circ f^{-1}\cap g^{-1}\circ b\neq\emptyset$" means. Let $F(a)$ *what*?2012-01-24
  • 0
    @Arturo Magidin: I clarified that $F$ is a predicate.2012-01-24
  • 0
    If there are counter-examples, I am specifically interested about finite ones.2012-01-24
  • 0
    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$?2012-01-24
  • 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.)