Relation and Function problems

Question

Trying to solve these problems for a whole day, but just can't figure out where to start.

let $\Sigma=\{a,b\}$ and $L = \{w \in\Sigma^*: 3\mid\text{length}(w)\}$

Define R ⊆ Σ * × Σ * as follows: (w, w' ) ∈ R if there is a v ∈ Σ * such that: either wv ∈ L and w 'v ∉ L, or wv ∉ L and w 'v ∈ L.

Define $S\subseteq\Sigma^*\times\Sigma^*$ as the complement of $R$. That is $(w, w') \in S$ iff $(w, w')\notin R$.

1. State a simple rule for determining if $(w, w') \in S$
2. show that $S$ is an equivalence relation
3. How many equivalence classes does $S$ have?

---

Any tips or direction will be much appreciated.

Answer 1

If I understand well then $wSw'$ iff $$\text{length}(w)\equiv\text{length}(w')\mod 3$$or equivlently:$$3\mid\text{length}(w)-\text{length}(w')$$

This can also be expressed by: $$f(w)=f(w')$$where $f:\Sigma^*\to\{0,1,2\}$ is the function prescribed by $$w\mapsto\text{length}(w)-3\lfloor\frac13\cdot\text{length}(w)\rfloor$$

On base of $wSw'\iff f(w)=f(w')$ it is easy to prove that $S$ is an equivalence relation:

• $f(w)=f(w)$ for all $w\in\Sigma^*$ so reflexivity.
• $f(w)=f(v)\implies f(v)=f(w)$ so symmetry.
• $f(w)=f(v)\wedge f(v)=f(u)\implies f(w)=f(u)$ so transitivity.

The equivalence classes are the sets:

• $f^{-1}(\{0\})=L$
• $f^{-1}(\{1\})=\{vw\mid v\in\Sigma\wedge w\in L\}$
• $f^{-1}(\{2\})=\{uvw\mid u,v\in\Sigma\wedge w\in L\}$