Definability of set Let $A$ and $B$ be two disjoint sets definable (shouldn't be relevant, but I'm working in the standard model of natural numbers and the language of Peano) respectively with a formula $\varphi_A$ and $\varphi_B$, both with $n$ alternated quantifiers, the outermost being existential, and let $C=(A \cup B)^C$. From the hypotheses it easily follows that $C^C$ is definable with a formula with $n$ alternated quantifiers, the outermost being existential. Since $B=A^C\cap C^C$ I would like to show that either $A^C$ can be defined with a formula with $n$ alternated quantifiers, the outermost being existential, or both $B$ and $C^C$ can be defined using a formula with $n$ alternated quantifiers, the outermost being universal (or both the things). Using the Arithmetical Hierarchy jargon, the same question can be phrased as: if $A,B \in \Sigma^0_n$ and $C=(A\cup B)^C$ can we conclude that either $A\in\Pi^0_n$ or $B,C^C\in\Pi^0_n$ (or both)?

No, here's a counterexample.

Let $X$ be a set of natural numbers that is recursively enumerable but not recursive. (So $X$ is $\Sigma^0_1$ but not $\Pi^0_1.)$

Define $A = \lbrace 2n \mid n\in X \rbrace,$ and $B = \lbrace 2n+1 \mid n\in X \rbrace.$ Then $A$ and $B$ are also both $\Sigma^0_1$ but not $\Pi^0_1,$ which is enough to see that this is a counterexample.

By the way, $C^C = A \cup B$ is also $\Sigma^0_1$ (since both $A$ and $B$ are $\Sigma^0_1)$ but not $\Pi^0_1$ (since if it were $\Pi^0_1,$ it would then be recursive, which would imply that $X$ is recursive).