Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 4 / 16H (Logic and Set Theory)

A class in set theory is a collectiondefined by a formula $\psi$, with set parameters if these are allowed by the chosen convention. It is a set-class if there is an $m\in V$ whose elements are exactly the members of $M$. Otherwise it is a proper class.

Let $\mathcal{F}$ be the class of all finite sets. It is proper. If $\mathcal{F}$ were a set, then for every set $x$ the singleton $\{x\}$ would belong to $\mathcal{F}$, soThus $\bigcup \mathcal{F}$ would be a universal set. Separation applied to the property $z\notin z$ would then give the usual Russell contradiction.

The class $\mathcal{F}$ is not transitive. For example, $\{\omega \}$ is finite, but its member $\omega$ is infinite. It is nevertheless $\phi$-closed for every formula $\phi$: if $x$ is finite, then every subsetis finite.

The collection of hereditarily finite sets iswhere $V_0=\varnothing$ and $V_{n+1}=\mathcal{P}(V_n)$. Every $V_n$ is finite, and the axiom of infinity together with replacement and union makes $V_{\omega }$ a set. Hence this collection is not a proper class.

It is transitive: if $x\in V_n$, then $x\subset V_{n-1}$, so every $y\in x$ belongs to $V_{n-1}\subset V_{\omega }$. It is also $\phi$-closed. If $x\in V_n$ andthen $s\subset x\subset V_{n-1}$, so $s\in V_n\subset V_{\omega }$.

Consider the structure $(M,\in )$.

For extensionality, let $x,y\in M$ have the same members in $M$. Since $M$ is transitive, every actual member of $x$ or $y$ lies in $M$. Thus $x$ and $y$ have the same members in $V$, and ambient extensionality gives $x=y$.

By hypothesis $\varnothing \in M$, and it has no members in the induced structure, so the empty-set axiom holds. If $x,y\in M$, then $\{x,y\}\in M$ by closure, and its internal members are exactly $x$ and $y$, proving pairing.

Finally, if $x\in M$, then $\bigcup x\in M$. For $z\in M$,Every such $y$ lies in $M$ by transitivity, so the same equivalence holds internally. Hence union is satisfied. This is the basic set-theoretic axioms inherited by a transitive class argument.

The definition of $\phi$-closure formswhereas the axiom schema of specification inside $(M,\in )$ requiresAn arbitrary formula need not be absolute between a transitive class and the ambient universe, so $s_V$ and $s_M$ can differ. Closure under $s_V$ therefore supplies no reason for the required set $s_M$ to belong to $M$.

Takethe formula relativization to a class: replace each $\exists y\psi$ byand each $\forall y\psi$ byleaving atomic formulas unchanged. If $M$ is given by a defining formula, insert that formula wherever $y\in M$ occurs; this is why the map may depend on $M$.

For $z$ and any parameters in $M$, induction on formulas givesTherefore ${\phi }^{\ast }$-closure putsin $M$ for every $x\in M$. This is exactly the relativized closure criterion for separation, so $(M,\in )$ satisfies the $\phi$-instance of separation.