## Relations

Sooner or later I’ll have to use relations, so I may as well get the basics nailed down now.

A relation between two sets and is just a subset of their Cartesian product . That is, it’s a collection of pairs . Often we’ll write when is in the relation.

A function is a special kind of relation where each element of shows up on the left of exactly one pair in . In this case if is in the relation we write . Remember from our discussion of functions that I was saying every element of has to show up both at least once and at most once (that is, exactly once). A surjection is when every element of shows up on the right side of a pair in at least once, and an injection is when each element in shows up at most once.

Also interesting are the following properties a relation between a set and itself might have:

- A relation is “reflexive” if for every in .
- A relation is “irreflexive” if is
*never*true. - A relation is “symmetric” if whenever then also .
- A relation is “antisymmetric” if whenever and then and are the same.
- A relation is “asymmetric” if whenever then is
*not*true. - A relation is “transitive” if whenever and then also .

A very important kind of relation is an “equivalence relation”, which is reflexive, symmetric, and transitive. We’ve already used these a bunch of times, actually. When a group acts on a set , we can define a relation by saying whenever there is a group element so that . Since the identity of sends every element of to itself, this is reflexive. If there is a so that , then , so this is symmetric. Finally, if we have and so that and , then , so the relation is transitive.

When we have an equivalence relation on a set , we can break up into its “equivalence classes”. Any two elements and of are in the same equivalence class if and only if . We write the set of equivalence classes as . For group actions, these are the orbits of .

Show for yourself that in our discussion of cosets that there’s an equivalence relation going on, and that the cosets of in are the equivalence classes of elements of under this relation.