Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.