0
$\begingroup$

Please Examine the presented proof to the given theorem my contention is that the presented argument is merely intuition and not a rigorous proof

please point out any flaws in the argument and do suggests improvements.

Theorem. Given that $R$ is a relation on $A$, and $S$ is the transitive closure of $R$ then Dom($S$) = Dom($R$) and Ran($S$) = Ran($R$).

Proof. Assume that $xRy$ and $yRz$ where $x,y$ and $z$ are arbitrary members of $A$ in order to produce the transitive closure $S$ we are required to add the ordered pair $(x,z)$ but by adding this ordered pair we have introduced no new element in Dom$(R)$ because $xRy$ and thus $x\in$ Dom$(R)$ similarly we have introduce no new element in Ran$(R)$ because $yRz$, $z\in$ Ran$(R)$. This argument holds whenever we need to add another pair because of the requirement of transitivity, consequently Dom($S$) = Dom($R$) and Ran($S$) = Ran($R$).

$\endgroup$
3
  • $\begingroup$ It looks fine to me. Is there a specific problem you have with it? $\endgroup$ Jun 10, 2017 at 18:09
  • $\begingroup$ This question is part of a series of problems that i have been solving and through out those proofs effort has always been made in trying to produce the result from first principles that is the definitions of the objects mentioned in the theorem i do not see that in the proof mentioned above is this a valid concern or am i simply being over-skeptical ? Regards $\endgroup$ Jun 10, 2017 at 18:13
  • $\begingroup$ I think you're being over-skeptical, but re-writing the proof to whatever your standards of rigour are would be a good exercise. $\endgroup$ Jun 10, 2017 at 18:15

1 Answer 1

1
$\begingroup$

I think the argument is fine, but if you want to be really thorough, you could do this.

Let $S' = \{(x,y) \in S: x \in dom(R) \mbox{ and } y \in ran(R)\}$.

Then prove that $S'$ is transitive. This part of the argument is very similar to the paragraph you wrote.

Since $S' \supset R$, then $S'$ is a transitive relation containing $R$ and therefore $S' \supset S$. Also, $dom(S') = dom(R)$ and $ran(S') = ran(R)$.

By definition $S' \subset S$. So we have $S' = S$.

Then $dom(S) = dom(S') = dom(R)$ and $ran(S) = ran(S') = ran(R)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.