Relation Complement

The complement of a relation contains all ordered pairs that are not in the original relation but are in the Cartesian product of the examined set. The complement thus gives the 'opposite' of the original relation.

Formal Definition

If A is a set and R is a relation on A, then the complement of R contains every (a,b) pair that is in A × A but not in R.

Examples of Relation Complements

Let A = {1,2,3}, and R = { (1,1), (2,2), (3,3) } (the equality relation).

Then A × A = { (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3) }.

Thus R^c = { (1,2), (1,3), (2,1), (2,3), (3,1), (3,2) }.

• If R = "≤" on integers, then the complement of R is the ">" relation.
• If R = "divides" on natural numbers, then the complement is "does not divide".
• If R = "friend of" among people, then the complement is the "not friend of" relation.

Properties

• Taking the complement twice returns the original relation: (R^c)^c = R.
• Union and intersection relate to the complement (De Morgan's laws): (R ∪ S)^c = R^c ∩ S^c, (R ∩ S)^c = R^c ∪ S^c.
• The complement often expresses the opposite property compared to the original relation (e.g., friend of ↔ not friend of).

Summary

The complement of a relation contains every pair not in the original but in the full Cartesian product. This is a useful tool in mathematics, as it allows examination of the opposite of relations and helps in logical operations.

Practice Exercise