Regarding Formal Proof Dom($S$) = Dom($R$) and Ran($S$) = Ran($R$).

228 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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