Prove that if S is a symmetric relation on A and R $\subseteq$ S, then $R^{-1}$ $\subseteq$ S

Question

Let R be a relation on the set A.

pf(contradiction) Assume S is a symmetric relation on A and R $\subseteq$ S. Then (x,y) $\in$ S and (y,x) $\in$ S. Also, (x,y) $\in$ R. Assume $R^{-1} \not \subset$ S. Then (y,x) $\not \in$ S. This is a contradiction. Therefore, if S is a symmetric relation on A and R $\subseteq$ S, then $R^{-1}$ $\subseteq$ S.

This is what I have written. In a subset proof you are suppose to start off by "Let"(by what my high school math teacher says), but I don't know where to use that in the proof. This is what I have come up and was looking for some feedback.

Answer 1

A direct proof from the definitions:

Let $(x,y)\in R$, then, $(x,y)\in S$ (definition of subset).

By $S$ symmetric, $(y,x)\in S$ (definition of symmetric relation).

Also, $(x,y)\in R\Leftrightarrow(y,x)\in R^{-1}$ (just restated definition of inverse relation for clarity).

Therefore $R^{-1}\subseteq S$ (definition of subset, applied to the preceding two lines).

Note, everything in parenthesis can be omitted, I was just pointing out explicitly what the justifications were for each step. You could even omit the line beginning with also, but in my opinion, the proof isn't as clear without that line included.

Edit:

Pedantic version:

Let $(x,y)\in R^{-1}$, then by the definition of inverse relation, $(y,x)\in R$.

Since, by assumption, $R\subseteq S$, $(y,x)\in R\Rightarrow(y,x)\in S$.

Now, by assumption, $S$ is a symmetric relation, thus we have, by definition of symmetric relation, that $(y,x)\in S\Rightarrow(x,y)\in S$.

Thus we have shown that, $(x,y)\in R^{-1}\Rightarrow (x,y)\in S$.

Therefore, by the definition of subset, $R^{-1}\subseteq S$.

QED

Answer 2

It's a solid proof.   There's nothing requiring you to start of with "Let ..." other than style; although it is good practice to put definitions before manipulations.   So my suggestion is to move the phrase starting with "Also..." to a bit earlier (and make it a "let" if you wish).

Also, $R^{-1}\not\subset S$ does not mean that every $(y,x)\notin S$, just that some such exist (which is enough).

pf(contradiction)   Assume $S$ is a symmetric relation on $A$ and $R\subseteq S$.   Let $(x,y)\in R$.   Then $(x,y) \in S$, and by symmetry, $(y,x)\in S$.   Assume $R^{−1}\not\subseteq S$.   Then there exists some $(x,y)\in R$ such that $(y,x)\notin S$.   This is a contradiction.   Therefore, if $S$ is a symmetric relation on $A$ and $R\subseteq S$, then $R^{-1}\subseteq S$.

Answer 3

Shortcut:

A relation $T$ is symmetric if and only if $T^{-1}=T$

Applying that on $S$ we find directly:$$R\subseteq S\implies R^{-1}\subseteq S^{-1}=S$$

Answer 4

Your intuition is correct, but when you say:

Then $(x,y) \in S$ and $(y,x) \in S$

that's not very precise: what are $x$ and $y$ here? Consider that $S$ could be the trivial relation $S = \{\}$, which is symmetric; but then it's certainly false that "$(x,y) \in S$ and $(y,x) \in S$" for any $x$ and $y$. Instead, I think you mean:

Then, $(x,y) \in S$ if and only if $(y,x) \in S$.

Next, you say "Also, $(x,y) \in R$"; again this is not precise. Which $x$ and $y$ are you speaking of here? Clearly, we don't know that every pair $(x,y) \in S$ 'also' has $(x,y) \in R$.

So to be clearer, you might say:

For all $(y,x) \in R^{-1}$, $(x,y) \in R$; and since $R \subseteq S$, then $(x,y) \in S$; which then implies $(y,x) \in S$. Therefore for all $(y,x) \in R^{-1}$, $(y,x) \in S$; and so $R^{-1} \subseteq S$.