Assignment8.md

Assignment 8 Counterexample

Question: Is there a difference between the symmetric closure of the transitive closure of a relation R and the transitive closure of the symmetric closure of R?

Answer: Yes, (R⁺)^s ≠ (R^s)⁺ where R^s is the symmetric closure of R.

(R⁺)^s

• Take R = {(0,1)}
• R⁺ = {(0,1)}
• (R⁺)^s = {(0,1),(1,0)}

(R^s)⁺

• Take R = {(0,1)}
• R^s = {(0,1),(1,0)}
• (R^s)⁺ = {(0,1),(1,0),(1,1),(0,0)}