Is indistinguishability an equivalence relation?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.