I am given the sets $A$ such that $|A|<\infty, A\neq\emptyset$ and $B$ such that $|B|=\infty$. I am then supposed to find where the following sets go in the arithmetic hierarchy:
$S=\{e\colon \text{dom}(\Phi_e)=A\}$
$T=\{e\colon \text{dom}(\Phi_e)=B\}$
but am a bit confused on how to decide this? It is clear they are not in $\Sigma_1,\Pi_1$ but I don't know where to go from there and why their classifications may be different, since as far as I can see any logical statement for one set would also work for the other? Thanks!
Note: $\Phi_e$ denotes the $e$-th partial computable function.
Let $\psi$ be a primitive recursive function such that $\psi(e,n,t)=1$ if $\Phi_e(n)$ halts in $t$ steps or less otherwise $\psi(e,n,t)=0$.
Then $S=\{n\;|\;\exists t\forall x \forall u(u\ge t \wedge x\in A\Leftrightarrow\psi(n,x,u)=1)\}$, so $S\in\Sigma_2$.
But also $S=\{n\;|\;\forall x \forall u\exists t(u\ge t \wedge x\in A\Leftrightarrow\psi(n,x,u)=1)\}$, so $S\in\Pi_2$.
So $S\in\Delta_2$. Note that $S\notin\Sigma_1\cup\Pi_1$
Note that $x\in A$ is a recursive primitive relation as $A$ is finite.
If $B$ is not recursively enumerable, then $T$ is empty, so $T\in\Delta_0$.
If $B$ is recursively enumerable, let $b$ such that $B=dom(\Phi_b)$.
Then $T=\{n\;|\;\forall x\forall u\exists t \quad u>t\Rightarrow (\psi(b,x,u)=1\Leftrightarrow\psi(n,x,u)=1)\}$. So $T\in\Pi_2$.
The main difference is that as $A$ is finite, there is time $t$ such that if a function $f$ of domain $A$ is computed, either $f$ halts before time $t$ or never halts (you can see $t$ as the maximum time needed to converge). But $B$ is infinite, so there may be no maximum time over all entries, so $T\notin \Sigma_2$