Definition:Complement of Relation

From ProofWiki
Jump to: navigation, search


Let $\mathcal R \subseteq S \times T$ be a relation.

The complement of $\mathcal R$ is the relative complement of $\mathcal R$ with respect to $S \times T$:

$\relcomp {S \times T} {\mathcal R} := \set {\tuple {s, t} \in S \times T: \tuple {s, t} \notin \mathcal R}$

If the sets $S$ and $T$ are implicit, then $\complement \paren {\mathcal R}$ can be used.

Also denoted as

An alternative to $\relcomp {S \times T} {\mathcal R}$ is $\overline {\mathcal R}$ which is more compact and convenient, but the context needs to be established so that it does not get confused with other usages of the overline notation.

Specific conventional symbols used to denote certain frequently-encountered relations often consist of lines in various configurations, for example $=$, $\le$, $\equiv$, and adding an overline to these can only make for confusion.

In these cases, it is conventional to draw a line through the symbol, for example:

$\ne$ for $\complement \paren =$
$\not \le$ for $\complement \paren \le$
$\not \equiv$ for $\complement \paren \equiv$

and so on.

Some authors use $\mathcal R'$ to denote the complement of $\mathcal R$, but $'$ is already heavily overused.

Linguistic Note

The word complement comes from the idea of complete-ment, it being the thing needed to complete something else.

It is a common mistake to confuse the words complement and compliment. Usually the latter is mistakenly used when the former is meant.