Past exam of the logic and set theory course of the University of Oxford / 2007 (B1, DMAB 2640, DMCN 2640, DMPB 2640, DMST 2640)

This University of Oxford Part B paper is cross-listed for Mathematics, Mathematics and Computer Science, Mathematics and Philosophy, and Mathematics and Statistics. Section A concerns mathematical logic and section B concerns set theory. ^[ref] The archive contains a complete editable five-page transcription. Bounded official-source searches found no advertised answers to this exact paper. All 29 source leaves and the attached unnumbered tasks are covered below. In Q7(v), the convergence condition is retained exactly as printed, without adding absolute-value bars.

A Boolean valuation is an arbitrary function $v$ assigning one of the two truth values to each propositional variable. It extends uniquely to all propositional formulas by following the construction of the propositional formula:For logical implication, $\tilde{v}(A\to B)$ is false exactly when $\tilde{v}(A)$ is true and $\tilde{v}(B)$ is false; otherwise it is true. Here the operations on the right are Boolean operations on truth values. Structural recursion gives existence, and structural induction gives uniqueness: once the immediate subformulas have their values, the outer connective fixes the resulting value.

Two propositional formulas are logically equivalent if every Boolean valuation gives them the same truth value. A disjunctive normal form is a logical disjunction of logical conjunctions of literals, with a literal being a propositional variable or its negation.

Let $p_1,\dots ,p_n$ include all propositional variables appearing in $\varphi$. For each Boolean valuation $s\in \{T,F{\}}^n$, putThe minterm $M_s$ is true exactly for Boolean valuations whose restrictions to these propositional variables are $s$. ConsequentlyIndeed, an Boolean valuation making $\varphi$ true makes its own minterm true, while a true minterm in the displayed logical disjunction certifies the truth of $\varphi$. There are only finitely many Boolean valuations, so this is a finite disjunctive normal form. If there are no satisfying Boolean valuations, use $p\wedge \neg p$ for any propositional variable $p$; this is a disjunctive normal form for falsity without needing an empty logical disjunction convention.

Assume first that $\varphi$ is false on the all-true and all-false Boolean valuations. Use the truth-table normal form from part (ii). Every satisfying Boolean valuation on the finitely many propositional variables must have at least one true propositional variable and at least one false propositional variable. Its minterm therefore has the formwhere $C_s$ conjoins its true propositional variables and $D_s$ disjoins its false propositional variables; both lists are nonempty. This is equivalent to $\neg (C_s\to D_s)$. If the satisfying Boolean valuations are indexed by $1,\dots ,N$, De Morgan's laws givesIf there are no satisfying Boolean valuations, take $N=1$ and $C_1=D_1=p$: the result is $\neg (p\to p)$, again always false.

Conversely, on the all-true Boolean valuation every nonempty $D_i$ is true, so every $C_i\to D_i$ is true. On the all-false Boolean valuation every nonempty $C_i$ is false, so every logical implication is again true. Negating their logical conjunction gives false on both Boolean valuations. Logical equivalence transfers these values to $\varphi$. The usual nonempty meaning of logical conjunction and logical disjunction of propositional variables is used here; allowing empty $C_i$ or $D_i$ without qualification would destroy this converse.

A logical derivation from $\Gamma$ is a finite sequence of propositional formulas, each either a member of $\Gamma$, an instance of one of the three axioms, or obtained from earlier lines by one of the two displayed inference rules. The notation $\Gamma ⊢\alpha$ means that some such logical derivation ends in $\alpha$. Writing $⊢\alpha$ means derivability with no assumptions.

Propositional consistency means that there is no propositional formula $\theta$ for which both $\Gamma ⊢\theta$ and $\Gamma ⊢\neg \theta$. Equivalently not every propositional formula is derivable. To check the equivalence directly for this calculus, use the identity theorem proved in (ii): from $\theta \to \theta$ and L3 obtain $\theta \to (\neg \theta \to \eta )$; two uses of modus ponens rule give arbitrary $\eta$. Thus a contradictory theory proves everything. Conversely a theory proving everything proves a propositional formula and its negation.

Choose an auxiliary propositional formula $\beta$. The two instances of L1 areThe instance of L2 with $\gamma =\alpha$ isApply modus ponens rule first with the first L1 instance and then with the second. This is an assumption-free logical derivation, soIn particular no semantic completeness theorem or deduction theorem for propositional logic has been assumed to obtain this identity theorem.

An instance of L3 isUsing the first assumed logical derivation and modus ponens rule gives $\Gamma ⊢\alpha \to (\neg \beta \to \gamma )$. The L2 instance for these same three propositional formulas isUse the other assumed logical derivation and then the newly obtained logical derivation in two applications of modus ponens rule. ThereforeThis conditional modus ponens construction is the step needed to discharge assumptions from a modus ponens rule line in part (iv).

For this calculus the deduction theorem for propositional logic isFor the reverse logical implication, retain the logical derivation from $\Gamma$, add the assumption $\alpha$, and use modus ponens rule.

For the forward logical implication, induct on a logical derivation from $\Gamma \cup \{\alpha \}$. For each line $\delta$ we construct a logical derivation of $\alpha \to \delta$ from $\Gamma$. If $\delta =\alpha$, use (ii). If $\delta$ is an axiom instance or belongs to $\Gamma$, it is already derivable from $\Gamma$; L1 gives $\delta \to (\alpha \to \delta )$, and modus ponens rule finishes that case.

If $\delta$ comes from $\eta$ and $\eta \to \delta$ by modus ponens rule, the induction hypothesis suppliesPart (iii) supplies $\Gamma ⊢\alpha \to \delta$.

