Thread: Finding an equivalance class

indeed...a MEMBER of an equivalence class is called a "representative". we don't need to pick these in a uniform way, but sometimes, they help illuminate the differences between the various equivalences classes.

for this example, we could pick as the "designated representative", which would tells us it comes from the level set defined by f(x,y) = a.

the other function i gave you:

g(x,y) = xy

works in much the same way, except now the level-sets are hyperbolas instead of circles.

if instead, our function was:

h(x,y) = x + y, the level-sets would be lines, instead of circles or hyperbolas.

we can do the same thing with a variety of different curve-shapes (parabolas, ellipses, squares) although finding a function that produces the level-set shape we want can take a bit of ingenuity.

*************

an equivalence relation (on a set S) is often defined (this is the definition you are probably using in your class) as a relation (a subset of SxS) that:

1) is reflexive (a~a, or equivalently: includes the diagonal set ΔS = {(a,a) in SxS: a in S})

2) is symmetric (if a~b then b~a, or equivalently: is symmetric about the diagonal)

3) is transitive (if a~b and b~c, then a~c, equivalently: the triangle of points (a,b),(b,c),(a,c) is in ~)

but there is another way of looking at equivalence relations on S: as PARTITIONS of S. so even though a relation may not LOOK like an equivalence relation, if it chops up the set S into disjoint pieces, its an equivalence.

the general idea is "all elements of an equivalent class share some property, so it doesn't matter which one we use". for our good old friend (this is also known as "the square of the distance from the origin function") if two elements are in the same equivalence class, we know they both lie on the same circle (centered at the origin). so if all we want to do is pick "some point" a fixed distance from the origin, any representative from the equivalence class is as good as any other.

Okay, so this is how we get to f^-1(x, y). This means that the range (z,w) of f inverse is the domain (x, y) of f, for all (x,y) in the domain, right? And this is how you would define the equivalence class for an infinite relation?

well f^-1 isn't usually a function.

the simplest example is f(x) = x². this sends 2-->4 and also -2-->4. so the pre-image of 4 is {-2,2}.

so when we write f^-1(4),we get a SET, not a number.

but...we CAN "sort of" turn f^-1 into a function:

define x~y if x² = y² (that is: f(x) = f(y)....look sort of familiar?)

then [x] = {x,-x} (these are the same if x = 0).

