Past exam of the logic and set theory course of the University of Oxford / 2007 / B

The axiom of infinity asserts that an inductive set exists: some set $I$ contains $0=\varnothing$ and contains $x^{+}=x\cup \{x\}$ whenever it contains $x$. Inside one such $I$, axiom of separation definesThis intersection is itself inductive and is contained in every inductive set, by intersecting that set with $I$. It is therefore the set of natural numbers. If a property holds at $0$ and passes from $n$ to $n^{+}$, axiom of separation forms the subset of $\omega$ on which it holds. That subset is inductive, so must equal $\omega$. This proves mathematical induction, including properties with set parameters.

Recursion on $\omega$ defines the arithmetic operations byExistence and uniqueness follow from the recursion theorem on the natural numbers.

For associativity of addition fix $m,n$ and induct on $k$. At $k=0$ both sides equal $m+n$. If the equality holds at $k$, thenThusEvery step after the induction hypothesis is a defining successor equation, so commutativity has not been used prematurely.

Induct on $n$. The initial equation is $0+0=0$ by the zero clause. If $0+n=n$, the successor clause givesConsequentlyThis proves the left-identity property independently of the right-identity equation built into the recursive definition.

Fix $m$ and induct on $n$. At $n=0$,If $m^{+}+n=m+n^{+}$, thenThe last expression is the right-hand side required at the successor $n^{+}$. ThereforeIn particular both sides also equal $(m+n{)}^{+}$ by the recursion equation for the second argument.

Fix $m,n$ and induct on $k$. For $k=0$,For the induction step, use the multiplication recursion, the induction hypothesis, and addition associativity from (i):ThusThis establishes the indicated distributive law without assuming multiplication is commutative.

Fix $m$ and induct on $n$. The initial equality $m+0=0+m$ follows from the defining zero clause and (ii). Assuming $m+n=n+m$, the successor clause and (iii) giveThis provesThe extension to arbitrary ordinals is false. By the limit clause for ordinal addition,whereas $\omega +1$ is the successor ordinal of $\omega$ and is strictly greater than it. ThereforeFinite addition is commutative; ordinal addition records the order of concatenated well-orders and need not be commutative.

Use the Kuratowski ordered pairThe axiom of pairing first constructs $\{x\}$ and $\{x,y\}$, then constructs the displayed pair of those sets, proving that it is a set.

For any $a,b$, the intersection of the members of this pair is $\{a\}$, and their union is $\{a,b\}$. Thus equality of two ordered pairs first gives $\{a\}=\{c\}$, hence $a=c$, and then $\{a,b\}=\{a,d\}$. If $b=a$, this latter set is a singleton and forces $d=a$. If $b\ne a$, its unique member distinct from $a$ is $b$, forcing $d=b$. Hence equality of ordered pairs gives equality of both coordinates.

For a set $R$ of ordered pairs, both coordinates of every pair belong towhich is a set by two applications of the Axiom of union. Axiom of separation inside $U$ givesThese are sets, including when $R$ is empty.

The Axiom of foundation asserts that every nonempty set $A$ has an element $a$ with $a\cap A=\varnothing$. If a descending membership sequence $f:\omega \to V$ existed, replacement would give the nonempty range set $S=\{f(n):n\in \omega \}$. Foundation would give some $f(n)$ disjoint from $S$. But $f(n^{+})\in f(n)$ and $f(n^{+})\in S$, contradicting that disjointness. Thus foundation rules out every such sequence.

Conversely suppose there is no descending membership sequence, but foundation fails. There is then a nonempty set $A$ such that $a\cap A\ne \varnothing$ for every $a\in A$. The axiom of choice selects a function $h$ on $A$ with $h(a)\in a\cap A$. Choose $a_0\in A$ and use recursion to defineEvery value remains in $A$, and $f(n^{+})\in f(n)$ for every $n$. This is the forbidden sequence. Therefore, with the stated choice assumption, foundation is equivalent to the absence of descending membership sequences. The selection step explains exactly where choice is used; dependent choice would suffice.

