# Operations on Relations

Besides the ordinary set operations, there are special operations we can perform on relations.

Definition. The inverse of a relation from to is the relation from to defined by:

That is, iff iff iff .

E.g. iff iff .

That is, the inverse of the less-than relation is the greater-than relation.

Note that the inverse and the complement are very different things, because the complement of less-than is greater-than-or-equal-to.

Exercise. What is the inverse of the identity relation?

Definition. If is a relation from to and is a relation from to , we define the {\em composite relation} from to by:

Note that the source of is the source of and the target of is the target of .

We can think of as a stepping stone between and . consists of all the pairs such that there is such a stepping stone, as we pass from the source of to the target of .

Observe that unless the target of and the source of are the same, we can't even make sense of . So most composites aren't defined, and we must first check that two relations are compatible before we try to compose them. Even if is defined, usually isn't.

In lower mathematics courses, you probably only encountered relations on , so that all sources and targets were the same---thus, all compositions were defined. The sole exception to this is in multivariable calculus. This is precisely why the multivariable Chain Rule is so much more complicated than its single-variable counterpart.

Exercise. Formulate the definition of in infix notation. That is, explain what means.

Exercise.  Consider the set of all people, and the relations and on given by: iff is 's mother and iff is 's father. Explain what the following relations mean: , , , , , , , , .

Theorem. Let be a relation from to , a relation from to , and a relation from to . Then

• and
• and .

Proof. We'll prove the last clause, and leave the others as exercises.

Since we need to prove , let . Then for some . Since , there is some with . So . So .

To show , let . Then for some . Since , there is some with . Then . So .