If $\delta$ comes by the elimination rule E from $\eta \to \delta$ and $\neg \eta \to \delta$, the induction hypothesis suppliesThe L2 instance with $(\alpha ,\beta ,\gamma )=(\alpha ,\eta ,\delta )$ combines these by two applications of modus ponens rule. Thus the rule E also survives the discharge construction. These are all possible lines, proving the theorem for the final line $\beta$.

Suppose both extensions were inconsistent. By the explosion argument in (i), the extension by $\varphi$ proves $\neg \varphi$, and the extension by $\neg \varphi$ proves $\varphi$. The deduction theorem for propositional logic therefore yieldsThe identity theorem gives $⊢\neg \varphi \to \neg \varphi$ and $⊢\varphi \to \varphi$. Apply E to the first displayed logical implication and the identity logical implication with antecedent $\neg \varphi$ to obtain $\Gamma ⊢\neg \varphi$. Apply E to the identity logical implication with antecedent $\varphi$ and the second displayed logical implication to obtain $\Gamma ⊢\varphi$. This contradicts propositional consistency of $\Gamma$.

Consequently at least one of the two one-formula extensions is propositionally consistent. The formal proof uses the source's own calculus, including its rule E, rather than assuming an unproved completeness theorem for this presentation.

The first-order terms are the smallest collection containing every variable and $c$ and containing $F(s,t)$ whenever $s,t$ are first-order terms. The atomic formulas are exactly $s\approx t$ for first-order terms $s,t$. Logical formulas are then obtained from atomic formulas by the logical connectives and quantifiers: if $\theta ,\psi$ are logical formulas and $x$ a variable, then $\neg \theta$, $(\theta \wedge \psi )$, $(\theta \vee \psi )$, $(\theta \to \psi )$, $\forall x\theta$ and $\exists x\theta$ are logical formulas. These closure rules, with no additional strings admitted, define the syntax; a presentation using fewer primitive connectives treats the others as abbreviations.

Semantic entailment is the conditionThe same first-order variable assignment is used for all premises and the conclusion. This matters when free variables occur; for first-order sentences the truth value is independent of the first-order variable assignment.

For independence, construct four first-order structures, each satisfying exactly the three required remaining axioms and failing the chosen one.

To fail associativity, use the carrier $\{0,1,2\}$, interpret $c$ as $0$, and define the commutative operation by its table:The first row and column give a two-sided identity, and every element is its own inverse because the diagonal entries are $0$. Symmetry gives commutativity. Butso associativity fails.

To fail the identity axiom, take $\{0,1\}$, $c=0$, and the constant operation $F(x,y)=0$. It is associative and commutative, and every element has a two-sided partner producing $c$; but $F(1,c)=0\ne 1$.

To fail the inverse axiom, use natural numbers under addition with $c=0$. Addition is associative and commutative and has the required identity, but $1$ has no additive inverse in this carrier.

To fail commutativity, use the symmetric group $S_3$ under permutation composition with $c$ its identity. Associativity, identity and inverses are group properties, while $(12)(23)\ne (23)(12)$. Each countermodel witnesses the failure of semantic entailment from the other three to the failed first-order sentence. Hence the four source axioms are independent.

Soundness states that formal derivability implies semantic entailment:For first-order sentences this means that every first-order structure satisfying all assumptions also satisfies every first-order sentence formally derived from them. In the logical formula version one uses the usual restrictions on generalization from assumptions with free variables.

Strong completeness states the converse:Equivalently, every syntactically consistent set of first-order sentences has a first-order model. Equality is interpreted as actual identity, and its usual logical axioms and substitution rules are part of the standard calculus. Both assertions hold for arbitrary sets of assumptions, rather than only finite sets.

The compactness theorem says that a set $T$ of first-order sentences has a first-order model if and only if every finite subset of $T$ has a first-order model. One direction follows by using the same first-order model for each subset.

For the nontrivial direction suppose every finite subset has a first-order model, but $T$ has none. Semantically $T\models \perp$, so completeness gives a formal logical derivation $T⊢\perp$. A formal logical derivation is finite and uses only finitely many assumptions, say $T_0\subseteq T$. Thus $T_0⊢\perp$. Soundness would make $T_0$ unsatisfiable, contradicting the hypothesis. Here $\perp$ can be any fixed contradictory first-order sentence, such as $\exists x(x\ne x)$, if it is not a primitive logical symbol. Therefore finite satisfiability implies satisfiability.

Take $S_1$ to consist of the three usual first-order sentencesThese assert reflexivity, symmetry and transitivity and therefore define exactly the equivalence relations.

For $S_2$, adjoin to $S_1$ the single first-order sentenceIts witness $y$ gives a second member of each class, while its final universal clause excludes all others. Hence every class has exactly two members, and conversely such a relation satisfies it. This remains a finite set of first-order sentences.

For each positive integer $n$, writeThenEvery class in a first-order model has at least $n$ elements for every $n$, so cannot be finite. Conversely every infinite equivalence class supplies each finite collection of distinct witnesses. The displayed infinite scheme therefore has exactly the requested first-order models.

Suppose such a first-order theory $S$ existed. Add two new constants $c,d$ and considerwhere ${\theta }_n$ is the finite lower-bound logical formula from (iii).

Every finite subset of $T$ has a first-order model. Choose a first-order structure with exactly two equivalence classes: one countably infinite, and one finite of size at least the largest bound appearing in that subset. Interpret $c$ in the infinite class and $d$ in the finite class. The first-order structure satisfies all of $S$, by its assumed characterization, and meets the finite demands on both named classes.

Compactness theorem in the language with the two new constants gives a first-order model of all of $T$. Its classes of $c$ and $d$ are distinct and both infinite. Its reduct still satisfies $S$, which is impossible if $S$ characterizes exactly one infinite class. HenceThe finite approximations work because any finite list of lower bounds permits the second class to remain finite; the entire list prevents that escape.

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.