The Cantor-Schröder-Bernstein theorem says that injections $X\to Y$ and $Y\to X$ imply a bijection $X\to Y$. Thus mutual cardinal inequalities imply equal cardinalities, without a choice assumption.

Write $\mathfrak{c}=2^{{\aleph }_0}=|\mathbb{R}|$. Standard cardinal arithmetic gives $\mathfrak{c}\cdot \mathfrak{c}=\mathfrak{c}$ and ${\mathfrak{c}}^{{\aleph }_0}=\mathfrak{c}$. The correspondence $x+iy\leftrightarrow (x,y)$ is a bijection $\mathbb{C}\leftrightarrow {\mathbb{R}}^2$. HenceEquivalently, the real axis supplies the lower inequality and a coding of two real coordinates supplies the upper one; Cantor-Schröder-Bernstein then gives the equality.

The set of all functions from a set of size $\mathfrak{c}$ to another set of size $\mathfrak{c}$ has size ${\mathfrak{c}}^{\mathfrak{c}}$. Cardinal exponentiation and the law $({\kappa }^{\lambda }{)}^{\mu }={\kappa }^{\lambda \mu }$ giveThereforeThe lower bound can also be seen by taking characteristic functions of all subsets of $\mathbb{C}$. Cantor's theorem makes this strictly larger than $\mathfrak{c}$, unlike the continuous-function space in the next part.

The set $D=\mathbb{Q}+i\mathbb{Q}$ is countable and dense in $\mathbb{C}$. Restriction to $D$ is injective on continuous functions $\mathbb{C}\to \mathbb{R}$: if two such functions agree there, their equality set is closed and contains a dense set, so is all of $\mathbb{C}$. Equivalently a sequence of points of $D$ converging to any chosen point and continuity determine its value uniquely.

Thus the family has cardinality at mostFor the lower bound, every real number determines a different constant continuous function. Cantor-Schröder-Bernstein yieldsThe reduction to countably many values is the feature that separates this answer from unrestricted functions.

Every strictly increasing sequence is in ${\mathbb{N}}^{\mathbb{N}}$, whose cardinality is ${\aleph }_0^{{\aleph }_0}=\mathfrak{c}$. This gives the upper bound.

For each binary sequence $ϵ=({ϵ}_n{)}_{n\in \mathbb{N}}$, defineThen $a_{n+1}-a_n=2+{ϵ}_{n+1}-{ϵ}_n\ge 1$, so the sequence is strictly increasing. Distinct binary sequences give distinct increasing sequences. This injects a set of size $2^{{\aleph }_0}$ into the desired family, giving the matching lower bound. HenceOne may also identify an increasing sequence with its infinite range subset of $\mathbb{N}$; the explicit binary coding establishes the lower bound without discarding finite subsets by cardinal subtraction.

The family is a subset of all complex sequences, so its cardinality is at mostFor each $z\in \mathbb{C}$, the sequence $(z,0,0,\dots )$ belongs to the family because its displayed series has just one nonzero first-order term. These sequences are distinct as $z$ varies, giving a lower bound $\mathfrak{c}$. ThusThe source condition is convergence of ${\sum }_j{a}_j^2$, without absolute-value bars. The argument uses exactly that printed condition and makes no assertion that it is equivalent to square summability of complex sequences. The same upper and lower bounds would also work for the stronger absolute-square condition, but no alteration of the source is needed.

Inclusion gives $|\mathbb{R}\setminus \mathbb{Q}|\le \mathfrak{c}$. If $\kappa =|\mathbb{R}\setminus \mathbb{Q}|$, the disjoint decomposition of $\mathbb{R}$ givesThe irrational numbers are infinite, for instance $n+\sqrt{2}$ are pairwise distinct irrationals. Standard infinite cardinal addition gives ${\aleph }_0+\kappa =\max ({\aleph }_0,\kappa )$. Since Cantor's theorem gives $\mathfrak{c}>{\aleph }_0$, the equality forces $\kappa =\mathfrak{c}$. ThereforeThis is the permitted cardinal-arithmetic formal proof; it does not subtract infinite cardinals as though they were finite numbers.