we will call the set of equivalence classes of R (yes, we're using the real numbers here...we could use another set, but this one will do), R/~.

we can make another function (which we'll call [f]) that goes from R/~ --> R⁺ U {0} = range(f), by defining:

[f]([x]) = f(x) (you might want to check that this makes sense...which in this case means verifying that f(x) = f(-x)).

now, for THIS function, [f]^-1 IS a function, if we ask for the pre-image under [f] of y in range(f), we have [f]^-1(y) = f^-1(y) = {√y,-√y} = [√y], and this equivalence class is the ONLY one [f] maps to y.

in other words, by "lumping all the pre-images together in one equivalence class", we turn a many-to-one function into a one-to-one function between the equivalences classes and the range.

The majority of that last post makes sense to me, and the "we turn a many-to-one function into a one-to-one function between the equivalences classes and the range." helps a ton because for the longest time I was wondering how I was supposed to find "all equivalence classes" when we were dealing with variables rather than numbers like 1, 2, 3, 4, etc. I'm still left wondering how I should answer the question, though. Would f^-1(x, y) be the final answer, or would something like [(x, y)] = {(z,w) | ((x, y), (z, w)) in Af} be the final answer you would look for. If I understand correctly either way would suffice?

well, sometimes we have an infinite number of set elements, but only a finite number of equivalence classes.

the proto-typical example of this is the following:

suppose our set S = Z, the integers, and n is some given positive integer. we define a~b if a - b is a multiple of n.

we then get the following equivalence classes:

[0],[1],[2],[3],...,[n-1].

now, in the example you originally gave in this thread: recall that f(x,y) is a single number, not a pair of numbers f:R²--->R, so it would be f^-1(z) <---pre-image of a single number.

the 1-1 correspondence is:

circle of radius r <---> non-negative number r² or:

non-negative number a <---> circle of radius √a <---these are BOTH infinite sets (there's an infinite number of non-negative real numbers, and an infinite number of possible circles centered at the origin).

with the example i gave above (a~b if a- b = kn), then equivalence 1-1 correspondence is:

[a] <---> r (where r = 0,1,...,n-1) and we can find r by writing a = qn + r (dividing by n, and finding the remainder).

so, for your original question, some possible, and equivalent answers are:

[(x,y)] = f^-1(f(x,y)) <--this ISN'T just (x,y) because f might (and in this case, does) "shrink stuff", so when we take the pre-image it "expands". (x,y) is guaranteed to be in it, somewhere, though.

[(x,y)] = {(z,w) in R² : f(z,w) = f(x,y)}

[(x,y)] = {(z,w) in R²: (z,w) ~ (x,y)} <---both this and the answer above are "technically correct" but unenlightening: they just say "the equivalence class is the equivalence class"

[(x,y)] = a circle of radius √(x² + y²) <--this answer tells us something about the equivalence class that isn't obvious at first.

***********************

something about functions: functions either are 1-1, or they are not. 1-1 functions are nice, because we can treat f(x) as a "re-naming" of x. unfortunately, not all functions ARE 1-1. if they are not, then some "collapsing" takes place. in other words:

1-1 functions represent the BEST POSSIBLE situation, the equivalence classes induced by f just have one element in them: [f] = f. for the function f(x) = x, the equivalence relation induced by f:

x~y if f(x) = f(y) is called EQUALITY. so the identity function f(x) = x is a very nice function, indeed. constant functions, on the other hand, are very "not nice", since if f(x) = c for ALL x, if we know we ended up at c we have absolutely NO idea how we got there. constant functions effectively shrink an entire domain down to a point, and every element in the domain of f is equivalent to every other (not a very useful equivalence, since it tells us nothing, but it still qualifies as one).

Thanks for the great explanation. I guess it is sort of catching me off guard that not only are there many ways to state the answer, but saying "equivalence class is the equivalence class" is also a valid answer which is odd to me. Many examples in the reading for this class follow the 2nd and 3rd equivalent answer format you posted above, so I may just have to get used to it and try a few more problems to practice. In long hand form it means the equivalence class of (x,y) is equal to all (z,w) in R such that f(z,w) is equal to f(x, y)?

yes, but as i noted earlier that may be unenlightening. usually your instructor (or the text) wants you to notice something ELSE about an equivalence relation, some property (besides being in the same equivalence class) that all the elements have in common. for example:

equality: an element of an equivalence class has everything in common with its fellow members, because each equivalence class has a size of 1

congruence modulo n: all elements of an equivalence class have the same remainder upon division by n

defined by a function (of one variable): all elements of an equivalence class get mapped to the same value by f <---very useful for periodic functions, among other things

defined by a continuous function of several variables: all elements of an equivalence class represent a k-dimensional (where k is the number of variables) implicitly defined curve

congruence and similarity: important equivalence relations in geometry

trivial equivalence: contains all of SxS, "everything is equivalent" (one giant equivalence class).

equivalence classes are, in general, a way to see things as both "same and not the same" at the same time. very useful for simplifying structure by "modding out unhelpful information".

equivalence classes are usually defined for a REASON. figuring out what that reason is (or how it helps us) is not always obvious. to make people more comfortable with equivalence relations, often small finite sets are used as examples, to give students more confidence. since these are usually "toy examples" they don't give that much insight into the power of the idea (it is very strong).

for example, you might be given:

R = {(1,1),(1,2),(2,1),(2,2)} and asked to verify that this is an equivalence on {1,2}. this is a trivial equivalence on {1,2} and doesn't really motivate why we might make such a definition. a much better example is this one:

R = {(x,y) in Z*xZ*: xy > 0} which separates non-zero integers into "positive" and "negative" equivalence classes (allowing us to make an "arithmetic of signs" under multiplication).