Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.