Thread: Set Theory - Partitions and Equivalence Relations

I'm having trouble understanding something that was in lectures on set theory. Unfortunately I am not experienced enough in latex to be able to write it out, so have attached a pdf.
(page 10) I am struggling with the theorem:

Theorem 3.1.8. Let A be any set. Then to each equivalence relation R on A there
corresponds a partition PR, and to each partition P of A there corresponds an equivalence relation RP.

If anyone could help me understand the proof I would be most grateful. I get to about line 5 before I just loose track of whats going on completely.

It's a hard to help you here - to give more details for the whole proof would be too time consuming, and may end up confusing you more. I think you need to ask specific questions about what you're having trouble understanding. For example, do you understand the definition of a partition? Can you write out specific examples of partitions? Do you understand what an equivalence relation is, and what equivalence classes are?

One suggestion I have for you when reading the proof, is to use a specific example as you read the argument, and draw lots of pictures. Pick your favorite equivalence relation, and draw the corresponding partition. Then pick your favorite partition and draw the corresponding equivalence relation. Then read the argument and see how it applies to your specific examples.

Again, if you can ask some specific questions it will be much easier for me to help you understand.

I understand the concept of partitions and equivalence relations, but not entirely sure about equivalence classes.
As for the proof, I really start to get stuck when unions start becoming involved (around line 7-8 of the proof) and I can't understand it from there no matter how many times I read it through.
Thanks for the help!

Perhaps we should look at a simple example. Consider the equivalence relation ~ on Z (the set of integers), defined by n ~ m precisely when n - m is even. See if you can verify that this is an equivalence relation.

There are 2 equivalence classes - the odds and the evens. These 2 equivalence classes form a partition of Z because they are disjoint (no even is odd and vice versa), and every integer is either even or odd.

Conversely, if you partition the integers into the evens and the odds, the two sets in the partition are precisely the equivalence classes of the original equivalence relation I gave you.

Perhaps we should look at a simple example. Consider the equivalence relation ~ on Z (the set of integers), defined by n ~ m precisely when n - m is even. See if you can verify that this is an equivalence relation.

There are 2 equivalence classes - the odds and the evens. These 2 equivalence classes form a partition of Z because they are disjoint (no even is odd and vice versa), and every integer is either even or odd.

Conversely, if you partition the integers into the evens and the odds, the two sets in the partition are precisely the equivalence classes of the original equivalence relation I gave you.

An equivalence class is a (maximal) set of elements all of whom are equivalent. Here is another example. Consider the following relation on integers: x R y iff x and y have the same sign, which is the same thing as xy > 0. Then all positive integers are equivalent; they form one equivalence class. All negative integers are also equivalent; they form another. Finally, 0 is not equivalent to anything; it forms the third equivalence class by itself. I inserted some explanations using a color; I am not sure if this made it easier or twice as hard...

The following paragraph from p. 10 shows that equivalence classes of R cover the whole set A. This is one of the conditions that say that the equivalence classes form a partition of A; the other is that different equivalence classes are disjoint.

Suppose that . Then by reflexivity of R, a R a. So . If , then by definition . Also, if , then by definition . Besides, each is [b] for some and vice versa. Hence ; that is, . Thus we showed that for every , . Hence . On the other hand, if , then for some , ; so . Therefore, . Hence . Hence .

Ok I think I get this proof now, though whether I could reproduce it in an exam is a different matter :S
Thanks for the help guys!