How to prove that $\theta_1 \vee \theta_2$ = $\theta_1 \cup (\theta_1 \circ \theta_2) \cup (\theta_1 \circ \theta_2 \circ \theta_1) \cup ...$? How to prove that $\theta_1 \vee \theta_2$ = $\theta_1 \cup (\theta_1 \circ \theta_2) \cup (\theta_1 \circ \theta_2 \circ \theta_1) \cup ...$?
This is a theorem from "Burris, Sankappanavar: A Course in Universal Algebra" (the image is below).
However, I don´t understand how this is "clear" according to the author. My questions are:

*

*Why is each of the parentheses contained in the left hand side? The $\theta_1$ is clear, but what about the relational products? If $(x,y) \in \theta_1 \circ \theta_2$ then $\exists c: (x,c) \in \theta_1, (c,y) \in \theta_2$. But how does this imply the $(x,y) \in \theta_1 \vee \theta_2$?


*How to prove the right hand side is transitive? (I have proven reflexivity and symmetry, which is trivial, but I don´t know about the transitivity.)
Thank you.

 A: Ok, so I'll sum this up in an answer.
First question.
Why is it that each of $\theta_1,\, \theta_1\circ\theta_2,\, \theta_1\circ\theta_2\circ\theta_1,\ldots$ is contained in $\theta_1\vee\theta_2$?
While it is obvious for $\theta_1$ as you recognized, let us see for $\theta_1\circ\theta_2$.
If $(a,c) \in \theta_1\circ\theta_2$ then there exist an element $b$ of the algebra such that $(a,b) \in \theta_1$ and $(b,c) \in \theta_2$.
It follows that $(a,b), (b,c) \in \theta_1\vee\theta_2$, which is, by definition, the least congruence containing both $\theta_1$ and $\theta_2$;
in particular, $\theta_1\vee\theta_2$ is transitive, whence $(a,c) \in \theta_1\vee\theta_2$.
So $\theta_1, \theta_1\circ\theta_2 \subseteq \theta_1\vee\theta_2$.
This reasoning is immediately extendable for the other cases:
for suppose that for some $n$
$$\tau_1 \circ \tau_2 \circ \cdots \circ \tau_n \subseteq \theta_1\vee\theta_2,$$
whenever $\tau_i \in \{\theta_1,\theta_2\}$ (obviously we're supposing that successive $\tau_i$ alternate between $\theta_1$ and $\theta_2$ for otherwise we could remove one element from the sequence), and suppose also that
$$(u,w) \in \tau_1 \circ \tau_2 \circ \cdots \circ \tau_n \circ \tau_{n+1}.$$
Then there exists $v$ such that
$$(u,v) \in \tau_1 \circ \tau_2 \circ \cdots \circ \tau_n \subseteq \theta_1\vee\theta_2$$
and $(v,w) \in \tau_{n+1}$;
as $\tau_{n+1}$ is either $\theta_1$ or $\theta_2$ it follows that $(v,w) \in \theta_1 \vee \theta_2$, and therefore, $(u,w) \in \theta_1\vee\theta_2$.
This concludes the proof that
$$\theta_1 \cup \theta_1\circ\theta_2 
\cup \theta_1\circ\theta_2\circ\theta_1 
\cup \theta_1\circ\theta_2\circ\theta_1\circ\theta_2 \cdots 
\subseteq \theta_1\vee\theta_2.$$
Second question.
How to prove that
$$\Theta = \theta_1 \cup \theta_1\circ\theta_2 
\cup \theta_1\circ\theta_2\circ\theta_1
\cup \theta_1\circ\theta_2\circ\theta_1\circ\theta_2 \cdots$$
is transitive?
Pick $(u,v), (v,w) \in \Theta$.
For some $n,m \geq 1$ we must have
$$(u,v) \in \tau_1 \circ \cdots \circ \tau_n$$
and
$$(v,w) \in \tau_1 \circ \cdots \circ \tau_m,$$
where each of the $\tau_i=\theta_1$ for $i$ odd and $\tau_i=\theta_2$ if $i$ is even.
Without loss of generality, we may suppose that $n$ and $m$ are even (can you see why?) and so
$$(u,w) \in (\tau_1 \circ \cdots \circ\tau_n) \circ (\tau_1 \circ \cdots \circ \tau_m) = (\theta_1 \circ \theta_2 \circ \cdots \circ \theta_2)
\circ (\theta_1 \circ \theta_2 \circ \cdots \circ \theta_2) \subseteq \Theta,$$
where the inclusion follows from composition being associative.
