# Proving a class of languages is closed under union when it closed under concatenation, (inverse) homomorphic images, and intersections.

Let $$C$$ be a class of languages closed under concatenation ($$\cdot$$), intersection, homomorphic images, inverse homomorphic images, and intersection with regular languages. Prove that $$C$$ is also closed under union.

My attempt: Let $$L_1, L_2 \in C$$. Let $$\square_1, \square_2$$ be two unique elements not in $$L_1, L_2$$ respectively. Then $$L_i \cup \{\square_i\}$$ is an inverse homomorphic image of $$L_i$$. But then $$L_i \cup \{\epsilon\}$$ is a homomorphic image of $$L_i\cup \{\square_i\}$$. So $$L_1\cup L_2 \subseteq (L_1\cup \{\epsilon\})\cdot (L_2\cup \{\epsilon\}) \in C$$. However, I am not sure how to go from $$(L_1\cup \{\epsilon\})\cdot (L_2\cup \{\epsilon\})$$ to $$L_1\cup L_2 \in C$$. I have not used intersections at all, so I think I'm on the wrong track.

If $$C$$ is empty, then $$C$$ is closed under union and we are done. If $$C=\{\emptyset\}$$, then $$C$$ is closed under union and we are done.

Assume $$C$$ contains one nonempty language.

Let $$P\in C$$ be nonempty. Let $$\zeta$$ be the homomorphism that maps every letter to $$\epsilon$$, the empty string. $$\zeta$$ maps every string to $$\epsilon$$ as well. So $$\zeta(P)=\{\epsilon\}$$. Hence $$\{\epsilon\}\in C$$.

Suppose $$L_1, L_2\in C$$. I assume that you have shown $$L_1\cup\{\epsilon\}\in C$$ as well as $$L_2\cup\{\epsilon\}\in C$$.

Let $$\alpha, \beta$$ be two letters that never appear in any word in $$L_1$$ nor in any word in $$L_2$$. We have

$$L_1\cup L_2\cup\{\epsilon\}=g_{\alpha\beta}(\left((\cdot\alpha)^*\cup(\cdot\beta)^*\right)\cap f_\alpha(L_1\cup\{\epsilon\})f_\beta(L_2\cup\{\epsilon\}))$$

where

• $$f_\alpha$$ maps every letter $$\sigma$$ to $$\sigma\alpha$$.
• $$f_\beta$$ maps every letter $$\sigma$$ to $$\sigma\beta$$.
• $$f_\alpha(L_1\cup\{\epsilon\})f_\beta(L_2\cup\{\epsilon\})$$ is the concatenation of $$f_\alpha(L_1\cup\{\epsilon\})$$ and $$f_\beta(L_2\cup\{\epsilon\})$$.
• $$(\cdot\alpha)^*$$ is the regular language that consists of all words of even length such that each letter at an even position is $$\alpha$$.
• $$(\cdot\beta)^*$$ is the regular language that consists of all words of even length such that each letter at an even position is $$\beta$$.
• $$g_{\alpha\beta}$$ is the homomorphism that maps every letter to itself except that it maps $$\alpha$$ and $$\beta$$ to the empty string.

Hence $$L_1\cup L_2\cup\{\epsilon\}\in C$$.

If $$\epsilon\in L_1\cup L_2$$, then $$L_1\cup L_2=L_1\cup L_2\cup\{\epsilon\}\in C$$.
Otherwise, $$\epsilon\notin L_1\cup L_2$$, then $$L_1\cup L_2=(L_1\cup L_2\cup\{\epsilon\})\cap(\Sigma^*\setminus\{\epsilon\})\in C$$, where $$\Sigma$$ is the set of all letters that ever appear in $$L_1$$ or $$L_2$$.