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?
2026-03-29 14:57:45.1774796265
On
An arbitatry subset of a Turing-recognizable language, is also a Turing-recognizable language?
606 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
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.
Well, I guess not. Consider the language $L=\Sigma^*$ which is Turing recognizable. But there are undecidable subsets of $\Sigma^*$.