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 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!

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

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}$.)

The logic seems fine to me. I assume that (3) was a technical lemma needed to prove one of the significant points above.

share|cite|improve this answer
$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
@Belgi: I thought that it was probably something like that, but since it didn’t affect the overall logic of the argument, which is all that concerned me, I didn’t worry about the details. – Brian M. Scott Oct 17 '12 at 13:22

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.