Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – wj32 Oct 31 '12 at 5:50
up vote 2 down vote accepted

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.

share|cite|improve this answer
Thank you for the hint and the advice! I will definitely keep this in mind for when I work through future problems like this. – user41419 Oct 31 '12 at 6:08

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.