Let A be a nonempty set, and let's partition it into several nonempty subsets. That is, let's break A apart into several pieces so that each piece is a nonempty subset of A that is disjoint (sharing no elements) with the other pieces such that all of the subsets union to A. I made a picture:
Now, let's call any two elements of A equivalent if they ended up in the same subset after the partition and denote this equivalence relation by "a ~ b" (where a and b are elements of A).
Problem 9: Show that an equivalence relation is reflexive, symmetric, and transitive. That is, for all elements a, b, and c in the set A,
- a ~ a,
- a ~ b implies that b ~ a, and
- a ~ b and b ~ c imply that a ~ c.
Problem 10: Is equality (=), as it is usually defined on numbers, an equivalence relation?
Problem 11: Show that the converse of problem 9 is also true - that any relation defined on a set's elements that is reflexive, symmetric, and transitive is an equivalence relation on that set.
Ok, so I should let you know that this is the first really new concept for me so far. I hadn't thought about the material in the previous problems in over a year and they were good practice (and fun), but this is new territory. So it may be a better test both of your teaching and my learning.
ReplyDeleteProblem 9:
Let X, Y, and Z be disjoint subsets of A such that the union of X, Y, and Z is equal to A. (That is, X,Y, and Z comprise all of A. (I'm not sure if this is necessary or not.)) Let a be an element of X.
Reflexive: We know that a~a because a is in X, and elements are equivalent if they are in the same subset.
Symmetric: If a~b, then b is in X. If b is in X, then b~a, because elements are equivalent if they are in the same subset.
Transitive: If a~b, then b is in X. If b~c, then c is in X. If c is in X, then a~c, because elements are equivalent if they are in the same subset.
And all of this rests on the fact that the subsets are disjoint. I see that I didn't use Y or Z above at all, and I guess I didn't even really have to bring them up to begin with (let alone specify that they are the only subsets of A after partition). Whatever.
Problem 10:
Yes, I think so. I guess in this formulation, every point on the number line -- every definable quantity -- is a subset. So, for example, sqrt(36) and 6 are equal because they are both elements of the same "subset". And equality is certainly reflexive, symmetric, and transitive.
I'm having a hard time wrapping my head around an "equivalence relation" that is not simply equality, though don't worry about clarification at this point. Let's just wait.
Problem 11:
I think I need a hint with this one.
Problem 9: Great. And yeah, you didn't need all of that at the beginning, but whatever helps you visualize it is fine. The only weak point is your part on it being reflexive. Instead of assuming that a is in a subset X of A and then concluding that a~a, you need to say why you know that there exists some subset X that contains a for any a in A. We know that X exists because we have broken A up into subsets that jointly contain all of its elements. So any element of A has to be in a subset and therefore, a~a.
ReplyDeleteI actually should have done a better job in the post (and I will now correct it) of saying that A is broken into mutually disjoint subset, the union of which equals A.
It's for this reason that symmetry and transitivity don't imply reflexivity. That is, we can't use the following argument: ~ is symmetric so a ~ b implies that b ~ a, but ~ is also transitive so a ~ b and b ~ c implies that a ~ c. If we let a = c, then this implies that a ~ a.
This concept is seemingly trivial, and yet, I've had a difficult time thinking about it, personally so don't be frustrated if this is confusing. Just take some time with it and ask questions.
Problem 10: Yep, I think you've got this one. All I was trying to get at is that if you take a set of numbers (integers, reals, whatever) and define an equivalence relation by partitioning the set into subsets that contain only one element apiece, then you have defined equality as an equivalence relation because each number is only equivalent to itself. In fact, one way to think about an equivalence relation is that it is a generalization of equality. It measures equality up to some property. What these properties are depends on the equivalence relation you define. We will be doing this with some examples in the next post.
Problem 11: Yeah, I figured this one wouldn't go over well. So here's the deal-
Hersein's book doesn't actually define an equivalence relation in the way that I did. He defines it as follows:
"A binary relation, ~, on A is said to be an equivalence relation on A if for all a, b, and c in A: 1) a ~ a; 2) a ~ b implies b ~ a; 3) a ~ b and b ~ c imply a ~ c."
So he doesn't define it in terms of partitioning a set, but rather as a relation that satisfies three properties. However, the two definitions are equivalent. That is, any partitioning of a set into mutually disjoint subsets defines a relation on the set that satisfies these three properties (as you have shown). And conversely, any relation defined on a set that satisfies those three properties will also result in a partition of the set into mutually disjoint subsets (which is what I wanted problem 11 to show).
The big, overall point is that these equivalence relations can be thought of either way, and either definition is acceptable.
So here's your hint: Take an equivalence relation on a set A as Hersein defines it, and let cl(a) denote the set of all elements of A that are "related" to an element a under the relation. This is called a's "equivalence class."
Also, hey, I went ahead and put up the second part of this which are some (mostly easy) examples about equivalence relations. You can wait and work them if you want to get through this stuff first, but I think they might be good for you to do now if you want something less abstract. Just know, that Herstein's definition is probably going to be easier to apply to those problems, and you should use it. But also, while you work them, keep the mental image of a set being partitioned from my definition.
ReplyDeleteI didn't make any progress on this yesterday because I was studying the central science (in preparation for a tutoring session). But now I'm back! Because we're moving next week, I'll probably be inconsistent, but keep these problems coming.
ReplyDeleteI don't get what you're saying about "symmetry and transitivity don't imply reflexivity". Are you just saying that you have to use reflexivity as a starting point when discussing those properties?
Also, you say, "...one way to think about an equivalence relation is that it is a generalization of equality. It measures equality up to some property." This explanation is really helpful for me, just to let you know.
I'm going to try out the problems in your next post before looking at number 11 again.
what in the fuck is the central science? did you just make that up?
ReplyDeletealso, it's fine to not be consistent. do these at your own pace. if you're gone for too long, i'll ask after you to see if you've given up out of frustration or boredom. i have several more posts of problems written and ready to go anyway so they'll be coming when we're ready to move on. if another student jumps ahead of you, then i will post them. but barry and ethan are still clowning around on problem 1. and just so you know, the next several posts are all about functions. while some of the problems might be challenging, there's nothing that will be new to you as far as i know in terms of material. so don't worry about me throwing something else as confusing as equivalence relations out there during your move. i hope that the move goes well!
To answer your question, no, reflexivity doesn't need to be a starting point. All I mean is that each property stands alone and cannot imply the others. In fact, one of the problems in the next post shows a relation that is symmetric and transitive but not reflexive (I guess that's a hint). Let me think for a little while on how to explain this better.
I am NOT making up the Central Science. Look it up!
ReplyDeleteAnd, I am pretty happy to find that reviewing the Central Science is going for me just like reviewing high school algebra/trig/precal -- now that I'm older and not prone to dismissing something just because I can't grasp it at first sight, it makes a hell of a lot more sense than it did back during my freshman year of college when I dropped the sciences in favor of a bunch of squishy bullshit.
(note - I still like the squishy bullshit too, just so we're clear)
So, I just started looking over these problems again. I'm really interested to see how something can be transitive and symmetric but not reflexive, because I can't imagine it at this point. On to the next problem set.
ReplyDeleteI'm still clueless about this. I'm not 100% sure what I'm trying to prove, really. Do I want to prove that if a relation satisfies those three properties, then it necessarily describes a partitioning of A into mutually disjoint subsets....one of which is the set of elements that satisfy the relation? Or is it just the set of elements that demonstrate those properties under the relation? This is killing me.
ReplyDeleteWould I start like this? Let cl(a) denote the set of all elements of A for which reflexivity, symmetry, and transitivity hold for an element a in cl(a). Then for every element a, b and c in cl(a), a~a, a~b implies b~a and a~b and b~c implies a~c. We want to show that there is NOT an element p that exists outside of cl(a) and for which the above properties still hold. So, imagine that p exists and thus...
...
It's not happening. Can we move on, or is this too important to what comes next to leave behind?
You're on the right track. I am asking to show that an equivalence relation necessarily describes a partitioning of A into mutually disjoint subsets. However, that's not really what I meant by cl(a). It's not that cl(a) is all elements that satisfy those properties since it is the relation that satisfies the properties and not the elements. What I'm saying is that cl(a) is the set of all elements to which a is related. So in the example of the equidistant points on the plane, if a is the point (0,1), then it is 1 away from the origin, and cl(a) would be the set of all points that are also 1 away from the origin including (0,1), (1,0), (-1,0), etc. cl(a) would be the circle of radius 1 about the origin. This would be disjoint from all of the other sets ( such as cl(b) for some other point b not on that circle) that we could produce from that equivalence relation.
ReplyDeleteNot getting it all right now is ok, but we will be dealing with it again pretty soon (after functions but before group theory) when we talk about the integers. So let me show you what I had in mind for how to prove this, and then keep talking to me about it here, but I'll also get another post up about functions so that we can move on.
Let ~ be an equivalence relation on a set A, and let cl(a) denote the subset of A that contains all elements b in A such that a ~ b. We want to show that all of the subsets of the form cl(a) union to A (that they "cover" all of A), and that they are all mutually disjoint (it's ok if cl(a) = cl(b) for two different elements a and b, but these sets must either be equal or disjoint).
Let x be an element of A. Since ~ is reflexive, then x ~ x. Thus, x is an element of the subset cl(x). Therefore, every element of A is in one of these subsets. (this shows the "covering")
Now, let x and y be elements of A. Either x ~ y or not. If x ~ y, then let's show that cl(x) = cl(y) using the argument we did before showing that an element of one must be in the other and vice versa. So let a be an element of cl(x), then x ~ a, and by symmetry a ~ x. Since a ~ x and x ~ y, then a ~ y by transitivity and by symmetry again, y ~ a. Thus, a is also in cl(y). By a similar argument we can show that any element of cl(y) is in cl(x). So cl(x) = cl(y) if x ~ y.
If x is not related to y, then we must show that cl(x) and cl(y) are disjoint subsets. So let a be an element of cl(x). If a is also an element of cl(y), then x ~ a and also y ~ a. By the properties of the equivalence relation ~,this means that x ~ y - a contradiction. Therefore, the two sets must be disjoint.
So now we have shown that these sets are all disjoint.
What do you think about that? Were any of these steps unclear? I find that it's difficult to read other people's proofs often when they obviously know where they're going but you don't so I attempted to make this one more of a road map rather than a concise proof. I hope that it is ok.
Anyway, I'll go ahead with the functions. The important part is that you understand what an equivalence relation is via the three properties. Being able to think about them as a partitioning of a set is pretty powerful though so keep at it.
I just glanced at the wikipedia page for the central science and was disappointed to see that it's just chemistry. I like diagram on the page, but a lot of those arrows are pretty dubious. Anyway, I hope that it's fun - I'm not trying to mock chemistry itself, but I was just hoping that "the central science" was some new powerful science that combined a lot of other science into one (maybe that's what you hope to find in engineering?).
ReplyDelete