Question

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

Short answer

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

Step-by-step solution

Given

\(R\) is symmetric

Concept of Symmetric

A relation \(R\) on a set \(A\) is symmetric if \((b,a) \in R\)whenever \((a,b) \in R\).

A path in a directed graph \(G\) is a sequence of edges in \(G\).

Check the Symmetry

Given that\(R\)is symmetric.

Let\((a,b) \in {R^*}\).

\((a,b) \in {R^*}\)if there exists a path from\(a\)to\(b\)and thus there is a sequence of ordered pairs\(\left( {{s_0},{s_1}} \right) \in R\),\(\left( {{s_1},{s_2}} \right) \in R, \ldots ,\left( {{s_{j - 1}},{s_j}} \right) \in R\)with\({s_0} = a\)and\({s_j} = b\)and\(j \ge 1\).

Since\(R\)is symmetric: there is a sequence of ordered pairs\(\left( {{s_j},{s_{j - 1}}} \right) \in R,\left( {{s_{j - 1}},{s_{j - 2}}} \right) \in R, \ldots ,\left( {{s_1},{s_0}} \right) \in R\)with\({s_0} = a\)and\({s_j} = b\)and\(j \ge 1\). Thus there is a path from\(b\)to\(a\)and thus:

\((b,a) \in {R^*}\)

Since\((b,a) \in {R^*}\)whenever\((a,b) \in {R^*},{R^*}\)is symmetric

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