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

I am having difficulties determining if this relation is reflexive, symmetric, transitive, or none of these.

Let A be the set of all strings of $0's$, $1's$, and $2's$ of length $4$. Define a relation $R$ on $A$ as follows: For all $s$, $t ∈ A$, $s$ R $t$ if and only if the sum of the characters in s equals the sum of the characters in t.

Examples this is true:

$0121$ R $2200$

$1220$ R $2111$

share|cite|improve this question
up vote 1 down vote accepted

Tip: Any relation that is defined like $aRb$ iff $f(a)=f(b)$ for some function $f$ is an equivalence. Try if you can prove that.

Protip: The converse also holds by passing to the quotient.

share|cite|improve this answer

Reflexive means $aRa$ for every $a$. But clearly sums are the same for $a$ and $a$, so it is reflexive.

Symmetric means if $aRb$ then $bRa$ - so since $aRb$, both $a,b$ have the same sum, so $bRa$ is true.

Transitive means $aRb$ and $bRc$ imply $aRc$. Note that $aRb$ and $bRc$ means $a,b$ and $b,c$ have same sum, so $a,c$ must have it too, and thus $R$ is transitive.

Any relation with all 3 properties is called an equivalence relation, and this one is an equivalence relation indeed.

share|cite|improve this answer

HINT: I suspect that you’re letting yourself think it harder than it really is.

  • Reflexivity: If $a_1a_2a_3a_4\in A$, is it true that $a_1+a_2+a_3+a_4=a_1+a_2+a_3+a_4$? That’s exactly what’s required in order for $R$ to be reflexive.

  • Symmetry: If $a_1a_2a_3a_4,b_1b_2b_3b_4\in A$ and $a_1+a_2+a_3+a_4=b_1+b_2+b_3+b_4$, is it true that $b_1+b_2+b_3+b_4=a_1+a_2+a_3+a_4$? That’s exactly what’s required in order for $R$ to be symmetric.

Now see if you can deal with transitivity completely on your own.

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.