Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Empty relation and equivalence classes

  1. May 5, 2009 #1
    These two terms would be the simplest terms in the set theory as they are on the first chapter in my textbook. But why cant i understand it?
    In my textbook it says

    A relation R in a set is a set of ordered pairs, so any subset of a set of ordered pairs will be a relation. This includes the empty set which is referred to as the empty relation.

    What is this mean? empty set = empty relation? and if so then why empty relation is symmetric as well as transitive? My teacher said it is done by default but i still can not understand it.

    In case of equivalence class i understand the concept and i thought it was easy. An equivalnce relation on Set partitions Set into subsets which are called equivalence classes. Good enough not difficult. But in the example where

    A = {1, 2, 3, 4} and define a relation R by: xRy <-> x + y is even.

    The relation is equivalence relation. R = {(1, 1), (1, 3), (3, 3), (3, 1), (2, 2), (4, 4), (4, 2)}
    and they say equivalence classes : {1, 3} and {2, 4}

    This i can not understand.. why only these two? doesnt {1 ,1} {2, 2} {3, 3} {4, 4} counted?

    Set theory is too hard..I thought i understood everything and when i look back everything is new! well that must be because i couldnt have enough time for revision but this is too much.

    Any definitions of empty relation and equivalence class that can be understood by person like me?
     
  2. jcsd
  3. May 5, 2009 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper


    If X is a set with an equivalence relation R, then R is a relation on any subset of X, including the empty set

    The rules for an equivalence relation say things like 'R satsifies: for all x in X...'. Well, if we let X be the empty set then 'for all x in X' is always false, and any implication of the form False => True is true. So the empty set with any relation is an equivalence relation, but it has no equivalence classes, and is very boring. But it makes the statement of the theorems easier - it is generally better to allow the empty set to be a trivial example, rather than make statements like : for all subsets of X except for the empty set.

    Note these are elements of AxA.

    and these are subsets of A - you just have to amalgamate all of the elements of A that are related by the relation, i.e. (1,1) (1,3) (3,1) and (3,3) show that the equivalence class containing 1 is {1,3} a subset of A.

    because you're confusing (1,1) as an element of AxA with the symbol {1,1} which isn't allowed as sets don't have repeated elements.


    In general I would never teach that an equivalence relation is a subset of AxA satsifying... because it is completely unhelpful and unnecessary.

    An equivalence relation should just be defined like '=', cos that is all it is.
     
  4. May 5, 2009 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Here are some simple examples.

    Start with the integers, Z.


    We'll say that x~y if 2 divides x-y. What are the equivalence classes? They are the odd integers and the even integers. We can choose a representative of each: [0] and [1] would seem to be good candidates.


    What about the real numbers R. I'll say that x~y if x-y is an integer, i.e. if x and y have the same fractional part. Is there a good candidate for each equivalence class now? Yes there is - since two things are equivalent if and only if their fraction parts are the same, consider the set

    [0,1) = { x : 0<= x < 1}

    this forms a complete set of the representatives of equivalence classes.
     
  5. May 5, 2009 #4
    Ohhhhhh I got it know! so R={()} things are the element of AxA and the subsets of A{1, 2, 3, 4} are {1, 3} and {2, 4} as repeated elemtns are not allowed.

    But in the explanation of empty set i can not understand this line
    and any implication of the form False => True is true
    Sorry my english is not good enough; maybe this is related to the vacuous truth right?

    Anyways thankyou very much for your explanation it really helped me a lot :)
     
  6. May 5, 2009 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Matt, I don't think that's what the OP was referring to! The empty relation is when the *relation* itself is empty, not when the set it operates on is empty. So for the set {1, 2} the relation ~ that has
    1 ~ 1
    1 ~ 2
    2 ~ 1
    2 ~ 2
    as false is the empty relation on {1, 2}. By comparison, the operator < has
    1 < 2
    true and
    1 < 1
    2 < 1
    2 < 2
    false.


    Formally the relation < would be defined (on the set {1, 2}) as {(1, 2)} and the empty relation would be defined as {}. = on the same set could be defined as {(1, 1), (2, 2)}.


    A relation is symmetric if for every a ~ b you have b ~ a. For the empty relation a ~ b is always false, so the empty relation is always symmetric. Similarly, if you apply the definitions you'll see that the empty relation is always associative, transitive, and antisymmetric. The empty relation is reflexive only over the empty set. For example, the empty relation over {1, 2} is not reflexive because 1 ~ 1 is not true. But the empty relation over {} is reflexive (because being reflexive over {} doesn't require anything!).
     
    Last edited: May 5, 2009
  7. May 5, 2009 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Thanks for clearing that up, CR, but what you said apparently contradicts what the OP's teacher is reported to have said about it being transitive. (I've never heard of the empty relation, and was taking the only logical definition given the original post in order to make an equivalence relation, which was probably a silly thing to do. The empty relation of course is not an equivalence relation as you point out except in the trivial case.)
     
  8. May 5, 2009 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    The empty relation is transitive, though. Being transitive means that if a ~ b and b ~ c, then a ~ c. But the first condition never holds, so the empty relation is always transitive.

    The empty relation isn't reflexive (except over the empty set, as I mentioned), but that's not a problem -- the OP's teacher didn't claim that the empty relation was an equivalence relation, just symmetric and transitive.

    385sk117: Understanding equivalence relations can be tricky, since it requires you to learn new concepts and hold them all in your mind at the same time without confusing them with other ones. The empty relation easy -- maybe the easiest thing. It only seems hard because you're looking for something hard.

    You can think of a relation like this: you give it two things (in order), and it tells you if they're related. You say 1 and 10, and "<" tells you "They're related, 1 < 10"; you say 3 and 2 and "<" tells you "They're not related, 3 < 2 is false". In that case the empty relation is the one that is stuck in the 'no' mode, "Not related".
     
  9. May 5, 2009 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Sorry, I read 'reflexive' and remembered 'transitive'.
     
  10. May 5, 2009 #9

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    T'happens.
     
  11. May 5, 2009 #10
    I understood why empty relation is symmetric, transitive but not reflexive by default.
    Empty relation is relation which can not be satisfied by the elements within the sets right? So there is no ordered pair in it. R = {} nothing.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Empty relation and equivalence classes
  1. Equivalence Class (Replies: 0)

  2. Empty relation (Replies: 3)

  3. Empty relation (Replies: 3)

  4. Equivalence classes (Replies: 6)

Loading...