= Complement of a set
{title2=$X\setminus A$}
{wiki=Complement_(set_theory)}
= Complement
{synonym}
The complement of a <subset> $A$ within a specified <universal set> $U$ contains exactly the <set elements> of $U$ excluded from $A$:
$$
A^c=U\setminus A=\{x\in U:x\notin A\},\qquad x\in U\Longrightarrow\bigl(x\in A^c\iff\neg(x\in A)\bigr).
$$
Here $A^c$ depends on the chosen <universal set>. Within $U$, taking a <complement> performs <logical negation> (NOT) on membership. Writing $U\setminus A$ keeps the ambient <set> visible when there could be ambiguity.
For $A=\{1,2,3\}$, $B=\{3,4\}$, and $U=\{1,2,3,4,5,6\}$:
$$
U\setminus A=\{4,5,6\},\qquad U\setminus B=\{1,2,5,6\}.
$$
If the <universal set> grows to $U'=\{1,2,3,4,5,6,7\}$, the same <sets> have different <complements>: $U'\setminus A=\{4,5,6,7\}$ and $U'\setminus B=\{1,2,5,6,7\}$. In a database illustration, “records that fail this condition” therefore requires deciding which records are eligible to begin with; those eligible records form $U$.
For <subsets> $A,B\subseteq U$, <De Morgan's laws> exchange <union> and <intersection> when taking <complements>:
$$
U\setminus(A\cup B)=(U\setminus A)\cap(U\setminus B),\qquad U\setminus(A\cap B)=(U\setminus A)\cup(U\setminus B).
$$
For the same example, failing both conditions leaves $U\setminus(A\cup B)=\{5,6\}=(U\setminus A)\cap(U\setminus B)$. Failing at least one condition leaves $U\setminus(A\cap B)=\{1,2,4,5,6\}=(U\setminus A)\cup(U\setminus B)$. This is useful for rewriting exclusion rules into separate membership tests. The symmetry is also pleasing: exchanging <union> with <intersection> turns one rule into its partner.
\Image[/de-morgan-set-complements.png]
{title=<De Morgan's laws>: excluding a <union> means failing both tests, while excluding an <intersection> means failing at least one}
A brief membership proof works in <classical propositional logic>. For any $x\in U$, let $P$ mean $x\in A$ and $Q$ mean $x\in B$. The <truth table> below checks all four possibilities, with $1$ meaning true and $0$ false:
$$
\begin{array}{cc|cc|cc}
P&Q&\neg(P\vee Q)&\neg P\wedge\neg Q&\neg(P\wedge Q)&\neg P\vee\neg Q\\\hline
0&0&1&1&1&1\\
0&1&0&0&1&1\\
1&0&0&0&1&1\\
1&1&0&0&0&0
\end{array}
$$
Each paired column agrees. Translating <logical disjunction> (OR), <logical conjunction> (AND), and <logical negation> (NOT) back into membership proves the two <set> equalities. For the general method of reducing <set> equalities to equivalences in <propositional logic>, see https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_042js15_textbook.pdf#page=93[Lehman, Leighton and Meyer, Mathematics for Computer Science (2015), §4.1.5 and Problem 4.5].
A historical perspective appears in Augustus De Morgan's https://en.wikisource.org/wiki/Page:Formal_Logic_(1847,_De_Morgan).djvu/8[Formal Logic (1847), preface]{ref}: he describes treating each name together with its contradictory name. In the membership viewpoint here, a <set> and its <complement> likewise pair a condition with its <logical negation>.
Back to article page
