nLab complement

The complement of a subset $S$ of a set $X$ is the set

$\stackrel{˜}{S}=\left\{a:X\phantom{\rule{thickmathspace}{0ex}}\mid \phantom{\rule{thickmathspace}{0ex}}a\notin S\right\}.$\tilde{S} = \{ a: X \;|\; a \notin S \} .

(Besides $\stackrel{˜}{S}$, there are many other notations, such as $X-S$, $\overline{S}$, $¬S$, and so forth.)

Notice that $S\cap \stackrel{˜}{S}=\varnothing$, while $S\cup \stackrel{˜}{S}=X$ by the principle of excluded middle.

The complement of an element $S$ of a lattice is (if it exists) the unique element $\stackrel{˜}{S}$ such that $S\wedge \stackrel{˜}{S}=\perp$ and $S\vee \stackrel{˜}{S}=\top$. Such complements always exist in a Boolean algebra.

More generally, the pseudocomplement of an element $S$ of a Heyting algebra is given by $\stackrel{˜}{S}=S⇒\perp$. This satisfies $S\wedge \stackrel{˜}{S}=\perp$ but not $S\vee \stackrel{˜}{S}=\top$ in general. This case includes the complement of a subset even in constructive mathematics.

In another direction, the complement of a complemented subobject $S$ of an object $X$ in a coherent category is the unique subobject $\stackrel{˜}{S}$ such that $S\cap \stackrel{˜}{S}$ is the initial object and $S\cup \stackrel{˜}{S}=X$.

The complement of a truth value (seen as a subset of the point) is called its negation.

Revised on January 31, 2010 03:57:24 by Toby Bartels (173.60.119.197)