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

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!

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.