# Is indistinguishability an equivalence relation?

Let x and y be strings and let L be any language. We say that x and y are distinguishable by L if some string z exists whereby exactly one of the strings xz and yz is a member of L; otherwise, for every string z, $xz \in L$ whenever $yz \in L$ and we say that x and y are indistinguishable by L. If x an y are indistinguishable by L we write $x \equiv_L y$. Show that $\equiv_L$ is an equivalence relation.

It seems quite obvious to me, it is reflexive, symmetric and transitive. I have no idea as to how should I write a formal proof. I'd appreciate some help.

-

Let $\Sigma$ be the alphabet, and let $x\in\Sigma^*$; clearly for each $y\in\Sigma^*$ we have $xy\in L$ iff $xy\in L$, so $x\equiv_L x$, and since $x$ was arbitrary, $\equiv_L$ is reflexive.

Now let’s look at transitivity. Suppose that $x,y,z\in\Sigma^*$, $x\equiv_L y$, and $y\equiv_L z$; we want to show that $x\equiv_L z$, which means that we want to show that for any $u\in\Sigma^*$, $xu\in L$ iff $zu\in L$. Suppose that $u\in\Sigma^*$ and $xu\in L$. Since $x\equiv_L y$, this implies that $yu\in L$; and since $y\equiv_L z$, that implies that $zu\in L$. If, on the other hand, $xu\notin L$, then the fact that $x\equiv_L y$ tells you that $yu\notin L$, and the fact that $y\equiv_L z$ then tells you that $zu\notin L$. Thus, $xu\in L$ iff $zu\in L$, and we do indeed have $x\equiv_L z$. Again, $x,y$, and $z$ were arbitrary, so $\equiv_L$ is transitive.

I’ll leave symmetry to you; it shouldn’t be too hard after seeing proofs that $\equiv_L$ has the other two properties.

-
I would have preferred transitivity to be the one left as an exercise, though. Symmetry is too easy. – Tara B Mar 2 '13 at 17:01
@Tara: I thought about it, but I’ve a suspicion that the problem here is more with the writing than with the concept, so I wanted to show a bigger example. – Brian M. Scott Mar 2 '13 at 17:04
Yes, fair enough. I did vote up your answer. – Tara B Mar 2 '13 at 17:04
I'm fairly sure your transitivity proof is unnecessarily long. Could you please have a look at mine and see if I'm making silly tired mistakes? – Tara B Mar 2 '13 at 17:11

If $1$ is distinguishable from $2$ and $2$ is distinguishable from $1$, then transitivity would imply $1$ is distinguishable from $1$. That doesn't make sense for any notion of distinguishability that I know.

But I expect that indistinguishability, by some reasonable definitions, would be an equivalence relation.

-
Although the title asks if distinguishability is an equivalence relation, the actual question is asking whether or not indistunguishability is an equivalence relation. – Stahl Mar 2 '13 at 16:56
@Stahl: True! Except now the title asks the right thing... – Tara B Mar 2 '13 at 17:00

If you use the definition of indistinguishable in the question (rather than the negation of the definition of distinguishable), the proof for transitivity can be made much shorter:

Let $x,y,z\in \Sigma^*$ with $x\equiv_L y\equiv_L z$. Then whenever $u\in \Sigma^*$ with $zu\in L$, we also have $yu\in L$, and hence $xu\in L$. So $x\equiv_L z$. Hence $\equiv_L$ is transitive.

-
Yes, you can do this, if you follow the definition as given in the quoted passage. On the other hand, that definition isn’t the negation of the definition of distinguishability that immediately precedes it, though of course it’s equivalent. I was actually working from the negation of distinguishability and didn’t notice that the source had replaced it with a formally weaker condition. – Brian M. Scott Mar 2 '13 at 17:17
Right, I see. Yes, the question does look a bit odd to me because of the definitions not being the formal negation of one another, especially given that part of what one then has to prove (symmetry) is required to show that they actually are 'complementary' definitions. – Tara B Mar 2 '13 at 17:24