Complement (difference)

Complement of set A is a set of elements not in A. In other words, it’s the opposite of A.

A^{C} = \{x : x \notin A \}

The notion of complement (or difference) requires an implicit assumption: what other elements are we talking about? Say, the complement of all positive numbers is negative numbers, and zero, and dogs, and Korean words, and… all possible elements that aren’t positive numbers? Thinking this way quickly reduces the conversation to either absurdity or to Russell’s paradox. This is why the complement assumes some larger set in which A exists. This larger set should be obvious from the context, or should be specified explicitly somewhere. For instance, when talking about movies, the complement of the set of my favorite movies is obviously all other movies that aren’t my favorite. The term universe is used for a collection of entities one wishes to consider. For the example of movies, the universe is probably “all movies ever produced”.

It’s sometimes useful to consider the complement of a set with respect to some other well-defined set. This is often called set difference and is denoted as A - B. Formally:

A - B = \{x | x \in A \textrm{ but } x \notin B\}

SQL operator EXCEPT is similar to this idea.

SELECT username FROM users
EXCEPT
SELECT username FROM managers;

This query would return all users who aren’t managers. In set theory, we’d write it this way:

\textrm{Users} - \textrm{Managers}

Or, with implicit universe:

\textrm{Managers}^{C}

with an assumption that we’re talking about users in general.

Even if you haven’t heard of set union, intersection and complement, you’ve definitely seen Venn diagrams. They illustrate those ideas quite nicely.