# Proving what are the equivalence classes of the relation $R_{L}$

I tried writing a solution for a question that defined a language $L$ and asked to find the equivalence classes of the relation $R_{L}$

The TA wrote that "this is not what you should prove" (or "this is not what should be proven") [in free translation].

I wish to know if I actually gave the correct claims that needs to be proven (I do not ask if their proof is correct, but rather on the logic - are my claims a proof assuming their proof is correct).

These are the steps of my proof:

1) for every $n\in\mathbb{Z}$ I defined $A_{n}$. I believed (and this was marked as correct) that those are the equivalence classes of the relation $R_{L}$ .

I have proved:

2) $\forall n\in\mathbb{Z}:\, A_{n}\neq\emptyset$ (I used it to prove another claim)

3) Let $n\in\mathbb{Z}$and $x,y\in A_{n}$ then $\forall z\in\Sigma^{*}:\, xz\in A_{n}\iff yz\in A_{n}$

4) $x\sim y\iff\exists n\in\mathbb{Z}:\, x,y\in A_{n}$ is an equivalence relation

5) $\forall w\in\Sigma^{*}:\exists n\in\mathbb{Z}:\, w\in A_{n}$

6) $x\sim y\implies xR_{L}y$

7) I concluded that by the above $\sim$ refines $R_{L}$

8) Let $n_{1}\neq n_{2}\in\mathbb{Z},x\in A_{n_{1}},y\in A_{n_{2}}$ then $\exists z\in\Sigma^{*}:xz\in L,yz\not\in L$ .

9) I concluded that all the $A_{n}$ are indeed the equivalence classes of $R_{L}$.

Is there a problem with my logic ? I believe that these steps are correct (in terms that if they are correct I proved that all the $A_{n}$ are indeed the equivalence classes of $R_{L}$) but I got $0$ point (out of $10$).

I would appreciate any help in figuring out if there is anything wrong in the way I have proved the claim!

-

Let me make sure that I understand what you did. In (2) you proved that the sets $A_n$ are non-empty. In (4) you proved that they are pairwise disjoint, so that they form a partition of their union, and you defined $\sim$, the corresponding equivalence relation on $\bigcup_nA_n$. In (5) you showed that $\bigcup_nA_n=\Sigma^*$ and hence that $\sim$ is an equivalence relation on $\Sigma^*$. In (6) you proved that the partition $\{A_n:n\in\Bbb N\}$ refines the Myhill-Nerode partition $\mathscr{P}$; (7) just restates this. In (8) you showed that if $x\not\sim y$, then $x(\lnot R_L)y$. Thus, distinct members of $\{A_n:n\in\Bbb N\}$ are contained in distinct members of $\mathscr{P}$, and $\{A_n:n\in\Bbb N\}=\mathscr{P}$. (Equivalently, (6) and (7) combine to give you $x\sim y$ iff $x\,R_L\,y$, and hence $\{A_n:n\in\Bbb N\}=\mathscr{P}$.)
$3)$ is to show that the relation $\sim$ is invariant from the right (if this is the correct terminology) and was used to get $7)$ by the theorem that say that every equivalence relation on $\Sigma^{*}$ is invariant from the right and refines $L$ also refines $R_{L}$ – Belgi Oct 17 '12 at 13:19