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.