I have difficulties understanding what is exactly the relations $\leftrightarrow$ (symmetric closure) (and friends: $\stackrel{+}{\leftrightarrow}$ (transtive symmetric closure), $\stackrel{*}{\leftrightarrow}$ (reflexive transtive symmetric closure))

Could you confirm whether I am right or otherwise tell me why I am not ?

Let the following graph describe the relations $\rightarrow$ and $\leftarrow$ (ie. $~\rightarrow\stackrel{{}^{-1}}{}$):


Therefore I would say that logically :

  1. $ \rightarrow~=~\{ (0,1)~;~(1,2) \}$
  2. $ \leftarrow~=~\{ (3,2) \}$
  3. $ \leftrightarrow~=~ \{ (0,1)~;~(1,2)~;~(3,2) \} $
  4. $ \stackrel{+}{\leftrightarrow}~=~\{ (0,1)~;~(1,2)~;~(0,2)~;(3,2) \} $
  5. $ \stackrel{*}{\leftrightarrow}~=~ \{ \{0,1\}~;~\{0,2\}~;~\{0,3\}~;~\{1,2\}~;~\{1,3\}~;~\{2;3\} \} $
  6. $ \rightarrow~\subseteq~\leftrightarrow~\subseteq~\stackrel{+}{\leftrightarrow}~\subseteq~\stackrel{*}{\leftrightarrow} $
  7. $ \leftarrow~\subseteq~\leftrightarrow~\subseteq~\stackrel{+}{\leftrightarrow}~\subseteq~\stackrel{*}{\leftrightarrow} $

What is the most confusing to me is 3. that states that $(1,3) \notin \leftrightarrow $.

Notation: $\{a,b\}$ expands to $(a,b)~;~(b,a) $


Okay, first of all let me say something about the relationship between graphs and relations. You have given the graph $$0 \rightarrow 1 \rightarrow 2 \leftarrow 3,$$ and a graph is not a relation, and your question seems to show some confusion about this relationship. We can interpret a graph as a relation (and conversely, when given a relation, we can interpret it as a graph) by creating a relation $R$ such that $(a,b) \in R$ whenever $a \rightarrow b$. So given your graph, the corresponding relation is $$R = \{(0,1),(1,2),(3,2)\},$$ which is the relation you have called $\leftrightarrow$.

Now, what is the symmetric closure of $R$? The symmetric closure of a given relation $S$ is the smallest superset $S^{\leftrightarrow}$ of $S$ such that $S^{\leftrightarrow}$ is symmetric. Informally, you can think of the symmetric closure of $S$ as the relation we get when we include all the pairs (and only those) to $S$ so as to make it symmetric. Thinking in terms of graphs, the symmetric closure is created by adding $b \rightarrow a$ to the graph whenever $a \rightarrow b$ is in the graph. Let's look at $R$ as an example. $R$ is not symmetric because $(0,1) \in R$, but $(1,0) \notin R$, so let's add $(1,0)$: $$R' = \{(0,1),(1,0),(1,2),(3,2)\}.$$ $R'$ is still not symmetric, because $(2,1) \notin R'$ and $(2,3) \notin R'$, so we add those to obtain $$R^{\leftrightarrow} = \{(0,1),(1,0),(1,2),(2,1),(3,2),(2,3)\},$$ which is the symmetric closure of $R$.

The exact same idea holds for the transitive and reflexive closure of $R$: it is the smallest superset $R^+$ of $R$ such that $R^+$ is transitive or reflexive, respectively. So when you want the reflexive, transitive, symmetric closure of $R$ you have to keep adding elements to $R$ until it is both reflexive, transitive, and symmetric.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.