[Math] Equivelence classes, how many there are, and how many elements they have.

discrete mathematics

I've been struggling to understand equivalence classes. Say I have a set T, the set of all binary strings, and the relation S on T = {(a,b) | length(a) = length(b)}.

How would I write down the equivalence class of 00? What about 101?
How do I know how many equivalence classes there are, or how many elements are in an equivalence class?

Thanks.

Best Answer

Equivalence classes can be looked at in two different ways. One is in terms of the definition - for example the problem you have described above.

The other way is that an equivalence relation breaks a set into disjoint subsets (disjoint meaning they don't share any members). This is a much easier way of visualising an equivalence relation.

Consider all natural numbers N = {1, 2, 3 ....}. Define an equivalence relation R such that xRy if (x-y) is divisible by two. This means x and y are both even or both odd (try some numbers to see that this is true). So this equivalence relation divides all numbers into one of two disjoint sets, being {1,3,5,7 ...} and {2,4,6...}. If xRy either both x and y are both from the even set or both from the odd set.

Now lets look at your example. Possible strings are "0", "1", "00", "01", "10", "11", "000", "001" ...

The rule is that xRy only if they have the same number of digits (same length of string). So one equivalence class is all strings of length 1, ie {"1", "0"}. So for example "1"R"0" is a valid relationship.

Another equivalence class is all strings of length 2, being {"00", "01", "10", "11"). So for example "10"R"01" is true.

Another equivalence class is all strings of length 3, of which there are eight, {"000", "001" ..... "111"}. "010"R"101" is true.

There is another equivalence class of size 16 (16 elements) for strings of length 4, and so on.

In the question, strings can be infinite, and these all form one single equivalence class - strings of infinite length. So for example "0000..."R"1111....", all infinite strings are in the same equivalence class.

When solving these, the easiest thing to do is defines the disjoint sets that form the equivalence classes - odd and even numbers in my first example, or sets comprising binary strings of length 1,2,3.. plus infinite strings. When you visualise these sets, its easy to see what the equivalence relation actually is.

Note that as your question seems to allow strings of zero length, there is one additional equivalence class which comprises all binary strings of length zero. Its only member is "" (the empty string) and the only relation is ""R"" so its the trivial case.

Related Question