0
$\begingroup$

Please Comment on the validity of presented proof of the given theorem.

Theorem. Given that $R$ is a relation on $A$, and $S$ is the transitive closure of $R$, If $R$ is symmetric, then so is $S$.

Proof. Assume that $R$ is a relation on $A$, $S$ is the transitive closure of $R$ and $R$ is symmetric. Let $\mathcal{F} = \{T\subseteq A\times A|R\subseteq T \land\forall x\in A\forall y\in A\forall z\in A(xRy\land yRz\implies xRz)\}$

Now assume that $(x,y)\in R$ where $x$ and $y$ are arbitrary members of $A$ as $R$ is symmetric it follows that $(y,x)\in R$ and $S$ is the transitive closure of $R$ then it must be that $R\subseteq S$ and so $(y,x)\in S$ which implies that $(x,y)\in S^{-1}$ since $x$ and $y$ were arbitrary it follows that $R\subseteq S^{-1}$.

Now Assume that $(z,y)\in S^{-1}$ and $(y,x)\in S^{-1}$ where $z,y$ and $x$ are arbitrary members of the set $A$, from this it is evident that $(x,y)\in S$ and that $(y,z)$ but since $S$ is transitive it follows that $(x,z)\in S$ which entails that $(z,x)\in S^{-1}$. since $x$ and $y$ were arbitrary it follows that $S^{-1}$ is transitive.

We have now established that $R\subseteq S^{-1}$ and that $S^{-1}$ is transitive but then $S\in \mathcal{F}$ and since $S$ is the transitive closure of $R$ and thus satisfies $\forall T\in\mathcal{F}(S\subseteq T)$ consequently $S\subseteq S^{-1}$.

Now Assume that $(x,y)\in S$ where as before $x$ and $y$ are arbitrary in $A$ it follows that $(x,y)\in S^{-1}$ and thus $(y,x)\in S$ generalizing our argument to any ordered pair in $S$ establishes the symmetry of $S$.

$\endgroup$
  • $\begingroup$ This seems fine to me. Is there a particular point about which you are concerned? $\endgroup$ – WSL Jun 9 '17 at 0:24
0
$\begingroup$

If $aSb$, then there is some $x_1,.. x_j$ with
$. . aRx_1, x_1Rx_2,.. x_jRb$.
As $R$ symmetric,
$. . . bRx_j, x_jRx_{j-1},.. x_1Ra$;
so $bSa$.

$\endgroup$
  • $\begingroup$ Please: When you have 530 reputation it really is time to use proper formatting... $\endgroup$ – user370967 Jun 9 '17 at 8:45
  • $\begingroup$ @Math_QED. I have not found an apt that assists with writing the syntax of TeX. $\endgroup$ – William Elliot Jul 22 '17 at 20:37
  • $\begingroup$ It's really not hard: math.meta.stackexchange.com/questions/5020/… $\endgroup$ – user370967 Jul 23 '17 at 8:45
  • $\begingroup$ @Math_QED. That is not an app. It is a manual. $\endgroup$ – William Elliot Jul 24 '17 at 9:15
  • $\begingroup$ Why do you need an app? You could have simply formatted your answer if you would have written dollar signs around each expression. $\endgroup$ – user370967 Jul 24 '17 at 9:30

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.