Proof concerning a transitive closure

[Syrus]

Homework Statement

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.*

Homework 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).

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!

 

[micromass]

Hi Syrus!

There is another description of the transitive closure. This description will make this exercise very easy. Basically it is this

If K is any relation, then we denote $K^\circ=K\cup \{(x,z)~\vert~\exists y:~(x,y)\in K~\text{and}~(y,z)\in K\}$. Practically, this means that if we see (x,y) and (y,z) in K, then we adjoin the relation (x,z) to K.

Now, define

$$R_0=R,~R_1=R_0^\circ,~R_2=R_1^\circ,...,R_n=R_{n-1}^\circ,...$$

Then the transitive closure is

$$M=\bigcup_{n\in \mathbb{N}}{R_n}$$

Can you prove this?? And does this make your question easier?

 

[Syrus]

Hey Micromass, thank you for your response!

I believe your response deals with the definition of transitive closure that uses compositions of relations and proof via induction. It turns out this topic is addressed in a later section than that which this problem is from. I have since reviewed and understood that section, and as such, I respect and understand your post. At the same time, however, I am trying to do this exercise justice by attempting a proof using the definition of transitive closure provided within the corresponding text (which i stated above).

But you are obviously well-informed regarding this subject!

 

[micromass]

OK, I thought that actually.

Here's another thing to try. By contradiction. Assume that x is not in the domain of R, but suppose that x is in the domain of M (the transitive closure). Can we then not remove all relations with x as first argument and still have a transitive relation?

 

[Syrus]

So far I've got:

To prove Dom(S) ⊆ Dom(R), suppose to the contrary there is some x ∈ A such that x ∈ Dom(S) and x ∉ Dom(R). Then there is some y ∈ A such that (x,y) ∈ S. Also,(∀z ∈ A)((x,z) ∉ R).

Hmmm, still feeling a little stuck. I'm trying to produce a contradiction at this point.

 

[Syrus]

I need to learn from my mistakes! Look here: https://www.physicsforums.com/showthread.php?t=520630.

In the last post of the thread linked above, I realized my difficulty with that exercise was I didn't make proper use of a given of the following form: (∀X ⊆ A)(statement). It turns out, as I discovered, that when this appears you must more or less "design" a set which has the specified properties and helps you solve the proof. This is the case here as well.

As it turns out, the beginning of my original post was correct for this approach. That is,
"Let x ∈ Dom(S). Then there is some y ∈ A such that (x,y) ∈ S = ∩M. This means (∀K ∈ M)((x,y) ∈ K)."

Thus, it appears that if we can come up with any set K ∈ M, we can show that (x,y) ∈ K. Still, though, we'd have to somehow use this to conclude x ∈ Dom(R).

Now, we must "construct" a set T which is an element of M. The criteria for being a member of M are (as in the original post) that R ⊆ T and T is transitive. But recall we also need this set T to somehow relate to R (in order to show x ∈ Dom(R)).

Let T = {(x,y) ∈ A x A | x ∈ Dom(R) and y ∈ Ran(R)}.

Clearly, if (x,y) ∈ R then (x,y) ∈ T. So R ⊆ T. Also, if (x,y),(y,z) ∈ T, then x ∈ Dom(R) since (x,y) ∈ T and similarly z ∈ Ran(R) since (y,z) ∈ T. Hence, (x,z) ∈ T, so T is transitive. Therefore, T ∈ M and so (x,y) ∈ T, which in turn implies x ∈ Dom(R).

Whew! I've proven the other subset direction and it is much easier. I'm sure the range equality is analogous and can use the same relation T. On the other hand, I'm not sure how to feel. I'm definitely happy the problem has been solved, but I feel I shouldn't have struggled as much with it (I usually post problems for help only after pondering them for a few hours with no avail).