# Proof

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

1. Knauer Ulrich: "Diskrete Strukturen - kurz gefasst", Spektrum Akademischer Verlag, 2001