I am currently struggling with figuring out the following problem:

Given decidable languages L1, L2, L3, L4, ...

Is the infinite union of Languages L1, ...... decidable? I have an intution that it is not, but I cannot find an example against that thesis.

Thank you in advance


1 Answer 1


Your intuition is right.

Hint: for any $x$, the language $\{x\}$ is decidable. Think how we can use this fact to construct an undecidable language.

  • $\begingroup$ Sorry, but this is still leaving me clueless. Can you elaborate on that? $\endgroup$ Commented Nov 18, 2022 at 18:57
  • 2
    $\begingroup$ You agree that $\{x\}$ is decidable for any singleton? Now, take any undecidable set. What's that but a countable union of singletons? $\endgroup$
    – Pål GD
    Commented Nov 18, 2022 at 19:00

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.