Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 19 / 1

In the Lévy hierarchy, a bounded formula in set theory has only quantifiers of the forms $\forall x\in y$ and $\exists x\in y$. A Sigma-one formula in set theory is an existential unbounded quantifier block followed by a bounded formula in set theory, and a Pi-one formula in set theory has a universal unbounded block. A formula is a Delta-one formula modulo ZFC if ZFC proves it equivalent, with the same free variables, both to a ${\Sigma }_1$ formula and to a ${\Pi }_1$ formula. Equivalence modulo the specified theory is part of the definition; it is not necessary that the original string have both syntactic forms. Such formulas satisfy the usual Delta-one absoluteness between transitive models satisfying the relevant axioms. The modulo-ZF analogue is a Delta-one formula in set theory.

A Sierpiński set is an uncountable subset $S$ of $\mathbb{R}$ such that $S\cap N$ is countable for every set $N$ of Lebesgue measure zero. Equivalently it is enough to test Borel null sets, because every null set is contained in a Borel null set. Uncountability and countable intersection with every null set are both required. This is the measure analogue of the category-based Luzin set condition; it does not say that $S$ itself is measurable.

The cumulative-hierarchy reflection principle says that for every finite collection $\Phi$ of formulas and every ordinal $\gamma$, there is an ordinal $\alpha >\gamma$ such that for all $\phi \in \Phi$ and all parameters $a_1,\dots ,a_n\in V_{\alpha }$,Equivalently, all quantifiers on the right are relativized to $V_{\alpha }$. It is a theorem schema of ZF for finite lists of formulas, with reflecting stages arbitrarily high. It does not assert one set-sized stage elementary for every formula at once. By beginning above the ranks of any specified finite parameter list, the parameters can also be required to belong to the reflecting stage.

Let $f$ be given and choose $Y\subseteq \mathbb{R}$ of cardinality ${\aleph }_1$. Each $f(y)$ is countable, so the axiom of choice and infinite cardinal arithmetic giveSince the continuum is larger, choose $x$ outside this union. Then $x\notin f(y)$ for every $y\in Y$. The countable set $f(x)$ cannot contain $Y$, so choose $y\in Y\setminus f(x)$. ThusThe two points are distinct because $x\notin Y$. This proves the countable-valued free-pair criterion and the required direction of the Freiling axiom of symmetry without any measurability assumption on $f$.

Assume the Continuum hypothesis and enumerate $\mathbb{R}=\{r_{\alpha }:\alpha <{\omega }_1\}$. DefineEvery value is countable. For any two indices, say $\alpha \le \beta$, one has $r_{\alpha }\in f(r_{\beta })$, so the two required nonmembership conditions cannot both hold. Including the endpoint in each initial segment also rules out taking the two points equal. Therefore the free-pair assertion implies the negation of Continuum hypothesis. Cantor theorem and choice already give $2^{{\aleph }_0}\ge {\aleph }_1$, so

The Gödel constructible universe theorem gives $\mathrm{Con}(\mathrm{ZFC})\Rightarrow \mathrm{Con}(\mathrm{ZFC}+\mathrm{CH})$. The forcing independence theorem for the Continuum hypothesis gives $\mathrm{Con}(\mathrm{ZFC})\Rightarrow \mathrm{Con}(\mathrm{ZFC}+\neg \mathrm{CH})$. For example, the latter can be obtained by first passing to the constructible universe and then adding sufficiently many Cohen reals. By the equivalence in part (b), these are respectively models of the negation and affirmation of the free-pair assertion. Thus if ZFC is consistent, the assertion is independent of ZFC. The consistency qualification is essential: an inconsistent theory proves every sentence. These are syntactic relative-consistency implications, not a claim that bare consistency supplies a countable transitive model.

The axiom of infinity excludes $V_{\omega }$ and all smaller stages, so the cardinal $\lambda$ is uncountable. Full semantics for second-order logic is decisive: every externally specified functional relation whose ordered pairs lie in $V_{\lambda }$ is an allowed class parameter, even if the relation itself is not an element of $V_{\lambda }$.

If $\mathrm{cf}(\lambda )=\mu <\lambda$, choose an external cofinal function $h:\mu \to \lambda$. Its graph is an allowed class parameter: each input, output and ordered pair has rank of a set below the infinite cardinal $\lambda$, which is a limit ordinal. The domain $\mu$ belongs to $V_{\lambda }$. The second-order form of Axiom schema of replacement would give its range as an element of $V_{\lambda }$. But a cofinal subset of $\lambda$ has rank of a set $\lambda$ and cannot belong to $V_{\lambda }$. Therefore $\mathrm{cf}(\lambda )=\lambda$.

If $2^{\theta }\ge \lambda$ for a cardinal $\theta <\lambda$, choice supplies an external surjection $q:\mathcal{P}(\theta )\to \lambda$. The domain belongs to $V_{\lambda }$ and the ordered pairs of its graph have ranks below $\lambda$. Applying Axiom schema of replacement to this external functional class would put its range, the ordinal $\lambda$, in $V_{\lambda }$, again impossible. Hence $2^{\theta }<\lambda$ for every $\theta <\lambda$.

ConsequentlyThese are exactly the defining conditions for a strongly inaccessible cardinal. This full second-order replacement rank obstruction would not follow from Henkin semantics, where the available class relations may exclude the external functions just used.