nLab
complement

Contents

Idea

The complement of a subset SS of a set XX is the set

S˜={a:X|aS}. \tilde{S} = \{ a: X \;|\; a \notin S \} .

(Besides S˜\tilde{S}, there are many other notations, such as XSX - S, S¯\bar{S}, ¬S\neg{S}, and so forth.)

Notice that SS˜=S \cap \tilde{S} = \empty, while SS˜=XS \cup \tilde{S} = X by the principle of excluded middle.

The complement of an element SS of a lattice is (if it exists) the unique element S˜\tilde{S} such that SS˜=S \wedge \tilde{S} = \bot and SS˜=S \vee \tilde{S} = \top. If all complements exists one speaks of a complemented lattice. Examples are Boolean algebras.

More generally, the pseudocomplement of an element SS of a Heyting algebra is given by S˜=S\tilde{S} = S \Rightarrow \bot. This satisfies SS˜=S \wedge \tilde{S} = \bot but not SS˜=S \vee \tilde{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 SS of an object XX in a coherent category is the unique subobject S˜\tilde{S} such that SS˜S \cap \tilde{S} is the initial object and SS˜=XS \cup \tilde{S} = X.

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

Revised on December 24, 2013 06:00:26 by Urs Schreiber (82.113.121.211)