1
$\begingroup$

I was given the following problem and told it has to be solved using diagonalization. However, I am confused as to why diagonalization would be the solution. Would the answer not be since L is infinite it has uncountably many subsets. Since there are only countably many decidable languages, some subset of L must be undecidable.

Problem: We know that for Σ = {0, 1}, there are uncountably many languages over Σ. Is this also true for the languages over the unary alphabet {1}? Give a proof from scratch (not using known theorems).

$\endgroup$

1 Answer 1

1
$\begingroup$

Your proof is roughly correct, indeed showing that |Power(L)| is uncountably infinite is usually done via diagonalization. Here, L is the set of strings over the unary alphabet, and a language is any subset of L.

Suppose for contradiction that |P(L)| was denumerable. Then we can create an infinite array indexed on the rows by the members of P(L) and indexed on the columns by the members of L. Now we can add a 0 or a 1 for each cell depending on whether or not a string is inside a subset... Can you complete the proof?

$\endgroup$
2
  • $\begingroup$ would you by any chance be able to show a diagonalization example $\endgroup$ Commented Mar 25, 2022 at 3:36
  • $\begingroup$ do you know what diagonalization is? $\endgroup$
    – emesupap
    Commented Mar 25, 2022 at 3:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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