Question

Suppose that the relation R is symmetric. Show that \({R^*}\) is symmetric.

Short answer

Thus, \({R^*}\) is symmetric.

Step-by-step solution

Given data

The relation \(R\) is symmetric.

Concept used of symmetricrelation

A relation \({\rm{R}}\) on a set \({\rm{A}}\) is called symmetric if \((b,a) \in R\) whenever \((a,b) \in R\), for all \(a,b \in A\).

Prove for symmetric relation

Suppose that \((a,b) \in {R^*}\); then there is a path from a to\(b\) in (the digraph for) \(R\).

Given such a path, if Ris symmetric, then the reverse of every edge in the path is also in R.

Therefore, there is a path from \(b\) to ain \(R\) (following the given path backwards).

Since \({R^*} = R \cup {R^2} \cup {R^3} \cup \ldots \cup {R^n}\), so

\(R \subseteq {R^*}\)

This means that \((b,a)\) is in \({R^*}\) whenever \((a,b)\) is in \(R\)

Hence proved.