The complement S˜\tilde S of a subset SS of a set XX is the set of ell elements of XX not contained in SS:

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

(Besides S˜\tilde{S}, there are many other notations, such as XSX - S, XSX \setminus S, S¯\bar{S}, S cS^c, ¬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.

A complement of an element SS of a lattice is an element TT such that ST=S \wedge T = \bot and ST=S \vee T = \top. Note that in general, complements need not be unique; for example, in the lattice of vector subspaces of a 2-dimensional vector space over a field kk, a 1-dimensional subspace will have as many complements as there are elements of kk. However, in some cases complements will be unique, for example in a distributive lattice, in which case it is denoted S˜\tilde{S} (or ¬S\neg S, etc.).

If every element has a complement, one speaks of a complemented lattice. Examples are Boolean algebras, and in fact complemented distributive lattices are the same thing as Boolean algebras (in the sense that the category of Boolean algebras is equivalent to the category of complemented distributive lattices).

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 July 15, 2017 02:48:23 by Mike Shulman (