Jump to content
  • entries
  • comments
  • views

Equivalence relations

Sign in to follow this  


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 = {A[sub]1[/sub], A[sub]2[/sub], ..., A[sub]n[/sub]} where A[sub]i[/sub] is some set for 1 <= i <= n. A partition has a few requirements for that set of sets though. Each A[sub]i[/sub] 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 A[sub]i[/sub] 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 Z[sub]n[/sub] 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!

Reposted from http://invisiblegdev.blogspot.com/
Sign in to follow this  


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!