Proving associativity in Algebra

Question

How to proof that a specially defined Transitive Join for the relations $R \subseteq A\times B$ und $S \subseteq B\times C$ is associative? The join is defined as: $R \Join S =_\text{def} \{(a,c)\mid \text{there is a } b \in B \text{ with } (a,b) \in R \text{ and }(b,c) \in S\}. $ My question is how do you proof that $\Join$ is associative meaning that $(R \Join S) \Join T = R \Join (S \Join T)$ for $R\subseteq A\times B, S \subseteq B\times C $ and $ T \subseteq C \times D$ holds

Answer 1

The following statements are equivalent:

• $\left(a,d\right)\in\left(R\Join S\right)\Join T$

• $\exists c\in C\:\left(a,c\right)\in(R\Join S)\wedge\left(c,d\right)\in T$

• $\exists c\in C\:\exists b\in B\:\left[\left(a,b\right)\in R\wedge\left(b,c\right)\in S\right]\wedge\left(c,d\right)\in T$

• $\exists c\in C\:\exists b\in B\:\left(a,b\right)\in R\wedge\left(b,c\right)\in S\wedge\left(c,d\right)\in T$

• $\exists b\in B\:\exists c\in C\:\left(a,b\right)\in R\wedge\left(b,c\right)\in S\wedge\left(c,d\right)\in T$

• $\exists b\in B\:\left(a,b\right)\in R\wedge\exists c\in C\:\left[\left(b,c\right)\in S\wedge\left(c,d\right)\in T\right]$

• $\exists b\in B\:\left(a,b\right)\in R\wedge\left(b,d\right)\in S\Join T$

• $\left(a,d\right)\in R\Join\left(S\Join T\right)$

Answer 2

Suppose $(a,c) \in R \Join S$ and $(c,d) \in T$ (that is $(a,d) \in (R \Join S) \Join T$).

By definition, there is $b \in B$ with $(a,b) \in R$ and $(b,c) \in S$.

Since $(b,c) \in S$ and $(c,d) \in T$, we have $(b,d) \in S \Join T$.

Thus that same $b$ shows that $(a,d) \in R \Join (S \Join T)$, so $(R \Join S) \Join T \subseteq R \Join(S\Join T)$.

The reverse inclusion is shown similarly.