Given that Let S = {a | |a| is odd}. I know that since S is decidable, but does there exist a subset within S that is undecidable?


closed as unclear what you're asking by D.W., FrankW, Juho, David Richerby, vonbrand Mar 21 '14 at 0:04

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ This is a dump of a homework problem. It has also been previously asked on this site. $\endgroup$ – Yuval Filmus Mar 20 '14 at 1:57
  • $\begingroup$ Any set (even undecidable ones) are subsets of the set of all strings... $\endgroup$ – vonbrand Mar 21 '14 at 0:04

Hint: For every language $L$, the language $M = \{ 1^{2x+1} : x \in L \}$ is a subset of $S$.

  • $\begingroup$ thanks for the hint. If L contains all natural numbers, wouldn't M = {1} since 1 to any power will remain 1, and even though M is a subset of S, M only contains 1 and is decidable? $\endgroup$ – user3277633 Mar 20 '14 at 2:04
  • $\begingroup$ Here $1^{2x+1}$ is the string of length $2x+1$ consisting only of $1$s. $\endgroup$ – Yuval Filmus Mar 20 '14 at 2:05
  • $\begingroup$ I am confused as to why a language with only odd number of 1s would be a subset of S. Am I misinterpreting the question by thinking that x must be a number? $\endgroup$ – user3277633 Mar 20 '14 at 2:11
  • $\begingroup$ Well, $S$ consists of all strings of odd length... $\endgroup$ – Yuval Filmus Mar 20 '14 at 2:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.