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

Question

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:

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

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.

Answer 1

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.