(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
up vote 1 down vote accepted

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

Hope this helps.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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