Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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.

share|cite|improve this answer

Your Answer


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.