Defining the polynomial hierarchy using $\Pi_i^p$ instead of $\Sigma_i^p$

Question

From Computational Complexity - A Modern Approach, it is claimed in a remark that the following holds true.

Remark 5.5

Note that $\mathbf\Sigma_1^p = \mathbf{NP}$ and $\mathbf\Pi_1^p = \mathbf{coNP}$. More generally, for every $i \geq 1$, $\mathbf\Pi_i^p = \mathbf{co\Sigma}_i^p = \{ \overline{L} : L \in \mathbf\Sigma_i^p\}$. Note also that $\mathbf\Sigma_i^p \subseteq \mathbf\Pi_{i+1}^p$, and so we can also define the polynomial hierarchy as $\cup_{i>0} \mathbf\Pi_i^p$.

However, I am having trouble understanding this. Similar claims are made in lecture notes found on the web, but none of them give a proof since they are all left as exercise. Would it be possible to prove this using NTM instead of verifiers?

Answer 1

It is a direct consequence of the definition of $\textsf{PH}$.

Remember:

$\qquad \Sigma_i^P = \textsf{NP}^{\Sigma_{i-1}^P}$

$\qquad \Pi_i^P = \textsf{coNP}^{\Sigma_{i-1}^P} $

What we want to prove is:

$\qquad \bigcup_{i>0}\Sigma_i^P = \bigcup_{i>0}\Pi_i^P $

We have:

$\qquad \Sigma^P_i \subseteq \textsf{coNP}^{\Sigma^P_i} = \Pi_{i+1}^P$

$\qquad \Pi^P_i \subseteq \textsf{NP}^{\Pi^P_i} = \textsf{NP}^{\Sigma_i^P} = \Sigma^P_{i+1}$

Taking the union yields:

$\qquad \bigcup_{i>0} \Sigma^P_{i} \subseteq \bigcup_{i>0} \Pi^P_{i} \subseteq \bigcup_{i>0} \Sigma^P_{i}$

which is exactly our goal.