I took inspiration from the proof given in "Complete sets and the Polynomial-time hierarchy" of Wrathall. However, I tried to focus mainly on the intuitions, since the original proof is pretty long. Let us focus on the induction step:
Membership:
Let $\phi=\exists X_1 \forall X_2 \dots Q_i X_i(F(X_1, X_2, \dots, X_i))$. We want to show that deciding if $\phi$ is satisfiable is a problem in $\Sigma^p_i$, where each $X_j$ contains a polynomial number of boolean variables in $n$, where $n=|\phi|$.
One can use the hypothesis induction and say that the safisfiability problem for $\phi'=\forall X_2 \dots Q_i X_i(F(X_2, \dots, X_i))$ belongs to $\Pi_{i-1}^p$. At this point is should be easy to see that one can build a ND Turing Machine with a $\Pi_{i-1}SAT$ oracle such that it guesses in polynomial time an assignment for the variables in $X_1$ ($|X_1| \leq n$), and check if it is satisfiable using an $\Pi_{i-1}SAT$ oracle call.
Hardness:
Lemma 1 (polynomial erasing). Given a language $L$, $L\in \Sigma^p_i$ $\iff$ $h(L')=L$, where $h$ is a polynomial erasing homomorphism (with respect to conjunction), i.e. $|x|\leq p(|h(x)|)$ for some polynomial $p$.
The ($\impliedby$) proof is very similar to the argument used above for the membership.
The main idea is for the ($\implies$) case is to see that $L\in \Sigma^p_i \iff$ $\exists L_1 \in P, L_2\in \Sigma^p_{i-1}, L_3\in \Pi^p_{i-1}$ such that $L=h(L_1 \cap L_2 \cap L_3)$.
Each word in $L_j$ for $j=1,2,3$ has the following format:
$(x, y, v, z)$ where the intuition is that
- $x$ is the input (the one you are testing the membership in $L$),
- $y$ is a sequence of TM operations that leads the machine to call some oracles,
- $v$ is a sequence of words that belong to $L_2$
- $z$ is a sequence of words that do not belong to $L_3$
To understand what it is going on, you can read the $y$ has a sequence of instructions that lead the Turing Machine to call (multiple times) oracles in $L_2$ and $L_3$.
Now, you can apply the $h$ function to $(L_1 \cap L_2 \cap L_3)$, obtaining that
$h(L_1 \cap L_2 \cap L_3)=h(L_1) \cap h(L_2) \cap h(L_3)$
By definition, $L1$ (polynomial) and $L_2$ ($\Pi^p_{i-1}$), therefore they are both in the set of languages defined as {$h'(L)$} for some $L\in \Pi^p_{i-1}$ and $h'$ a polynomial erasing homomorphism.
By induction hypothesis, since $L_3\in \Sigma^p_{i-1}$, then there exists an homomorhpism $h'$ such that the target language is in $\Pi_{i-2}^p$, therefore in $\Pi_{i-1}^p$ as well.
Lemma 1 allows us to obtain the following Lemma:
Lemma 2
If $L \in \Sigma^p_i$ and $x\in L $ then, $ \exists y$ s.t. $|y|=p(|x|)$ for some polynomial $p$, and $xy\in L'$ with $L'\in \Pi^p_{i-1}$.
This result can be obtained by induction by applying Lemma 1. Note that in Lemma 1 there is an inequality, while here there is an equality. The trick is to extend the alphabet with a new character which can be used as padding.
At this point, we have all the tools to conclude that $\Sigma_iSAT$ is complete for $\Sigma^p_i$. One can use the hypothesis induction:
$\Phi=${$\phi=\forall X_2 \dots Q_i X_i(F(X_2, \dots, X_i)) | \phi$
is true} is complete for $\Pi^p_{i-1}$, and apply Lemma 2.
Intuitively, you can encode the word $y$ of Lemma 2 using a polynomial number of propositional variables. For example, since we know that $|y|=p(|x|)$, and a finite alphabet $\Gamma$, we can interpret $x_{k,l}$ as a propositional variable which is true if and only if the k-th position of the word coincides with the l-th symbol in $\Gamma$. The set {$x_{k,l}$} will coincide with the set $X_1$ of the statement (see the paper of Wrathall for further details on the encoding).
In that way, you can obtain the desired result. Note that the discussion is only about $\Sigma^p_i$, we can refer to the induction hypothesis on $\Pi^p_i$ as well because they are complementary.
