# About binary relations under certain conditions and their composition

(I have edited it. The previous version was with errors.)

Let $A$ be a set.

Let $\pi_0$, $\pi_1$ be projections from $A\times A$.

Let $F_0$, $F_1$, $G_0$, $G_1$ be binary relations on $A$.

Let $\Phi_A$ be the maximal binary relation in $(A\times A)\times(A\times A)$ such that $\pi_0\circ\Phi_A\subseteq F_0\circ\pi_0$ and $\pi_1\circ\Phi_A\subseteq F_1\circ\pi_1$.

Let $\Phi_B$ be the maximal binary relation in $(A\times A)\times(A\times A)$ such that $\pi_0\circ\Phi_B\subseteq G_0\circ\pi_0$ and $\pi_1\circ\Phi_B\subseteq G_1\circ\pi_1$.

Prove (or disprove) that $\Sigma=\Phi_B\circ\Phi_A$ is the maximal binary relation on $A$ such that $\pi_0\circ\Sigma\subseteq G_0\circ F_0\circ\pi_0$ and $\pi_1\circ\Sigma\subseteq G_1\circ F_1\circ\pi_1$.

-
What do you mean by $\circ$ above? If you meant relation-composition then I guess there's some type problem above: $\pi_0 \circ \Phi_A$ should be a relation from $A$ to $A$ (a binary relation in $A$) while $F_0 \circ \pi_0$ should be a relation from $A\times A$ to $A$ hence one cannot be a subset of the other one, because one is a set of ordered pairs while the other one is second is a set of ordered triples. – Giorgio Mossa Sep 6 '13 at 13:59
By $\circ$ I mean relation-composition. I've edited the type of relations – porton Sep 6 '13 at 14:21
To prove that $\pi_0\circ\Phi_B\circ\Phi_A\subseteq G_0\circ F_0\circ\pi_0$ and $\pi_1\circ\Phi_B\circ\Phi_A\subseteq G_1\circ F_1\circ\pi_1$ is trivial. The hard part is to prove maximality – porton Sep 6 '13 at 14:28
I've found a more inspiring proof for this. It follows from the formula $\Sigma=( \pi_0^{- 1} \circ F_0 \circ \pi_0) \cap ( \pi_1^{- 1} \circ F_1 \circ \pi_1)$ (I'm too busy now to post a full proof). – porton Sep 6 '13 at 18:19

Ok, for start let's try to understand what should be a maximal relation such that $\pi_0 \circ R \subseteq F_0 \circ \pi_0$ and $\pi_1 \circ R \subseteq F_1 \circ \pi_1$.
If $R$ is a relation that satisfies the condition above then if $((x,y),(a,b)) \in R$ we have $(x,a) \in F_0$ and $(y,b) \in F_1$. The maximal relation which satisfies this property is the $\Phi_A=\{((x,y),(a,b)) \mid (x,a) \in F_0 \land (y,b) \in F_1\}$. Similarly $\Phi_B = \{((x,y),(a,b)) \mid (x,a) \in G_0 \land (y,b) \in G_1\}$, and $\Sigma = \{((x,y),(a,b)) \mid (x,a) \in G_0 \circ F_0 \land G_1 \circ F_1\}$ Now a simple computation proves that $\Phi_B \circ \Phi_A = \{((x,y),(a,b)) \mid \exists (z,w) \ ((x,y),(z,w)) \in \Phi_A \land ((z,w),(a,b)) \in \Phi_B\}$ which implies (by the construction of $\Phi_A$ and $\Phi_B$) that $\Phi_B \circ \Phi_A$ is the set
$$\{((x,y),(a,b)) \mid \exists (z,w) \ (x,z) \in F_0 \land (y,w) \in F_1 \land (z,a) \in G_0 \land (w,b) \in G_1\}=\{((x,y),(a,b)) \mid (x,a) \in G_0 \circ F_0 \land (y,b) \in G_1 \circ F_1\}$$
Which is exactly the set $\Sigma$ so $\Sigma= \Phi_B \circ \Phi_A$.