# The Unapologetic Mathematician

## 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 $X$ and $Y$ is just a subset $R$ of their Cartesian product $X\times Y$. That is, it’s a collection of pairs $(x,y)$. Often we’ll write $xRy$ when $(x,y)$ is in the relation.

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

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

• A relation is “reflexive” if $xRx$ for every $x$ in $X$.
• A relation is “irreflexive” if $xRx$ is never true.
• A relation is “symmetric” if whenever $xRy$ then also $yRx$.
• A relation is “antisymmetric” if whenever $xRy$ and $yRx$ then $x$ and $y$ are the same.
• A relation is “asymmetric” if whenever $xRy$ then $yRx$ is not true.
• A relation is “transitive” if whenever $xRy$ and $yRz$ then also $xRz$.

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 $G$ acts on a set $X$, we can define a relation $\sim$ by saying $x\sim y$ whenever there is a group element $g$ so that $gx=y$. Since the identity of $G$ sends every element of $X$ to itself, this is reflexive. If there is a $g$ so that $gx=y$, then $g^{-1}y=x$, so this is symmetric. Finally, if we have $g$ and $h$ so that $gx=y$ and $hy=z$, then $(hg)x=z$, so the relation is transitive.

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

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

March 2, 2007 - Posted by | Fundamentals