I'm self-learning my way through Set theory and came across this question.
Now I have a few difficulties to gain an entry to this question.
The textbook and the lecture videos which I'm using gives no explanation about composition of relations. It just touches the basics of composition of functions (which I was already familiar from Pre-Calculus).
- What does it mean to compose two relations, in particular, a relation with its inverse?
- What is $Id_B$ in simple terms of set relations? Googling led me to wikipedia entry of Identity function, but there I am thrown to entirely new definitions like monoids, morphism etc. which looks like an intellectual leap for me at this stage.
Best Answer
Composition of relations is an operation that produces a new relation from two (or more) other relations.
To say that "x is the uncle of y" means that x is the brother of someone which in turn is the father of y.
$\text {Id}_B$ is the Identity relation on set $B$ : $\text {Id}_B = \{ (x,x) \mid x \in B \}$.
If $R: A → B$ we have that its inverse will be $R^{−1}: B → A$.
Thus, $R \circ R^{−1}: B → A → B$ (apply $R^{−1}$ first and then $R$, because it is modelled on function composition: $(g∘f)(x)=g(f(x))$) and thus it is a relation $B → B$.