Briefly justify your answer for each statement. a. Any subset of a decidable set

Question

Briefly justify your answer for each statement. a. Any subset of a decidable set is recognizable. b. Any subset of an uncountable set is countable. c. Any superset of an undecidable set is uncountable. d. There is a language that is both countable and undecidable. e. There is a decidable but not recognizable language. f. The complement of a recognizable language must be recognizable. g. Every language reduces to itself. h. Every language reduces to its complement. i. For any two languages L_1, L_2, if L_1 reduces to L_2 then L_2 reduces to L_1.

Explanation / Answer

(a) False.

Universal set is a decidable set. Not all subsets of universal sets are recognizable, otherwise there would be no recognizable sets! Hence not all subsets of decidable sets are recognizable.

(b) False.

Let U be the uncountable set. Pick a subset of uncountable set with all but 1 element from the set. Let call this subset U' and the removed element r. Suppose U' was countable, this means there's a 1-to-1 mapping with set of natural numbers, we can always pick another natural number and map it to r. This will give us a 1-to-1 mapping of U with natural numbers, which is a contadiction. And hence not all subsets of uncountable sets are countable.

(c) False

Universal set is the super set of all languages, which is countable. Hence not all supersets of undecidable set are uncountable.

(d) False.

If a language is countable, there's a 1-to-1 mapping with natural numbers and hence we have a turing machine for it. So the language cannot be undecidable.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.