$ R$ is left-total if and only if $ \operatorname{Id}_A \subseteq R \circ R^{-1} $

56 Views Asked by At

Proof:
$$R\;\text{ is left-total } \Longleftrightarrow \operatorname{Id}_A \subseteq R \circ R^{-1} $$

$R \subseteq A \times A $
$ R \circ R^{-1} = \{(a,c) \mid \exists b \in A: aRb\; \text{ and } \; bR^{-1}c \} $

This is the third part of this exercise. The first were similar, where you had to prove something if and only if R is transitive. I managed to prove it but I'm struggling with the assignment above quite a bit.
Also could not find anything online, but because I'm German and my assignment is in German, I might not have been able to translate it correctly to find what I need.

1

There are 1 best solutions below

4
On BEST ANSWER

I guess that $R$ left-total means: for every $a\in A$, there exists $b\in A$ such that $(a,b)\in R$.

Suppose $R$ satisfies $\mathit{Id}_A\subseteq R\circ R^{-1}$; then, for every $a\in A$, $(a,a)\in R\circ R^{-1}$, so there exists $b\in A$ with $(a,b)\in R$ and $(b,a)\in R^{-1}$.

In particular $(a,b)\in R$. Thus $R$ is left-total.

Conversely, suppose $R$ is left-total. Take $a\in A$: you want to prove that $(a,a)\in R\circ R^{-1}$. By assumption, there exists $b\in A$ such that $(a,b)\in R$.

Then $(a,b)\in R$ and $(b,a)\in R^{-1}$, so…