Skip to main content
added 15 characters in body
Source Link
j4GGy
  • 3.8k
  • 13
  • 14

Lets recall the definition of transitivity. A relation $R \subseteq A \times A$ on $A$ is called transitive, if we have $$(a,b),(b,c) \in R \Rightarrow (a,c)$$ for all $a,b,c \in A$.

Your initial set is $R = \{(1,2),(2,3),(3,4),(4,1)\}$. The way you described your approach is basically the way to go. Just go through the set and if you find some $(a,b),(b,c)$ in it, add $(a,c)$.

The way the answer is given is a little bit confusing because it already tries to be explanatory :) The thing is, that they mean unions $\cup$ instead of compositions $\circ$. BUT they are writing it as a union to emphasize the steps taken in order to arrive at the solution:

  1. Step: Look at $R$. Since $(1,2),(2,3) \in R$, we need to add $(1,3)$ to the set. Analogously we have to add $(2,4),(3,1)$ and $(4,2)$. Lets call this new set $R_1$.
  2. Step: Now we have $R \subset R_1$, but $R_1$ is not yet transitive because $(1,3),(3,4) \in R_1$ but $(1,4)\notin R_1$. Hence, we have to add $(1,4)$ to $R_1$ and so on...

If we keep going we end up with the complete relation $R^+ = A \times A$ where $A = \{1,2,3,4\}$, i.e. $R^+$ contains ALL possible pairs of $1,2,3,4$.

By the way: I really like the idea to visualize the relation as a graph.

Lets recall the definition of transitivity. A relation $R \subseteq A \times A$ on $A$ is called transitive, if we have $$(a,b),(b,c) \in R \Rightarrow (a,c)$$ for all $a,b,c \in A$.

Your initial set is $R = \{(1,2),(2,3),(3,4),(4,1)\}$. The way you described your approach is basically the way to go. Just go through the set and if you find some $(a,b),(b,c)$ in it, add $(a,c)$.

The way the answer is given is a little bit confusing because it already tries to be explanatory :) The thing is, that they mean unions instead of compositions. BUT they are writing it as a union to emphasize the steps taken in order to arrive at the solution:

  1. Step: Look at $R$. Since $(1,2),(2,3) \in R$, we need to add $(1,3)$ to the set. Analogously we have to add $(2,4),(3,1)$ and $(4,2)$. Lets call this new set $R_1$.
  2. Step: Now we have $R \subset R_1$, but $R_1$ is not yet transitive because $(1,3),(3,4) \in R_1$ but $(1,4)\notin R_1$. Hence, we have to add $(1,4)$ to $R_1$ and so on...

If we keep going we end up with the complete relation $R^+ = A \times A$ where $A = \{1,2,3,4\}$, i.e. $R^+$ contains ALL possible pairs of $1,2,3,4$.

By the way: I really like the idea to visualize the relation as a graph.

Lets recall the definition of transitivity. A relation $R \subseteq A \times A$ on $A$ is called transitive, if we have $$(a,b),(b,c) \in R \Rightarrow (a,c)$$ for all $a,b,c \in A$.

Your initial set is $R = \{(1,2),(2,3),(3,4),(4,1)\}$. The way you described your approach is basically the way to go. Just go through the set and if you find some $(a,b),(b,c)$ in it, add $(a,c)$.

The way the answer is given is a little bit confusing because it already tries to be explanatory :) The thing is, that they mean unions $\cup$ instead of compositions $\circ$. BUT they are writing it as a union to emphasize the steps taken in order to arrive at the solution:

  1. Step: Look at $R$. Since $(1,2),(2,3) \in R$, we need to add $(1,3)$ to the set. Analogously we have to add $(2,4),(3,1)$ and $(4,2)$. Lets call this new set $R_1$.
  2. Step: Now we have $R \subset R_1$, but $R_1$ is not yet transitive because $(1,3),(3,4) \in R_1$ but $(1,4)\notin R_1$. Hence, we have to add $(1,4)$ to $R_1$ and so on...

If we keep going we end up with the complete relation $R^+ = A \times A$ where $A = \{1,2,3,4\}$, i.e. $R^+$ contains ALL possible pairs of $1,2,3,4$.

By the way: I really like the idea to visualize the relation as a graph.

Source Link
j4GGy
  • 3.8k
  • 13
  • 14

Lets recall the definition of transitivity. A relation $R \subseteq A \times A$ on $A$ is called transitive, if we have $$(a,b),(b,c) \in R \Rightarrow (a,c)$$ for all $a,b,c \in A$.

Your initial set is $R = \{(1,2),(2,3),(3,4),(4,1)\}$. The way you described your approach is basically the way to go. Just go through the set and if you find some $(a,b),(b,c)$ in it, add $(a,c)$.

The way the answer is given is a little bit confusing because it already tries to be explanatory :) The thing is, that they mean unions instead of compositions. BUT they are writing it as a union to emphasize the steps taken in order to arrive at the solution:

  1. Step: Look at $R$. Since $(1,2),(2,3) \in R$, we need to add $(1,3)$ to the set. Analogously we have to add $(2,4),(3,1)$ and $(4,2)$. Lets call this new set $R_1$.
  2. Step: Now we have $R \subset R_1$, but $R_1$ is not yet transitive because $(1,3),(3,4) \in R_1$ but $(1,4)\notin R_1$. Hence, we have to add $(1,4)$ to $R_1$ and so on...

If we keep going we end up with the complete relation $R^+ = A \times A$ where $A = \{1,2,3,4\}$, i.e. $R^+$ contains ALL possible pairs of $1,2,3,4$.

By the way: I really like the idea to visualize the relation as a graph.