(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

Suppose R is a relation on A and let S be the transitive closure of R. Prove that Dom(S) = Dom(R) and Ran(S) = Ran(R).

*Dom() signifies the domain of the specified relation. Ran() signifies the range of the specified relation.*

2. Relevant equations

Let M = {T ⊆ A x A | R ⊆ T and T is transitive}. I have already shown (in a different exercise) that ∩M is the transitive closure of R (so S = ∩M).

3. The attempt at a solution

Let x ∈ Dom(S). Then there is some y ∈ A such that (x,y) ∈ S = ∩M. This means (∀K ∈ M)((x,y) ∈ K). We must show x ∈ Dom(R), which means there is some z ∈ A such that (x,z) ∈ R... (and this is where i can't seem to find how to proceed)

As you can see I am trying to prove the two conjuncts separately. I am proving the equalities by proving that each side is a subset of the other... I can prove the opposite direction easily, but this one doesn't seem as easy. I'm sure it is analogous for the Range equalities as well.

Any insight is appreciated, thanks!

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Proof concerning a transitive closure

**Physics Forums | Science Articles, Homework Help, Discussion**