# Proof or disproof Fin = Fin-Complete $Fin = \{ L \in \Sigma^* : |L|$ is finite and greater than 0 $\}$

$$Fin = \{ L \in \Sigma^* : |L|$$ is finite and greater than 0 $$\}$$ Proof or disproof Fin = Fin-Complete Where Fin-Complete means that for every $$L_1,L_2 \in Fin$$ there exist a valid reduction $$L_1 \leq L_2$$

my trial:

Consider two languages $$L_1$$ and $$L_2$$ where $$L_1$$ contains a single string s $$L_1 = \{ s \} \ s \in \Sigma^*$$ and $$s \neq \epsilon$$ a finite language of size 1. Let $$L_2 = \emptyset$$ the empty language, which is also finite by definition as it contains zero strings. By the definition of reduction, $$L_1 \leq L_2$$ there must exist a computable function $$f$$ such that for any string $$w \in L_1$$ if and only if $$f(w) \in L_2$$ however since $$L_2 = \emptyset$$ there are no strings in $$L_2$$ for $$f(x)$$ to map to construct such a function f that satisfies the condition for all $$w\in L_1$$

• By your definition Fin does not contain the empty set: $|L| > 0$. Feb 2 at 10:20
• right i miss that thank u Feb 2 at 10:58

The claim is correct. To see why, note that every language in $$L\in Fin$$ is non-trivial and regular. Indeed, $$L$$ is not empty, by the definition of $$Fin$$, and does not equal $$\Sigma^*$$ as then it would be infinite. Now the claim follows from the fact that every regular language is decidable, and the fact that every non-trivial language is $$R$$-hard. Specifically, for every two languages $$L_1, L_2 \in Fin$$, we have that $$L_1 \in \text{REG} \subseteq \text{R}$$ and $$L_2 \notin \{ \emptyset, \Sigma^*\}$$. Hence, we conclude that $$L_1\leq_m L_2$$.