Relations: Reflexive, symmetric, transitive

Question

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$

Answer 1

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.

Answer 2

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.

Answer 3

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.