# set complement and superset

If 'S is a set complement of S, then a set complement of a superset of S' is a subset of S.

Just want to verify that above is true just based on the definition of set complement and superset.

• I deleted your request for further "interesting facts" because that seems to be an opinion-based invitation to an infinite list and discussion. – David Richerby May 10 '15 at 11:02
• Why isn't such an invitation to discussion not welcomed ? – user1419 May 10 '15 at 14:33
• Because the purpose is to try to have focussed contribution, hopefully easily retrievable with title and keywords, rather than open ended discussion, which you find on other forum. It is a matter of choosing one's ecological niche. – babou May 10 '15 at 14:55
• Because this is a question and answer site, not a discussion forum. However, if you just want to chat about whether there are other interesting examples of things, we do have a Computer Science Chat feature, which you're welcome to use. – David Richerby May 10 '15 at 14:58
• Actually, I have been wondering why you asked for that proof, which is not a very complex one. Is it the case that you were never presented with this type of proof? (I had a friend who enrolled on a CS PhD program in a major university with no knowledge of set theory ... not that I would recommend it - it was a very special case) – babou May 10 '15 at 15:00

Let $U$ be the universal set. We have $S\subseteq U$. The complement of $S$ is define as $S'=\{x\in U\mid x\notin S\}$. Thus $\forall x\in U,\; x\in S'\text{ iff } x\notin S$.

Let $T$ be a superset of $S'$, $T\supseteq S'$, which is true iff $\forall x\in U,\; x\in S'\text{ implies } x\in T$.

Then let $T'$ be the complement of $T$, so that again, as in the case of $S$, $\forall x\in U,\; x\in T'\text{ iff } x\notin T$.

Now you want to prove that $T'$ is a subset of $S$, $T'\subseteq S$, which is true iff $\forall x\in U,\; x\in T'\text{ implies } x\in S$.

Proof: Consider any element $x\in U$. Taking all our definitions in reverse order, we see that if $x\in T'$ then $x\notin T$. But this in turn that $x\notin S'$ since all elements in $S'$ are in its superset $T$. But by definition of $S'$, all elements not in $S'$ are in $S$.

So we have proved that $\forall x\in U,\; x\in T'\text{ implies } x\in S$.

Hence $T'\subseteq S$.

I'm not sure what you mean by "a set complement of $S$."

If you mean to allow complements with respect to different universal sets, then the statement in the question is not true. For example, let $S=\{1\}$. Its complement $S'$ with respect to $\{1,2\}$ is $\{2\}$. $\{1,2\}$ is a superset of $S'$ but its set complement with respect to $\{1,2,3\}$ is $\{3\}$, which is not a subset of $S=\{1\}$.

On the other hand, if you mean "the set complement of $S$" with respect to some fixed universal set $U$,the statement is true. We have $S'=U\setminus S$ and choose some $T \supseteq S'$. Then $U\setminus T \subseteq U\setminus S' = S$.

• I do mean with respect ot a fix universal set U . Thanks, – user1419 May 10 '15 at 14:32