Zorn's lemma states that a nonempty partially ordered set in which every chain has an upper bound contains a maximal element. Here a chain means a subset totally ordered by the inherited order; it need not have a greatest member.

View every partial function as its graph, a subset of $\mathbb{R}\times \mathbb{R}$. The family $\mathcal{F}$ is a set by axiom of separation from the power set of this product. Let $\mathcal{C}\subseteq \mathcal{F}$ be a chain and put $h=\bigcup \mathcal{C}$. If two members of the union assign values to the same input, the chain property makes one graph contain the other, so those values agree. Thus $h$ is a partial function.

If $x\in \mathrm{dom}h$ and $q\in \mathbb{Q}$, choose a chain member containing $x$ in its domain. Its rational-scalar closure gives $qx\in \mathrm{dom}h$. If $x,y\in \mathrm{dom}h$, choose two chain members containing them; the larger one contains both, and therefore contains $x+y$ with value $h(x)+h(y)$. Hence $h$ satisfies the required additive identity and domain closure. Consequentlyand it is an upper bound for the chain. For the empty chain its union is the empty function, which satisfies the defining logical implications vacuously, so this case is covered too.

A nonempty weakly linear function has a domain $D$ closed under rational scalars and addition, hence a vector subspace of $\mathbb{R}$ over $\mathbb{Q}$. Additivity first gives $f(0)=0$ and $f(-x)=-f(x)$, then $f(nx)=nf(x)$ for integers $n$. If $q=m/n$ with $n>0$, rational closure puts $qx$ in $D$ andThus $f(qx)=qf(x)$: it is a $\mathbb{Q}$-linear map. The empty function is not maximal because it extends to the function on $\{0\}$ with value zero.

Suppose a maximal $f$ had proper domain $D\ne \mathbb{R}$. Choose $t\notin D$ and any prescribed real value $a$, for instance $a=0$. Every element of $D+\mathbb{Q}t$ has a unique expression $d+qt$: if two expressions coincide and the coefficients differ, then $t$ would belong to $D$. DefineUniqueness makes this well-defined. The displayed logical formula and the $\mathbb{Q}$-linearity of $f$ show directly that $h$ is additive and has a domain closed under rational scalars. Hence it is a weakly linear function and extends $f$. It is a proper extension because $t$ is now in its domain, contradicting maximality. ThereforePart (a) and Zorn's lemma guarantee the existence of maximal extensions as well as this description of their domains.

Irrationality of $\sqrt{2}$ makes the expression $q+r\sqrt{2}$ unique for rational $q,r$: equality of two such expressions with different $r$ would express $\sqrt{2}$ as a rational number. Therefore the rule selecting the coefficient $r$ defines a function on $A$. Its domain is a vector subspace over $\mathbb{Q}$, and direct coefficient addition and rational scaling show it is $\mathbb{Q}$-linear, hence weakly linear. In particularUse Zorn's lemma on the nonempty family of weakly linear extensions of this particular function. Chain unions remain extensions by (a); hence there is a maximal extension $h$. Any further extension in $\mathcal{F}$ would also contain the original function, so this $h$ is maximal in $\mathcal{F}$. Part (b) therefore gives $\mathrm{dom}h=\mathbb{R}$.

A real-linear map $\mathbb{R}\to \mathbb{R}$ is multiplication by its value at $1$. Were $h$ real-linear, it would satisfycontradicting the inherited value $h(\sqrt{2})=1$. Thus a weakly linear function on all of $\mathbb{R}$ need not be real-linear. Its rational homogeneity of an additive function is insufficient for real homogeneity. This particular extension is also discontinuous: rational numbers approaching $\sqrt{2}$ have value zero, while the value at their limit is one.