How to prove $R=\{(x,y)\mid x ,y\} $ is an equivalence relation?

Question

$R=\{(x,y)\mid x,y\; \text{are 5 bit strings with equal numbers of zeros }\}$ Prove that $R$ is an equivalence relation. How much classes does it have?

Apply the definition checking if the relation $R$ has the desired properties- — Mauro ALLEGRANZA, Dec 15 '19 at 13:13
I am thinking that you mwan that the relation is between bit strings and they are related if they have equal number of zeros. Correct? Suppose the bit strings have only a single bit each. What are the bit strings and how are they related? Can you solve the problem in that case? — Somos, Dec 15 '19 at 13:15
@BerianidzeLuka Being a member for more that $2$ years you should know by now that you are expected to show your efforts on this. Not in a comment but in the question itself. — drhab, Dec 15 '19 at 13:20
I have only ideas how to solve this, but in practice it doesn’t work — Berianidze Luka, Dec 15 '19 at 13:22
Can you state the defining properties of an equivalence relation? Which point in particular do you find difficult? — lulu, Dec 15 '19 at 13:23
Yeah,it should be symmetric ,reflexive and transitive to be equivalnce — Berianidze Luka, Dec 15 '19 at 13:24
Oh,if we have array R , where for any (x,y) E R, xFy and yFx — Berianidze Luka, Dec 15 '19 at 13:29
Well, almost. here is a handy reference. But, in any case, you need to apply this to the relation at hand. If $a, b$ are two binary strings of length $5$ and $a$ has as many zeroes as $b$, does that imply that $b$ has as many zeroes as $a$? — lulu, Dec 15 '19 at 13:37
I don't want to chat about it. Please edit your post to show some effort! There are only three things to check, and each of them is really quite simple. — lulu, Dec 15 '19 at 13:40
Yeah,I have already proved that this is equivalence. But what about classes? I think there is 4 classes,because we can not involve 00000 in them,there is only one object with 5 zeros and it doesn't have pair. Am I right? — Berianidze Luka, Dec 15 '19 at 13:42
No. Every element in the set has to be exactly one equivalence class. As you remark, $00000$ is in a class by itself, but that's fine. Indeed, on any set you can have an equivalence relation out of $a\sim a$ with no other relations. — lulu, Dec 15 '19 at 13:53
So how can it be? We have just 5 bits,maximum is 5. We have pair for all. Can it be greater? — Berianidze Luka, Dec 15 '19 at 13:56
Try a simpler example. Suppose you do the same thing for strings of length $1$. How many such strings are there? How many classes? — lulu, Dec 15 '19 at 13:58
If 1,there can only be two lines 0

0 is in only 1 line,so It think answer is 1 — Berianidze Luka, Dec 15 '19 at 13:59
I don't know what "two lines" means in this context. Just write down all the strings. Count the equivalence classes. — lulu, Dec 15 '19 at 14:00
How many zeroes may appear at all in a 5 length bit strings. — Berci, Dec 15 '19 at 14:01
Let's do that for three bit strings. 000 001 010 011 100 101 110 111. 0 is in 7 of them. — Berianidze Luka, Dec 15 '19 at 14:03
The underlying set is "all strings of the given length." Not "all strings in which $0$ appears.". — lulu, Dec 15 '19 at 14:08
Why not? Every string will create pair with itself ,but + with others. (00000,00000) (00001,00001) ... (00001,10000). I need to count them all? — Berianidze Luka, Dec 15 '19 at 14:11
I don't understand. Once again: there is no reason you can't have an equivalence class with only one element in it. That's perfectly ok. There are two strings of length $1$, for instance. $0$ and $1$. They are not equivalent to each other. — lulu, Dec 15 '19 at 14:12
Show some effort! I just did length one for you. There are two classes in that case. Now you do length two. — lulu, Dec 15 '19 at 14:14

score 1 · Accepted Answer · answered Dec 15 '19 at 14:13

1

Consider the function $f$ that assigns the number of zeroes to its input which is a bit string of length $5$.

It's straightforward that $R$ is just the 'kernel' of $f$, i.e. $(x,y)\in R\iff f(x)=f(y) $.

The number of equivalence classes of $R$ are thus corresponding to the possible values (=elements of the range) of $f$, which in this case is $\{0,1,2,3,4,5\}$.

answered Dec 15 '19 at 14:13

Berci

90,745

So classes count is 6? – Berianidze Luka Dec 15 '19 at 14:15
Yes, exactly. ${{{}}}$ – Berci Dec 15 '19 at 14:16
0 is because of having line 11111 which contains 0 zeros? – Berianidze Luka Dec 15 '19 at 14:18
Yes, that element (and also $00000$) forms an equivalence class with a single element. – Berci Dec 15 '19 at 14:19
00000 - 5 00001 - 4 00011 - 3 00111 - 2 10000 - 1 11111 - 0 something like that,right? – Berianidze Luka Dec 15 '19 at 14:20
Yes, something like that. Just I'd rather write '$\mapsto$' to denote the function assignment in place of your '-'. Also, $10000\mapsto 4$ and not $1$. – Berci Dec 15 '19 at 14:22
'-' is count of zero in string – Berianidze Luka Dec 15 '19 at 14:23
Yes, or just use the notation $f('10000')=4$. – Berci Dec 15 '19 at 14:25
That's right! Thank you for the clear answer! – Berianidze Luka Dec 15 '19 at 14:25
Note that it's a generally applicable method: if a relation is defined as (some property of two objects coincide), you can just define the function to the set of given properties. – Berci Dec 15 '19 at 14:28

How to prove $R=\{(x,y)\mid x ,y\} $ is an equivalence relation?

1 Answers1