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.

About these ads

March 2, 2007 - Posted by | Fundamentals

2 Comments »

  1. [...] Orders As a bonus today, I want to define a few more kinds of relations. [...]

    Pingback by Orders « The Unapologetic Mathematician | March 11, 2007 | Reply

  2. [...] given a topological space and an equivalence relation on the underlying set of we can define the quotient space to be the set of equivalence classes [...]

    Pingback by Limits of Topological Spaces « The Unapologetic Mathematician | April 28, 2010 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 392 other followers

%d bloggers like this: