Let $\Phi\subseteq (A\times A)\times(A\times A)$, $F_0,F_1\subseteq A\times A$ (for some set $A$) be binary relations.

I will denote $\pi_0$ and $\pi_1$ the projections of a cartesian product of sets.

Do inequalities $\pi_0\circ\Phi \subseteq F_0\circ\pi_0$ and $\pi_1\circ\Phi \subseteq F_1\circ\pi_1$ imply existence of a binary relation $\Psi\supseteq\Phi$ (we also require $\Psi\subseteq (A\times A)\times(A\times A)$) such that $\pi_0\circ\Psi = F_0\circ\pi_0$ and $\pi_1\circ\Psi = F_1\circ\pi_1$?

If yes, is this $\Psi$ unique?

Remark: For binary relations $f$ and $g$ I define the binary relation $g\circ f$ by the formula:

$(x,z)\in g\circ f \Leftrightarrow \exists y: ((x,y)\in f\wedge(y,z)\in g)$.

• What do mean $\pi_0\Phi$ and $\Phi\pi_0$? What difference is between them? – Boris Novikov Aug 31 '13 at 19:31
• $\pi_0\circ\Phi$ is applying $\Phi$ first and $\pi_0$ then. $\Phi\circ\pi_0$ is applying $\pi_0$ first and $\Phi$ then – porton Aug 31 '13 at 19:40
• @BorisNovikov: Note that $\Phi$ may be a multivalued function – porton Aug 31 '13 at 19:41
• @BorisNovikov: I've added the definition to my question – porton Aug 31 '13 at 19:46
• OK, but $\pi_0$ is not a binary relation. – Boris Novikov Aug 31 '13 at 19:53

No, such a set does not always exist. Here's a counterexample: Let $A=2$, let $F_0=\{(0,1)\}$ and $F_1=\{(0,1)\}$ and let $\Phi=\varnothing$. Then $((1,0),1)\in F_1\circ\pi_1$. If there is such a $\Psi$ then $((1,0),1)\in\pi_1\circ\Psi$, i.e. there is some $n\in 2$ such that $((1,0),(n,1))\in\Psi$. Then $((1,0),n)\in\pi_0\circ\Psi$, hence $((1,0),n)\in F_0\circ\pi_0$. Then $(1,n)\in F_0$ a contradiction.

A sufficient condition so that this set exists is that for every $a\in A$ there are $b,c\in A$ such that $(a,b)\in F_0$ and $(a,c)\in F_1$. Indeed if that is the case let $$\Psi=\{(a,b,c,d) : (a,c)\in F_0\land (b,d)\in F_1\}.$$ If $(a,b,c)\in\pi_0\circ\Psi$ then there is some $d$ such that $(a,b,c,d)\in\Psi$, hence $(a,c)\in F_0$ and thus $(a,b,c)\in F_0\circ\pi_0$. On the other hand if $(a,b,c)\in F_0\circ\pi_0$ then $(a,c)\in F_0$. Since by the assumption there is some $(b,d)\in F_1$, $(a,b,c,d)\in\Psi$ and hence $(a,b,c)\in\pi_0\circ\Psi$. In fact this is also a necessary condition - to see this notice how the above counterexample worked.

I may later add some stuff regarding the uniqueness.

Edit: Even if this set exists it needs not be unique. The counterexample is the following: Let $A=2$, $F_0=F_1=\{(1,0),(1,1),(0,0)\}$ and $\Phi=\varnothing$. Then one can notice that if $\Psi$ is the set I give above then $\Psi'=\Psi\setminus\{(1,1,1,1)\}$ also works.

• Please make your explanation more clear by adding parentheses: Whether $(1,0,1)$ is $((1,0),1)$ or $(1,(0,1))$? It's hard to understand without parentheses – porton Sep 1 '13 at 13:13
• @porton: Parentheses are irrelevant. Either way how can it be possible, following your definitions that it is $(1(0,1))$? You have $F_1\circ\pi_1\subseteq(A\times A)\times A$. But I can add them if you want. I just thought they'd add noise. – Apostolos Sep 1 '13 at 13:18
• "I may later add some stuff regarding the uniqueness." If existence of $\Psi$ is not guaranteed then there is no reason to invest time in checking uniqueness – porton Sep 1 '13 at 13:18
• I wanted this to work for every possible $F_0$, $F_1$ (at least for finite sets where this toy problem coincides with a real research). If for some $F_0$, $F_1$ it does not work, the result is negative and there are no reason to continue this research – porton Sep 1 '13 at 13:25
• @porton: I added the parentheses. If I find a simple argument regarding the uniqueness I'll add it in case someone who sees this question is curious about that. – Apostolos Sep 1 '13 at 13:27