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.

  • $\begingroup$ I deleted your request for further "interesting facts" because that seems to be an opinion-based invitation to an infinite list and discussion. $\endgroup$ – David Richerby May 10 '15 at 11:02
  • $\begingroup$ Why isn't such an invitation to discussion not welcomed ? $\endgroup$ – user1419 May 10 '15 at 14:33
  • $\begingroup$ 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. $\endgroup$ – babou May 10 '15 at 14:55
  • $\begingroup$ 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. $\endgroup$ – David Richerby May 10 '15 at 14:58
  • $\begingroup$ 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) $\endgroup$ – 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$.

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

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.