Let $Q$ be the symmetric closure of $R$, and let $S$ be the transitive closure of $Q$. Prove that $S$ is the symmetric transitive closure of $R$.

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?

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.

• 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... – Daniel Mak Apr 3 '17 at 15:17
• $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'$. – drhab Apr 3 '17 at 15:24
• Thank you! Now that you rephrased it differently I think I got it now – Daniel Mak Apr 5 '17 at 16:50
• Glad to help. You're welcome. – drhab Apr 5 '17 at 17:01