My attempt to solve this:

If $\mathcal{A}$ is an arbitrary infinite recursive set then the members of $\mathcal{A}$ can be ordered in ascending order. We can do bijection between $\mathcal{N}$ and $\mathcal{A}$.

Halting problem is $\mathcal{K}\subseteq\mathcal{N}$ and therefore it's also $\mathcal{K}\subseteq\mathcal{A}$. And the same can be said about $\bar{\mathcal{K}}$.

Is my solution correct? Are there any "better" solutions to this problem?

  • $\begingroup$ why does it follow that $K \subset A$?? Indeed, you can find a bijection, but it may not be a subset. $\endgroup$
    – Ran G.
    Commented Jan 18, 2015 at 16:15
  • $\begingroup$ If I order the members of $\mathcal{A}$ and enumerate them such that lowest possible member of $\mathcal{A}$ is 0, next one is 1, next one is 2, etc. I have - because the $\mathcal{A}$ is infinite - a set of natural numbers. Let the bijecting function is $f$. So if $\mathcal{K}\subseteq\mathcal{N}$ then I use the $f$ to get the number in $\mathcal{A}$. $\endgroup$
    – Gordon
    Commented Jan 18, 2015 at 16:37
  • 1
    $\begingroup$ You're claiming that $\mathcal{K}\subseteq \mathcal{A}$ and also $\overline{\mathcal{K}}\subseteq \mathcal{A}$. That cannot be true unless $\mathcal{A}=\mathcal{N}$. $\endgroup$ Commented Jan 18, 2015 at 18:08
  • $\begingroup$ @DavidRicherby I am claiming that $\mathcal{A}$ has as many elements as $\mathcal{N}$. $\endgroup$
    – Gordon
    Commented Jan 18, 2015 at 20:00
  • $\begingroup$ @Gordon That's not what you wrote. The sentence beginning "Halting problem is" means what I said it means. $\endgroup$ Commented Jan 18, 2015 at 20:50


Your Answer

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

Browse other questions tagged or ask your own question.