Relation and closure

Question

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}}{}$):

$0\rightarrow~1~\rightarrow~2~\leftarrow~3$

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) $

Answer 1

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.