# Why is PH in PSPACE?

$PH \subseteq PSPACE$.

In order to prove it, one has to show that for a language $A \in \Sigma_k$ (for some $k \in \mathbb{N}$) there exists a turing machine $M_A$ that decides it in polynomial space.

I am having a hard time understanding why this is true. I'll try to explain:

Let's take for example $L \in\Sigma_2$: by definition, $x \in L \Longleftrightarrow \exists y_1\forall y_2 : V(y_1,y_2)=1$. But finding such $y_1$ and checking it against all possible $y_2$s has to take more than polynomial space! The machine has to remember each $y_2$ that it tried in order to make sure that it indeed tried out all of the options, and the number of possible $y_2$s is exponential, which makes it exponential space.

No, it is not necessary to remember all $y$'s tried before. In order to remember that I've tried the numbers $1,2,\ldots,200$, I do not need to remember $3,4,5,6,\ldots,199$. If you try them in order, just remembering the last one is enough.