Thread: 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.

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.

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.

He did say there are an infinite number of horses (i.e. the cardinality of the set is infinite).

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.

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.

Originally Posted by chiro

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 .
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.

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.

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.