A < HPL < Complement(A) What can you say about A and Complement(A)?

Question

Suppose we have the language

$ \overline L = \{x∈\{0,1\}*:x∉L\}$

And we know that

$A ≤ HPL ≤ \overline A$

where HPL is the Halting problem.

We need to state whether A is finite, countably infinite and whether $A$ and $ \overline A$ is recursive or not or re or not.

We know that A reduces to HPL and HPL is re and therefore A is re. Since HPL reduces to $\overline A$ and HPL is not recursive then $\overline A$ is not recursive. Furthermore, if we know that a language is not recursive but its complement is re then the language is not re. We know so far that $\overline A$ is not recurisve but $A$ is re then it means that $\overline A$ is not re. Furthermore if you know that a language L is not re then either $\overline L$ is not re or $\overline L$ is re but not recursive. We know that $\overline A$ is not re but A is re and therefore, we can say that A is not recursive.

Can anybody tell me if my deduction is any good? Also, how can I know if A is finite/ count infinite? Any tip would be greatly appreciated!

Answer 1

Your analysis appears to be correct. But some clarity may help you. Let's analyse each case and check whether it is consistent with given information. As $\text{HPL} \leq \overline{A}$, $\overline{A}$ cannot be finite or recursive.

\begin{array}{|l|l|} \hline \textbf{If A is } & \textbf{Then }\overline{A} \textbf{ is}\\ \hline \mbox{Finite} & \mbox{Contradiction - }\overline{A} \text{ has to be FA; Violates HPL} \leq \overline{A} \\ \hline \mbox{Recursive} & \mbox{Contradiction - }\overline{A} \text{ has to be recursive; Violates HPL} \leq \overline{A}\\ \hline \mbox{Recursively Enumerable} & \text{Non-Recursively Enumerable}\\ \mbox{but not Recursive} & \\ \hline \mbox{Non-Recursively Enumerable} & \mbox{Contradiction - Violates } A \leq \text{HPL}\\ \hline \end{array}

You can now infer countability based on this information.