Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 120 / 2 / f / Solution

Consistency of $P{A}^{-}$ makes $A$ and $B$ disjoint. Suppose a recursive set $C$ separated them, and let $R(x)$ represent its total characteristic function in $P{A}^{-}$. By the diagonal lemma, choose a sentence $\sigma$ satisfyingPut $n=┌\sigma ┐$. If $n\in C$, representability gives $P{A}^{-}⊢R(\bar{n})$ and hence $P{A}^{-}⊢\neg \sigma$, so $n\in B$, contradicting $B\cap C=\varnothing$. If $n\notin C$, representability gives $P{A}^{-}⊢\neg R(\bar{n})$ and hence $P{A}^{-}⊢\sigma$, so $n\in A\subseteq C$, again a contradiction. Therefore $A$ and $B$ are recursively inseparable.