Past exam of the analytic topology and axiomatic set theory course of the University of Oxford / 2008 / B / 6 / i

A bounded quantifier has the form $\exists u\in v$ or $\forall u\in v$, abbreviating $\exists u(u\in v\wedge \cdots )$ or $\forall u(u\in v\to \cdots )$. A ${\Sigma }_0$ logical formula, also called ${\Delta }_0$, is built from atomic membership and equality logical formulas using Boolean connectives and only bounded quantifiers. It has no unbounded quantifier.

For example $z\subseteq y$ abbreviates the bounded logical formula $\forall u\in z(u\in y)$. Quantifiers are bounded by an existing variable or parameter, not by an unrestricted class term such as the power set of a parameter unless that set has separately been supplied as a parameter.

A ${\Sigma }_1$ logical formula has the formup to the standard logical transformations defining the hierarchy. The initial existential quantifiers may be unbounded; all quantifiers inside the matrix are bounded. A finite tuple of witnesses can be encoded by one set if desired, and logical formulas with no initial unbounded quantifier are included as the level-zero special case.

The dual ${\Pi }_1$ class in set theory has an initial universal block with a bounded matrix. Negation interchanges these two classes, but does not in general preserve the existential class in set theory. Part (iii) supplies an explicit reason for the failure in this setting.