The Unapologetic Mathematician

Mathematics for the interested outsider

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 | 2 Comments