# Union of right congruence relations

Since we started talking about relations on languages and so on i keep on struggling with this subject.

So now iam faced with two questions where i really dont know how to start.

1. First of all, the natural relation of a language $L \subseteq \Sigma^*$ is the equivalence relation on $\Sigma^*$ with the equivalence classes $L$ and $\Sigma^* \setminus L$

Let the natural relations of two arbitrary languages $L_1$ and $L_2$ be right congruent. Is the natural relation of the language $L_1 \cup L_2$ also right congruent?

So a right congruence is a equivalence relation with the added property that:

$\forall a \in \Sigma : u \equiv v \Longrightarrow ua \equiv va$

Intuitively i would say that the union of this two relations remains to be a right congruence but i dont know how to prove this idea.

2. For every equivalence relation $\equiv$, there are at least two languages which are saturated by $\equiv$, true or false?

An equivalence relation saturates a Language $L$ if: $u \equiv v \Longrightarrow u \in L \Leftrightarrow v \in L$

My guess would be that any equivalence relation saturates the Language $L$ and $\bar{L}$

I would be pleased if some one could provide me with a useful hint on how to solve this questions.

• a. Please ask only one question per question. b. What have you tried? Have you tried working through some examples to see if your conjecture/suspicion seems to hold up, and to see if you can spot any patterns? – D.W. Nov 5 '15 at 18:14

## 1 Answer

I'll walk you through the first question. You can ask the second question separately (see D.W.'s answer).

When faced with a "proof or refute" question like this, we need to try both directions. First, we can try proving the claim. If we seem to get stuck, we can look for a counterexample.

Let's try proving the claim. We are given that $L_1$ and $L_2$ are right congruent. This means the following, for $u,v \in \Sigma^*$ and $a \in \Sigma$:

• If $u,v \in L_1$ or $u,v \notin L_1$ then either $ua,va \in L_1$ or $ua,va \notin L_1$.
• If $u,v \in L_2$ or $u,v \notin L_2$ then either $ua,va \in L_2$ or $ua,va \notin L_2$.

Let's try to prove that $L_1 \cup L_2$ also satisfies a similar condition. We have to consider two cases: $u,v \in L_1 \cup L_2$ and $u,v \notin L_1 \cup L_2$. The second case looks simpler, so let's start with it. If $u,v \notin L_1 \cup L_2$ then $u,v \notin L_1$ and $u,v \notin L_2$. The assumptions then show that:

• Either $ua,va \in L_1$ or $ua,va \notin L_1$.
• Either $ua,va \in L_2$ or $ua,va \notin L_2$.

We have to prove that either $ua,va \in L_1 \cup L_2$ or $ua,va \notin L_1 \cup L_2$. We reason as follows. If $ua,va \in L_1$ then $ua,va \in L_1 \cup L_2$ so we're done. Same if $ua,va \in L_2$. The remaining case is $ua,va \notin L_1$ and $ua,va \notin L_2$. In this case, $ua,va \notin L_1 \cup L_2$, so we're again done.

Now let's get back to the other case: $u,v \in L_1 \cup L_2$. This case looks harder. There are many different subcases. Let's start with a simple one: $u,v \in L_1$. In this case we can say that $ua,va \in L_1$ (and then we're done, since $ua,va \in L_1 \cup L_2$) or $ua,va \notin L_1$. What do we do in the latter case? We have to consider membership of $u,v$ in $L_2$. If $u,v \in L_2$ or $u,v \notin L_2$ then either $ua,va \in L_2$ (and then we're done, since $ua,va \in L_1 \cup L_2$) or $ua,va \notin L_2$, in which case we know that $ua,va \notin L_1 \cup L_2$. But what happens if $u \in L_2$ and $v \notin L_2$? Then we seem to be stuck.

Now we switch gears, trying to refute the claim. We got stuck when we had $u,v$ such that $u,v \in L_1$, $ua,va \notin L_1$, $u \in L_2$, $v \notin L_2$. So we try to look for two right congruent languages for which two such words exist. In order to do that, we need first to think of examples of right congruent languages. One very simple example is the language of even-length words. We can enrich the repertoire by taking the language of all words having an even number of some letter $a$.

Here are two examples of this sort: take $L_1$ to be all words with an even number of $0$s, and take $L_2$ to be all words with an even number of $1$s. We can take $u = \epsilon \in L_1 \cap L_2$ (here $\epsilon$ is the empty word) and $v = 1 \in L_1 \setminus L_2$. Since we want $ua,va \notin L_1$, we take $a = 0$. Then $u0,v0 \notin L_1$ while $u0 \in L_2, v0 \notin L_2$. So $u0 \in L_1 \cup L_2$ but $v0 \notin L_1 \cup L_2$, and we have found our counterexample!

As you can see, finding a counterexample is often more creative then proving a statement, which can be quite mechanical. You just need to try a lot of things until something works.

The next step is to reflect on what we have shown. Is there any other operation on two languages which preserves the property of being right congruent? Is there an operation on one language? Indeed, there are: if $L$ is right congruent then so is $\overline{L}$; and if $L_1,L_2$ are right congruent then their symmetric difference $L_1 \triangle L_2$ is right congruent. See if you can prove these claims.

(In fact, right congruent languages are exactly the languages accepted by a DFA with at most two states. This leads to a complete classification of these languages, which I leave to the reader.)