Proof
(related to Lemma: Composition of Relations (Sometimes) Preserves Their Left-Total Property)
Let \(A,B,C\) be sets and let let \(R_1\subseteq A\times B\) and \(R_2\subseteq B\times C\) be two left-total relations.
Case \((1)\)
- Suppose, there exist at least one tripple $(a,b,c)$ with $a\in A,$ $b\in B,$ and $c\in C$ such that $aR_1b$ and $bR_2c$.
- Since, by hypothesis \(R_1\) is left-total, we have for every \(a\in A\) that there is an element \(b\in B\) with \(aR_1b\).
- By the same argument, it follows that for every $b\in B$ there is an element \(c\in C\) with \(bR_2c\).
- Alltogether, for every $a\in A$ there is an element $c\in C$ with $a R_1 b$ and $b R_2 c$.
- From the definition of composition of relations, it follows that $(R_2\circ R_1)\subseteq A\times C$ is left-total.
Case \((2)\):
- Now suppose that such a tripple $(a,b,c)$ does not exist.
- Then the lemma is vacuously true.
∎
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
References
Bibliography
- Knauer Ulrich: "Diskrete Strukturen - kurz gefasst", Spektrum Akademischer Verlag, 2001
