Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

3 Answers

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.