If $S = \{ (p, q) \in P \times P \mid \text{p is an ancestor of q}\}$, what is $S \circ S^{-1}$?

41 Views Asked by At

Suppose $S = \{ (p, q) \in P \times P \mid \text{p is an ancestor of q}\}$. What is $S \circ S^{-1}$?

To achieve the desired result, I would start by identifying what $S^{-1}$ (the inverse of $S$) is in a set notation:

$$S^{-1} = \{ (q, p) \in P \times P \mid \text{q is an ancestor of p}\}$$

We know that composition starts from the right side, in this case from $S^{-1}$ to $S$: we take the first element of each pair of the relation $S^{-1}$ and put it together with the second element of $S$, so the pairs would be from $(q, q)$, which does not make much sense, in my opinion, because it would mean:

$$S \circ S^{-1} = \{ (q, q) \in P \times P \mid \text{q is an ancestor of q} \}$$

which does not make so much sense.

Is this solution correct?

I have also a solution from some my classmates, and it's different from mine:

$$S \circ S^{−1} = \{ (p,n) \in P\times P \mid (\exists q \in P) pS^{−1}q \land qSn \}$$

$$S \circ S^{−1} = \{ (p,n) \in P\times P \mid \text{p and n have a common ancestor} \}$$

Their set notation is more complicate, but at the end it seems it makes more sense. Is this correct?

1

There are 1 best solutions below

2
On BEST ANSWER

Relation composition is defined so that

$$a\,(S\circ R)\,b\iff\exists c:(a\,R\,c\wedge c\,S\,b).$$

And converse is defined so that $a\,R^{-1}\,b\iff b\,R\,a$. Applying this to your example, we have:

$$p\,S\circ S^{-1}\,q\iff\exists n:(p\,S^{-1}\,n\wedge n\,S\,q)\iff\exists n:(n\,S\,p\wedge n\,S\,q).$$

Applying the interpretation that $p\,S\,q$ means that $p$ is an ancestor of $q$, we read this as "$p\,S\circ S^{-1}\,q\iff$ there is an $n$ such that $n$ is an ancestor of $p$ and $n$ is an ancestor of $q$", or more briefly as "$p$ and $q$ have a common ancestor". Thus your friend's solution is correct.