0
$\begingroup$

Suppose $R$ is a relation on $A$. Let $Q$ be the symmetric closure of $R$, and let $S$ be the transitive closure of $Q$.

Useful theorem: Let $U$ be the transitive closure of $R$. If $R$ is symmetric, then so is $U$.

Prove that $S$ is the symmetric transitive closure of $R$.

I managed to prove 1) $R\subseteq S$, 2) $S$ is symmetric, and 3) $S$ is transitive. But I don't understand the solution which proves that $S$ is the smallest set that has these properties.

Solution: Suppose $T\subseteq A \times A$, $R \subseteq T$, and $T$ is both symmetric and transitive. Since $Q$ is the smallest symmetric relation on A containing $R$, $Q\subseteq T$. But then since $S$ is the smallest transitive relation on $A$ containing $Q$, $S \subseteq T$.

I just fail to understand how $S\subseteq T$ (the last two lines of the solution). I can see that $S$ is a member of $\{ T\subseteq A\times A | R\subseteq T, T$ is symmetric and $T$ transitive$\}$, i.e. $S$ is one of the Ts that has these properties, but I don't know how to jump from this to saying $S$ is the smallest set among all Ts.

I get the impression that it is just intuitive that the conclusion follows from the proof, which is just a matter of understanding by 'the smallest set' it is talking about a subset partial order, but I am just too stupid to get it. Could anyone please help?

$\endgroup$
1
$\begingroup$

Let it be that $S'$ is the smallest relation on $A$ that is symmetric, transitive and contains $R$ as a subset.

Then $Q\subseteq S'$ by definition of $Q$ since $S'$ is symmetric and satisfies $R\subseteq S'$.

Then $S\subseteq S'$ by definition of $S$ since $S'$ is transitive and satisfies $Q\subseteq S'$.

We know that $S$ is transitive and satisfies $R\subseteq Q\subseteq S$, but according to the useful theorem that was mentioned $S$ is also symmetric.

That allows us to conclude that $S'\subseteq S$ by definition of $S$, and consequently $S=S'$.

Proved is now (by use of useful theorem) that $S$ is the smallest relation on $A$ that is symmetric, transitive and contains $R$ as a subset.

$\endgroup$
  • $\begingroup$ Sorry would you mind explaining why is $Q\subseteq S'$ please? I get that $S'$ is symmetric and $R\subseteq S'$, but I don't get how do these two entail $Q\subseteq S'$. We know 1) $R\subseteq Q$, 2) Q is symmetric, and 3) Q is the smallest symmetric relation on A that contains R, but I still don't see it. I know it may sound like I am not using my brain but I just don't see it... $\endgroup$ – Daniel Mak Apr 3 '17 at 15:17
  • 1
    $\begingroup$ $Q$ is the symmetric closure of $R$, i.e. the intersection of all relations on $A$ that contain $R$ as a subset and are symmetric. $S'$ is one of these relations. That gives $Q\subseteq S'$. $\endgroup$ – drhab Apr 3 '17 at 15:24
  • $\begingroup$ Thank you! Now that you rephrased it differently I think I got it now $\endgroup$ – Daniel Mak Apr 5 '17 at 16:50
  • 1
    $\begingroup$ Glad to help. You're welcome. $\endgroup$ – drhab Apr 5 '17 at 17:01

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.