Apparently it is Hanamatsuri, the non-state holiday in Japan celebrating the Buddha's birth. So, omedetou gozaimasu, I guess. Let's talk about equivalence relations.
As always, what am I talking about? First, we must relate what a relation is, but in order to do that, let's talk (you listen) about Cartesian products. Let's say we have two sets, A and B. The Cartesian product A X B is the set of pairs (a, b) such that a belongs to A and b belongs to B. That's pretty easy, right? Just think of the aptly named Cartesian plane for an example, but keep in mind that our objects need not be numbers at all, but could be themselves pairs or sets or anything we choose (within the normal boundaries of set theory here).
On to relations! A relation is nothing more than a subset of a Cartesian product. Let's name our relation R, as is standard. Then a is said to be R-related to b if (a, b) is an element of R. That's pretty alright. It's worth noting that functions are relations, albeit relations with a special property.
Now let's consider the special case of A X A. That is, both the sets that we are Cartesian-producting are the same set. A convenient example would again be the standard Cartesian plane, but don't let your thinking get all boxed in to these number things. An equivalence relation R is a relation on (i.e., a subset of) such a Cartesian product, with three properties.
1. For all a in A, aRa. That means (a, a) is always a member of R. Another way of saying this is R is reflexive on A.
2. If aRb, then bRa; that is (a, b) in R implies (b, a) in R. In other words, R is said to be symmetric.
3. If aRb and bRc, then aRc; (a, b) in R and (b, c) in R implies (a, c) in R. R is said to be transitive.
This may all seem very abstract, so let's look at an example. In this case, A will be the set of triangles and R is the similarity relation. That is, triangles a and b are R-related if and only if their angles are congruent. You should recall that from geometry, but I find people tend to forget that kind of thing.
Is R an equivalence relation? We shall check the three conditions.
1. If we choose any triangle, is it similar to itself? I should hope this would be obvious.
2. If a is similar to b, is b similar to a? If the angles line up, then they obviously line up, regardless of which triangle we are looking at first.
3. If a is similar to b, and b similar to c, is a similar to c? The transitivity of the angles' congruency makes this fairly obvious, no?
So it's not that hard a concept to grasp. You could also look at congruency of triangles on this set and find you have another equivalence relation. Congruency would mean that the sides, in addition to the angles, would need to be of equal length for two triangles to be related.
So, why does this mean anything? Well, consider the case of equality in the usual sense. If you check, you will find that it meets those three conditions. What we have done here is generalize the idea of equality. In fact, if you look at the triangle example(s) again, you will find that we have found more than one way of defining equality on the set of triangles. That's pretty neat, right? Open problem for anyone (even though John no doubt has an answer ready already from number theory): can you come up with another (hopefully non-trivial) equivalence relation on the set of integers?
I tricked you into reading this post by giving it a non-math title.
Subscribe to:
Post Comments (Atom)
Posts
3 comments:
I work in Public Relations. That I can get my head around.
my weak sauce, barely nontrivial example: let A be the intuitive set of prime integers (greater than 1; excluding 1 is the important part), and let R(x,y) be our pal "x is divisible by y" (more rigorously, x is related to y iff x/y = k for some integer k).
then duh, x/x = 1, so reflexivity flies.
next, since we're dealing with primes, x/y = k iff y=x or y=1. but 1 isn't in A, so R(x,y) holds iff x=y, such that R(x,y) is equiv to R(x,x). same way with y/x, so R(y,x) is the same as R(y,y), which is also the same as R(x,x). to seal the deal, we already showed reflexivity, so this means symmetry is a go.
finally, suppose R(x,y) and R(y,z) hold for x,y,z ε A. then citing previous derivations, we can wave our hands and say that both R(x,y) and R(y,z) imply R(y,y), which is reflexivity FTW. with another wave, we can re-substitute to get R(x,z) from that. so, we have transitivity.
ergo, r-, s-, and t- are preserved, so R is an equivalence relation. any actual rigor is left as an exercise to those who actually care.
the only cool thing with this example is that it is a Rube Goldberg way to represent "pedestrian [numerical] equality" over the primes. it's extremely limited and inefficient, but what an esoteric delight!
the rest of my weird equivalence relations involve either groups, goats, or pie.
Very nice way of roundaboutting from that definition of primes, though I can't clearly remember the abstract algebra way of defining primality. I particularly like how it's just a bottleneck of normal equivalence to a smaller set. It's so abstract-y that I thought it was non-symmetric until I realized you had restricted the set to positive primes.
I was looking for congruency modulo a given integer, but your example is great and hilarious in that way that jazz is funny to people who understand it because of the notes that they don't play.
Post a Comment