2
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – porton Sep 1 '13 at 13:13
  • $\begingroup$ @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. $\endgroup$ – Apostolos Sep 1 '13 at 13:18
  • $\begingroup$ "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 $\endgroup$ – porton Sep 1 '13 at 13:18
  • $\begingroup$ 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 $\endgroup$ – porton Sep 1 '13 at 13:25
  • $\begingroup$ @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. $\endgroup$ – Apostolos Sep 1 '13 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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