Results 1 to 9 of 9
Like Tree7Thanks
  • 1 Post By chiro
  • 1 Post By johnsomeone
  • 1 Post By chiro
  • 1 Post By johnsomeone
  • 1 Post By chiro
  • 1 Post By Plato
  • 1 Post By HallsofIvy

Math Help - An infinite number of equivalence classes -- is this possible?

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Australia
    Posts
    14

    An infinite number of equivalence classes -- is this possible?

    For my assignment, one of the questions is 'how many equivalence classes are there for this relation and describe them.' I have come to the conclusion that there are an infinite number of equivalence classes, but I would like to know whether this is possible, and therefore correct. I don't want to copy and paste the question here -- lest I be accused of cheating -- so I will rephrase the question:

    The set T has a cardinality of infinity, and contains elements (I will call them horses) that are related to one another iff they contain the same number of hairs. Note: The number of hairs on a horse may be infinite.


    So horses are related iff they have the same number of hairs. That means that two horses are related to one another iff they both contain the same number of hairs out of the set of 0-infinity number of hairs, thus the equivalence classes are 0,1,2,3,4,...,infinity.

    Thanks for reading.
    Last edited by takaj; September 27th 2012 at 10:59 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,176
    Thanks
    767

    Re: An infinite number of equivalence classes -- is this possible?

    Hey takaj.

    The logic and reasoning sounds right, but the only thing is if you have to provide some kind of formal proof for your teacher/lecturer/professor.

    This will involve the whole cartesian product, equivalence relation, class thingy and I can't advise you on this since I haven't encountered these things for ages.
    Thanks from takaj
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: An infinite number of equivalence classes -- is this possible?

    It's a technical point, so I can't be 100% certain without reading a definition, but conceptually, and I'd bet technically too, there are no empty equivalence classes.

    For instance, if I consider the equivalence class of first names of Australian citizens, there isn't going to be an equivalence class - one that just happens to be empty - for the name "fhiafhihfehfibbkckzbkfefiefbfkbcsakhwhfhanvnzlcnn ", because no one has that name. The set of equivalence classes for that equivalence relation is formed from the set on which the equivalence relation is defined. Since no one one with a first name of "fhiafhihfehfibbkckzbkfefiefbfkbcsakhwhfhanvnzlcnn " was in that initial set (Australian citizens), it follows that there is no such equivalence class - not even an empty one - associated with the name "fhiafhihfehfibbkckzbkfefiefbfkbcsakhwhfhanvnzlcnn ".

    I'm pretty sure that to be an equivalence class requires containing at least one element from the original set. In your example, since there are only a finite number of horses on which this equivalence relation ("same number of hairs") is defined, there can only be a finite number of equivalence classes - and not, as you're suggesting, an infinite number of equivalence classes for which all but finitely many are empty.
    Last edited by johnsomeone; September 28th 2012 at 06:50 AM.
    Thanks from takaj
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,176
    Thanks
    767

    Re: An infinite number of equivalence classes -- is this possible?

    He did say there are an infinite number of horses (i.e. the cardinality of the set is infinite).
    Thanks from takaj
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: An infinite number of equivalence classes -- is this possible?

    Ah - yes - thanks.

    So it's possible that there are an infinite number of equivalence classes then. But it's also possible that all those horses have the same number of hairs, in which case there would be only one equivalence class. Or that (suppose they're countable, and then labelled 1, 2, 3, ...) all the even labelled horses have 150,189 hairs, and all the odd numbered horses have 93,445 hairs - in which case there are only two equivalence classes. Etc.
    Thanks from takaj
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,176
    Thanks
    767

    Re: An infinite number of equivalence classes -- is this possible?

    Yes very good point (and also having infinite hairs is probably a stretch). So it means that there needs to be some kind of map from T -> N union {0} and the equivalence relation needs to be done on this set instead.

    Hopefully this can be clarified by takaj.
    Thanks from takaj
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1

    Re: An infinite number of equivalence classes -- is this possible?

    Quote Originally Posted by chiro View Post
    Yes very good point (and also having infinite hairs is probably a stretch). So it means that there needs to be some kind of map from T -> N union {0} and the equivalence relation needs to be done on this set instead.
    This whole example is problematic on several levels.
    Unless one is a Platonist, there are no infinite sets in a real world.
    The example is easily fixed.
    Consider the collection of all finite subsets of \mathbb{N}.
    Using the idea in the OP, say two of these sets are related if and only if they have the same cardinality.
    Now the set of equivalence classes is denumerable.
    And all, except one, of the equivalence classes are denumerable.
    Thanks from takaj
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,453
    Thanks
    1868

    Re: An infinite number of equivalence classes -- is this possible?

    You have said that there are and infinite number of horses but you have only said "The number of hairs on a horse may be infinite."
    Yes, there may be an infinite number of equivalence classes but it is equally possible that all horses have the same number of hairs- in which there would be only one (non-empty) equivalence class.
    Thanks from takaj
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Sep 2012
    From
    Australia
    Posts
    14

    Re: An infinite number of equivalence classes -- is this possible?

    Thank you for your responses. To answer the question of how many equivalence classes there are, I will say that there could be an infinite amount, and not that there ARE an infinite amount. The lasts question wants me to describe them, so I will say that each equivalence class is defined by the cardinality of each set (i.e., the number of hairs).

    Thank you very much.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Equivalence classes
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 18th 2011, 09:12 PM
  2. Replies: 10
    Last Post: January 14th 2010, 01:28 PM
  3. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 07:36 PM
  4. Equivalence Classes
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 26th 2009, 03:04 PM
  5. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 04:39 AM

Search Tags


/mathhelpforum @mathhelpforum