Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2007-10-07 10:33:25

MarkusD
Member
Registered: 2006-10-08
Posts: 28

Proof with Transitive Closures

Im stuck with the following question:

Q: R is a relation on X. Prove if R is symmetric, then Rt is symmetric (Note Rt is the transitive closure of R).


I know that for R to be symmetric, we need xRy and yRx. Also, Rt is the smallest transitive relation containing so Rt is a subset of R.

So in thinking about this, I think I need to show that assuming R is symmetric, that 1) R is a subset of Rt^-1  and that Rt^-1 is transitive. Is this correct? If so, how do I prove 1)?

Offline

#2 2007-10-08 04:35:03

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Proof with Transitive Closures

You need to look at exactly what relations you will be adding to R.  Specifically, if a R b and b R c then you need to add a relation.  However, if that's the case, then b R a and c R b because R is symmetric.  Thus, c R b and b R a, so you need to also add in c R a if it isn't there.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

Board footer

Powered by FluxBB