1
$\begingroup$

Let $A = \{0, 1\}^8$. Define the relation $R$ on $A$ as

$R = \{ (u, v) \in A \times A | \text{u and v have the same number of entries equal to 0}\}$

How can I show that $R$ is an equivalence relation on $A$? I know that $R$ must be reflexive, symmetric, and transitive, but I'm a bit stuck on the actual proof.


For reflexivity, I believe the following work I have is true. $(u, u) \in A$ since $u$ and $u$ obviously have the same number of entries equal to 0. Is this sufficient to prove reflexivity?

I also think I've worked out the symmetry part. For $(u, v) \in R$, since $u$ and $v$ have the same number of entries equal to 0, then naturally $v$ and $u$ are the same case, and so $(v, u) \in R$. Correct?

I have no idea about the transitivity part yet.

$\endgroup$
  • 1
    $\begingroup$ If $w(s)$ denotes the number of entries in $s$ set to 0, then $uRv \Leftrightarrow w(u)=w(v)$. We know $=$ is an equivalence relation, so $R$ is an equivalence relation. $\endgroup$ – wj32 Oct 31 '12 at 5:50
1
$\begingroup$

The first two parts are fine as they are (except perhaps the formulation "are the same case"). For the transitivity: If $u$ and $v$ have the same number of zeros and $v$ and $w$ have the same number of zeros, what can you say about $u$ and $w$?

A general piece of advice: Don't be daunted by formal expressions that you're not quite familiar with. Things often turn out to be a lot more common-sensical than they may seem when you first encounter them. In the present case, transitivity is a very natural concept, which you can get a feel for if you see it as something that you can grok rather than a forest of variables and quantifiers.

$\endgroup$
  • $\begingroup$ Thank you for the hint and the advice! I will definitely keep this in mind for when I work through future problems like this. $\endgroup$ – user41419 Oct 31 '12 at 6:08
1
$\begingroup$

Your reasoning about reflexivity and symmetry are correct.

To show transitivity, note that if $u$ and $v$ have the same number of zero entries, and $v$ and $w$ have the same number of zero entries, then $u$ and $w$ have the same number of zero entries.

This is simply an exercise to get you familiar with proving such things.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy