# How to show a set is $\Pi_2$ complete

How can I prove that a set is complete for $\Pi_2$ complete? Can you give me an example proof? Say for $All_{TM}$ = Turing machines whose accepted language is all strings?

## 1 Answer

To show that the language is $\Pi^0_2$ complete you have to show two things:

1. The language is $\Pi^0_2$

2. Every $\Pi^0_2$ language is many-one reducible to your language

To show that your language is $\Pi^0_2$, informally, you need to know two things: (1) quantifiers over strings count the same as quantifiers over numbers, and (2) the predicate $P(M,\sigma)$ = "machine $M$ accepts string $\sigma$" is $\Sigma^0_1$. Your language is a universal quantifier in front of that $\Sigma^0_1$ relation, so it is $\Pi^0_2$.

To show that an arbitrary $\Pi^0_2$ language is many-one reducible to yours, it's easiest to show that some other language that you know is $\Pi^0_2$ complete is many-one reducible to your language. The details of that will depend on what languages you already know to be $\Pi^0_2$ complete. If you don't know any, then it helps to know that every $\Pi^0_2$ language is definable by a formula of the form $(\forall \sigma)(\exists \tau) R(\sigma,\tau)$ where $R$ is computable.