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

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.

Use the strict-order convention appropriate to the membership relation. A bounded logical formula isThe first clause is irreflexivity, the second transitivity, and the third comparability of distinct elements. Irreflexivity and transitivity exclude $u\in v\in u$, so distinct elements cannot be ordered in both directions. These are exactly the axioms of a strict total order on the set $x$, with $\in$ as its order relation.

Every displayed quantifier is bounded by $x$, so $TO(x)$ is ${\Sigma }_0$. The logical formula does not assert that $x$ is transitive as a set, and no such additional assertion is needed to say that the restriction of membership to $x$ is a total order.

There are two ways for a set to fail to be the power set of $y$: it may contain an object which is not a subset of $y$, or omit a subset of $y$. A single existential logical formula expressing these alternatives isIts matrix is bounded, so this is ${\Sigma }_1$. Its negation is precisely the first-order power-set specification

We prove the absoluteness fact needed to exclude a logically equivalent ${\Sigma }_1$ logical formula. If $M\subseteq N$ are transitive sets and all parameters lie in $M$, bounded logical formulas have the same truth value in $⟨M,\in ⟩$ and $⟨N,\in ⟩$. Atomic equality and membership agree because both structures use actual membership. Boolean operations preserve agreement. In a bounded quantifier over $v\in M$, transitivity ensures that every element of $v$ already lies in $M$, so the two structures quantify over exactly the same elements of $v$. Induction on logical formulas proves the claim. It follows that ${\Sigma }_1$ logical formulas are upward absolute: witnesses in $M$ remain available in $N$, and their bounded matrix retains its truth value.

Now use a finite counterexample, so no existence of a transitive model of ZF is assumed. Let $M=4=\{0,1,2,3\}$, the Finite von Neumann ordinal, and let $N=V_4$. These are transitive sets with $M\subseteq N$. Set $y=2$ and $x=3$, both elements of $M$. Inside $M$, the subsets of $2$ which are available as elements of the domain are exactly $0,1,2$; the remaining domain element $3$ is not a subset of $2$. Thus $M$ satisfies the displayed power-set specification with $x=3$.

Inside $N$, however, the set $\{1\}$ is also present and is a subset of $2$, while $\{1\}\notin 3$. Thus the same specification is false in $N$. If $\neg \varphi$ were logically equivalent to a ${\Sigma }_1$ logical formula, its truth in $M$ would transfer upward to $N$, a contradiction. ThereforeThis proves the requested unrestricted logical non-equivalence. The finite structures are not being claimed to satisfy all of ZF; logical equivalence must hold in them as well as in any models of a stronger theory.