An arbitatry subset of a Turing-recognizable language, is also a Turing-recognizable language?

606 Views Asked by At

Given a language $L_1$ which is a a Turing-recognizable language, and a language $L_2$ which is a arbitrary subset of $L_1$, then, $L_2$ is also a a Turing-recognizable language?

2

There are 2 best solutions below

1
On

Well, I guess not. Consider the language $L=\Sigma^*$ which is Turing recognizable. But there are undecidable subsets of $\Sigma^*$.

0
On

Using what @David C. Ullrich and @Wyestenfux said, let's say that we have a language $L_1 = \Sigma^*$, we know that this languague is a turing-recognizable language. If we pick all possible subsets of $L_1$, then we have a uncountable set $A$, and each subset of $A$ belongs to $\Sigma^*$, since our set $A$ is uncountable set, there is at least one element present at $A$ which isn't turing-recognizable, therefore, there is at least one subset of $\Sigma^*$ which isn't turing-reconizable.