Thursday, June 16, 2011

Equivalence relations

Today I learned about equivalence relations, equivalence classes, partitions, divides, and congruent to modulo n.

An equivalence relation is a relation that is reflexive, symmetric, and transitive.  Pretty straight forward.

An equivalence class (also known as an equivalence set) is denoted [a] = {x | x is an element of A, x R a}.  In other words, it is the set [a] consisting of all the elements of the set A which are related to a by the equivalence relation R.  To look at it in a slightly different way, [a] is the set of all elements in A which are related to a.  For example, if the relation is "has the same PvP score as" and A is the set of all the people in your gaming community and a is someone in that community (lets say it is you), then [a] would be the set of everyone in your gaming community who has the same PvP score as you do.

A partition is a set of sets.  So for example, S = {A1, A2, ..., An} where Ai is some set for 1 <= i <= n.  A partition has a few requirements for that set of sets though.  Each Ai is a subset of a single set A.  Also, every pair of distinct subsets (I will get to what "distinct" means shortly) is disjoint, meaning their intersection is the empty set (there are no overlapping elements between subsets).  And finally, the union of all Ai must be the set A.  This is kind of like partitioning a harddrive or separating the screen in a Tetris-like game into chunks for the various shapes and the empty space.

There is another noteworthy "set of sets": the equivalence classes.  You can actually make a set out of all the possible equivalence classes for a particular (nonempty) set and equivalence relation: S = {[a] | a is an element of A}  This is noteworthy because it turns out that the set of equivalence classes S is a partition of the set A.  However, if you are like me this can get confusing when you realize that two or more of the equivalence classes in the set can be equal.  For example, if A={1, 2, 3, 4} and the relation is setup so that [1] = {1, 3} and [3] = {1, 3}.  But isn't one of the requirements for a partition that all pairs of sets be disjoint?  How are {1, 3} and {1, 3} disjoint?  Well, the key bit of information I was missing is this: Only distinct sets count.  Two sets are distinct if they are not equal.  This makes sense, since you can have a set A = {a, b, a, c} but all of the a's are treated as the same element.

Lets define the set Z to be the set of all integers.  Given two variables d and m which are both elements of Z (they are both integers) and where d does not equal 0, if there is a variable q which is also an element of Z such that m = dq then you could say that d divides m, or in more "mathy" terms: d|m.  Note that q must be an element of Z, so in other words an integer.  If the division has a remainder, then q doesn't exist in Z and d does not divide m.

Lets look at d|m again, but this time using three variables instead of two: n, a, and b which are all elements of Z.  If you arrange these so that it reads "n divides the difference between a and b", in other words n|(a - b), you can also say that "a is congruent to b modulo n".  I don't have access to the exact symbols, but the mathematical way to write it is something like this: a congruent b(mod n).

Using congruent modulo n you get an interesting set called "integers modulo n", written Zn or Z/(n).  It is the set of distinct equivalence classes from the relation "is congruent modulo n" on the set of integers Z where n >= 2.  I stopped studying today about half-way through a problem which was designed to show uses for this set, so I'm not really sure how you could put it to use.  Based on the name however (and after seeing what a few of the equivalence classes are for a couple values of n), I'm going to guess that it can be used in division, possibly as a lookup table or for something related to remainders.  I'm sure I'll find out later!

No comments:

Post a Comment