Results 1 to 7 of 7

Math Help - Set Theory - Partitions and Equivalence Relations

  1. #1
    Member
    Joined
    Dec 2010
    Posts
    107

    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.
    Attached Thumbnails Attached Thumbnails Set Theory - Partitions and Equivalence Relations-lectures1.pdf  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2010
    Posts
    107
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    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 a \in A. Then by reflexivity of R, a R a. So a \in [a]. If A=\{b_1,b_2,\dots\}, then by definition \bigcup_{b\in A} [b]=[b_1]\cup[b_2]\cup\dots. Also, if \mathcal{P}_R=\{P_1,P_2,\dots\}, then by definition \bigcup_{P \in \mathcal{P}_R} P=P_1\cup P_2\cup\dots. Besides, each P\in\mathcal{P}_R is [b] for some b\in A and vice versa. Hence a \in \bigcup_{b\in A} [b]; that is, a \in\bigcup_{P \in \mathcal{P}_R} P. Thus we showed that for every a\in A, a \in\bigcup_{P \in \mathcal{P}_R} P. Hence A \subseteq \bigcup_{P \in \mathcal{P}_R} P. On the other hand, if P \in \mathcal{P}_R, then for some a \in A, P = [a] = \{b \in A : a R b\}; so P \subseteq A. Therefore, P_1\cup P_2\cup\dots\subseteq A. Hence \bigcup_{P \in \mathcal{P}_R} P \subseteq A. Hence \bigcup_{P \in \mathcal{P}_R} P = A.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Dec 2010
    Posts
    107
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 19th 2011, 02:09 PM
  2. Help with relations/partitions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 7th 2011, 01:00 AM
  3. Replies: 12
    Last Post: December 3rd 2010, 12:41 AM
  4. Replies: 10
    Last Post: January 14th 2010, 01:28 PM
  5. Equivalence Classes & Partitions
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: March 3rd 2009, 05:58 PM

Search Tags


/mathhelpforum @mathhelpforum