# how do I find a undecidable subset of a set that's decidable? [closed]

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?

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

## 1 Answer

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

• 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? – user3277633 Mar 20 '14 at 2:04
• Here $1^{2x+1}$ is the string of length $2x+1$ consisting only of $1$s. – Yuval Filmus Mar 20 '14 at 2:05
• 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? – user3277633 Mar 20 '14 at 2:11
• Well, $S$ consists of all strings of odd length... – Yuval Filmus Mar 20 '14 at 2:15