Discrete Math Let R be a symmetric relation Show that Rn is

Discrete Math:

Let R be a symmetric relation. Show that R^n is symmetric for all positive integers n. (perhaps induction would work?)

Solution

Let R be a symmetric relation on set A

Proof by induction

Step I- R¹=R is symmetric, which is true.

Step II- Assume that Rⁿ is symmetric.

Step III- to prove that Rⁿ⁺¹is symmetric.

Rⁿ⁺¹ is symmetric if for all (x,y) in Rⁿ⁺¹, we have (y,x) is in Rⁿ⁺¹ as well. Assume that (x,y) is in Rⁿ⁺¹.

Now, Rⁿ⁺¹= RⁿoR= RoRⁿ

we know that if (x,y)RoRⁿ, then by definition of composition there exists a z in A such that xRz and z(Rⁿ)y i.e. (x,z) is in R and (z,y) is in Rⁿ. And we also know that R and Rⁿ are symmetric, which implies that (z,x) is in R and also (y,z) is in Rⁿ.

Therefore, by definition of composition,

(y,z) RoRⁿ, i.e. (x,y)Rⁿ⁺¹

Hence proved