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

Fix a set $x$ and define by recursion on $\omega$The recursion theorem defines a function-class $F$ uniquely by $F(n)=T_n$: for each $n\in \omega$ there is exactly one finite sequence satisfying the displayed recursion through stage $n$. Thus $F$ is genuinely functional, and the Axiom schema of replacement applied to the set $\omega$ gives the set $\{T_n:n\in \omega \}$.

Now defineIt contains every member of $x$. If $y\in T$, then $y\in T_n$ for some $n$; hence every $z\in y$ belongs toThus $T$ is transitive. If $U$ is any transitive set containing every member of $x$, induction gives $T_n\subseteq U$ for every $n$, so $T\subseteq U$. Thereforeis the transitive closure of $x$.

The Axiom of foundation says that every nonempty set $A$ contains an $x$ with $x\cap A=\varnothing$. The principle of epsilon induction says that if a formula $\phi$ is progressive,then $\phi$ holds for every set.

Assume foundation and let $\phi$ be progressive. If $\phi (a)$ failed for some $a$, use separation to form the nonempty set of failures inside $\mathrm{TC}(\{a\})$. Foundation supplies an $\in$-minimal failure $x$. Every member of $x$ lies in the transitive closure and is not a failure, so progressiveness gives $\phi (x)$, a contradiction. Hence epsilon induction holds.

Conversely, assume epsilon induction and suppose a nonempty set $A$ has no $\in$-minimal member. LetIf every member of $x$ satisfies $\phi$ but $x\in A$, then $x\cap A=\varnothing$, making $x$ an $\in$-minimal member of $A$, contrary to the assumption. Thus $\phi$ is progressive. Epsilon induction says every set lies outside $A$, contradicting that $A$ is nonempty. Foundation follows.

True. If $\mathrm{TC}(\{x\})$ is countable, then each of its members is a subset of this transitive set and is therefore countable.

Conversely, if $x$ is reasonable, then $x$ itself and every set occurring at every finite membership depth below it are countable. Starting with the countable set $\{x\}$, each next level is a countable union of countable sets, hence countable. Their countable union is $\mathrm{TC}(\{x\})$, so the transitive closure is countable.

True. By part (i), the reasonable sets are exactly the hereditarily countable sets $H_{{\omega }_1}$. The rank of a countable transitive closure is the supremum of countably many countable ordinals, plus at most a finite amount, and is therefore below ${\omega }_1$. Hence every reasonable set belongs to

False. The reasonable sets form the transitive set $H_{{\omega }_1}$, but this structure fails the Axiom of power set. The set $\omega$ is reasonable, and every subset of $\omega$ is itself countable and therefore reasonable. Its full power set $\mathcal{P}(\omega )$ is uncountable, so it is not reasonable. No member of $H_{{\omega }_1}$ can therefore contain internally every subset of $\omega$ that belongs to $H_{{\omega }_1}$. Thus the reasonable sets do not form a model of ZFC.