Past exam of the logic and set theory course of the University of Oxford

A logical derivation of $\alpha$ from $\Gamma$ is a finite sequence ${\delta }_1,\dots ,{\delta }_n=\alpha$ in which each line belongs to $\Gamma$, is an instance of one of the three specified axiom schemes, or follows from two earlier lines ${\delta }_j$ and ${\delta }_j\to {\delta }_i$ by the modus ponens rule. $\Gamma ⊢\alpha$ means that such a finite derivation exists. In particular, a derivation uses only finitely many assumptions even if $\Gamma$ is infinite.

A theorem is derivable with no assumptions: $⊢\alpha$ abbreviates $\varnothing ⊢\alpha$. Its logical derivation consists entirely of axiom instances and applications of the modus ponens rule to earlier lines.

The following is a logical derivation using only A1, A2 and the modus ponens rule. The first two lines are assumptions:Thus $\boxed{\{\alpha \to \beta ,\beta \to \gamma \}⊢\alpha \to \gamma }$.

An instance of A3 isThe second assumed theorem and the modus ponens rule therefore give $\Gamma ⊢\beta \to \alpha$. Apply the preceding implication-composition derivation to this theorem and $\Gamma ⊢\neg \alpha \to \beta$. We obtain $\Gamma ⊢\neg \alpha \to \alpha$. The permitted theorem $(\neg \alpha \to \alpha )\to \alpha$ and one more modus ponens rule application yield $\boxed{\Gamma ⊢\alpha }$.

Logical equivalence means that the two propositional formulas receive the same truth value under every Boolean valuation of the propositional variables. Equivalently, $\alpha \leftrightarrow \beta$ is a tautology:

Assign to each propositional formula its finite symbol length. The set of lengths of formulas logically equivalent to $\alpha$ is a nonempty subset of the natural numbers, because it contains the length of $\alpha$. The well-ordering principle for the natural numbers gives a least such length, and hence a shortest equivalent formula.

A shortest equivalent formula need not be unique. For example $(p_0\to p_0)$ and $(p_0\leftrightarrow p_0)$ are distinct tautologies of the same minimal length. A shorter formula would contain no binary connective and hence be a variable with some number of negations, which is not a tautology. This counts each propositional variable as one symbol, as in the stated language, and proves that a shortest equivalent formula need not be unique.

A conjunctive normal form is a finite conjunction of clauses, each clause being a finite disjunction of literals. A literal is a propositional variable or the negation of one. Thus its shape isA single clause or single literal is allowed; the necessary parentheses can be inserted according to the grammar.

First eliminate implication and biconditional using the logical equivalencesPush negations inwards using De Morgan's laws and eliminate double negations. Structural induction leaves only literals joined by conjunction and disjunction.

Now induct on that remaining expression. A literal is already in conjunctive normal form. A conjunction of two conjunctive normal forms is again one after associating its clauses. For a disjunction, write the two inductively obtained forms as ${\bigwedge }_i{C}_i$ and ${\bigwedge }_j{D}_j$ and use distributivity:Each $C_i\vee D_j$ is a clause. All operations preserve logical equivalence, proving the required form exists.

A first-order structure for this language is $\mathcal{A}=(A,f^{\mathcal{A}})$, where $A$ is a nonempty set and $f^{\mathcal{A}}:A\to A$ is a total function. The logical equality symbol is interpreted as actual equality on $A$; there are no other nonlogical symbols to interpret.

Use an involution with exactly one fixed point:The first conjunct makes every orbit of the function $f$ have size one or two. The second says precisely one orbit has size one. A finite model therefore has $1+2m$ elements, an odd number.

Conversely, on any set of size $2m+1$, fix one element and partition the remaining $2m$ elements into pairs; let $f$ swap the two members of each pair. This defines a model of $\varphi$. The case $m=0$ gives a one-element model. Thus the finite model sizes are exactly the positive odd integers.

Extend the first-order variable assignment recursively to first-order terms byFor atomic formulas, $\mathcal{A}\models t=s[v]$ exactly when $\tilde{v}(t)=\tilde{v}(s)$. Extend to the Boolean connectives by their truth tables, for example implication is false exactly when its antecedent is true and its consequent false. Quantifiers use modified first-order variable assignments:This recursion defines satisfaction for a set structure for every first-order formula.

Semantic consequence under an assignment means that for every first-order structure $\mathcal{A}$ with the relevant first-order variable assignment $v$ into its domain,More explicitly, in a fixed structure this is the satisfaction implication at $v$; logical consequence requires that implication in all structures and assignments. An assignment takes values in a particular domain, so a single set map is not silently shared between unrelated domains.

By induction on first-order formulas, their truth values depend only on the values of their free variables. A first-order sentence has none. If all formulas here are sentences, every displayed satisfaction statement, and therefore the consequence condition, is independent of $v$.

The antecedent says that the nonempty domain has at most two elements: its two witnesses need not be distinct. The consequent says it has exactly one element. ThusOne-element structures satisfy both sides; domains of size at least three, including infinite domains, make the antecedent false. The function $f$ has no bearing on this condition.

A two-element model of $\varphi$ would be a finite model with even size, contrary to the defining property established in part (b). Every model of $\varphi$ therefore has size other than two, and the preceding interpretation of $\psi$ gives $\boxed{\{\varphi \}\models \psi }$. This includes infinite models, since the antecedent of $\psi$ is false there.

The compactness theorem states that a set of first-order sentences has a model if every finite subset has a model.

For each $n\ge 1$, let ${\chi }_n$ assert that at least $n$ distinct elements exist. Consider $T=\{\varphi \}\cup \{{\chi }_n:n\ge 1\}$. A finite subset requires only some finite lower bound $N$ on the size. Choose an odd integer $m\ge N$; the given property of $\varphi$ supplies a model of that size, satisfying the finite subset. By the compactness theorem, $T$ has a model. Its domain has at least $n$ elements for every $n$, so $\varphi$ has an infinite model. This argument applies to every sentence with the finite-model-size property in (b), irrespective of its behavior on infinite structures.

A logical derivation is a finite proof in the specified calculus, with conclusion $\Gamma ⊢\varphi$. Assumptions from $\Gamma$ and instances of A1–A7 are available; the rules are the modus ponens rule, universal generalization rule, and weakening.

In judgement form the universal generalization rule takes $\Delta ⊢\theta$ to $\Delta ⊢\forall x_i\theta$ only if $x_i$ is not free in any undischarged assumption in $\Delta$. Weakening permits $\Delta ⊢\theta$ to become $\Delta \cup \Sigma ⊢\theta$. All instances of A4 and A5 must meet their stated substitution and free variable conditions. Derivability means existence of such a finite proof with assumptions contained in $\Gamma$. Equivalently one tracks the finite assumption set used by each proof line.

The first-order term $t$ is free for substitution for $x_i$ in $\varphi$ if, at every free occurrence of $x_i$ to be replaced, no enclosing quantifier binds a variable occurring in $t$. Equivalently, the substitution introduces no variable capture. Only free occurrences of $x_i$ are replaced.

Take $\varphi =\forall x_1(x_0=x_1)$. The term $x_2$ is free for substitution for $x_0$: its variable is not bound by the enclosing quantifier. The term $x_1$ is not free for substitution for $x_0$, because insertion under $\forall x_1$ captures that occurrence.

Thus the first substitution gives $\forall x_1(x_2=x_1)$; the second, illegitimate substitution would give $\forall x_1(x_1=x_1)$.

In a two-element first-order structure, $\varphi =\forall x_1(x_0=x_1)$ is false for every first-order variable assignment. Blind substitution of $x_1$ for $x_0$ yields $\forall x_1(x_1=x_1)$, which is true. This does not express the original property evaluated at the value of the inserted term: it has changed a free parameter into a bound variable.

For a direct failure of the substitution axiom, use $\theta (x_0)=\exists x_1(x_0\ne x_1)$. On a two-element domain, $\forall x_0\theta (x_0)$ is true, whereas the captured instance $\exists x_1(x_1\ne x_1)$ is false. Consequently an unrestricted A4 would prove a false implication. The free for substitution condition is necessary for soundness.

Write $E(x,y)$ for the displayed equality predicate. A6 and A4 give $⊢E(x,x)$, establishing a reflexive relation.

An instance of A7, replacing just the first occurrence of $x$ in $E(x,x)$, isAssume $E(x,y)$, apply the modus ponens rule twice using reflexivity, and obtain $E(y,x)$. The deduction theorem for propositional logic discharges the assumption. This proves symmetry.

For transitivity, A7 suppliesby replacing $y$ in the atomic formula $E(x,y)$. From assumptions $E(x,y)$ and $E(y,z)$, two applications of the modus ponens rule give $E(x,z)$. Discharging assumptions and universally generalizing givesThus the predicate defines an equivalence relation within the calculus.

No such first-order axiom collection can force actual identity when the displayed symbol is treated as an ordinary relation. The duplication obstruction to axiomatizing identity proves this even for an infinite collection of extra axioms.

Start with any nonempty first-order structure $\mathcal{A}$ in which the symbol is identity. Form $B=A\times \{0,1\}$ and the surjection $\pi :B\to A$. Interpret each relation by pulling it back along $\pi$; in particular,Interpret every function on first coordinates as in $\mathcal{A}$ and choose second coordinate zero; likewise lift constants with second coordinate zero. Induction on first-order terms gives $\pi (t^{\mathcal{B}}(v))=t^{\mathcal{A}}(\pi v)$. Induction on first-order formulas then givesThe quantifier steps use surjectivity of $\pi$, so every witness in $A$ lifts to $B$.

Every proposed axiom valid with actual equality is therefore true in $\mathcal{B}$ under every assignment, along with A1–A7. But $E^{\mathcal{B}}((a,0),(a,1))$ holds for two different domain elements. Thus those axioms cannot enforce identity. The usual interpretation of logical equality as identity is a semantic requirement.

An approximation is a function $s:n+1\to X$ with $s(0)=x_0$ and $s(k+1)=g(s(k))$ for $k<n$. By induction on $n$, there is such a function: start with $\{(0,x_0)\}$ and append the uniquely specified value $g(s(n))$.

Any two approximations agree on their common domain, by induction from their common initial value and the same transition function $g$. The collection $\mathcal{S}$ of all approximations is a set, being a definable subset of $\mathcal{P}(\omega \times X)$. Therefore $f=\bigcup \mathcal{S}$ is a function. Existence of approximations of every finite length gives $\mathrm{dom}(f)=\omega$. Each defining equation appears in a sufficiently long approximation, soThis proves the natural-number recursion theorem without the axiom of choice; no arbitrary sequence of choices was made.

Suppose $h:\omega \hookrightarrow X$ is an injection. Shift its image by definingThe two pieces have disjoint images, so $g$ is injective, but $h(0)$ is omitted. Thus $g$ is not surjective.

Conversely, let $g:X\to X$ be an injection which omits some $a\in X$. The natural-number recursion theorem defines $h(0)=a$, $h(n+1)=g(h(n))$. If $h(m)=h(n)$ with $m<n$, repeated injectivity cancels $m$ iterations and gives $a=g^{n-m}(a)$, putting $a$ in the image of $g$, a contradiction. Hence $h$ is injective. ThereforeChoosing one witness $a$ from a single known nonempty set uses no axiom of choice. This is the Dedekind-infinite characterization.

The Cantor-Schröder-Bernstein theorem states that injections $A\hookrightarrow B$ and $B\hookrightarrow A$ imply a bijection $A\cong B$.

Let $\mathfrak{c}=|\mathbb{R}|$ and $\mathcal{D}=\{S\subseteq \mathbb{R}:S\text{ is dense in }\mathbb{R}\}$. Clearly $|\mathcal{D}|\le 2^{\mathfrak{c}}$. For the reverse bound, let $C$ be the usual Cantor set, of cardinality $\mathfrak{c}$. It is closed with empty interior, so $D=\mathbb{R}\setminus C$ is dense. The mapis injective, because $A=(D\cup A)\cap C$. Applying the Cantor-Schröder-Bernstein theorem givesOne can see $|C|=\mathfrak{c}$ by coding binary sequences as ternary expansions using only digits zero and two, together with the usual $|\{0,1{\}}^{\omega }|=|\mathbb{R}|$. The same fixed $D$ works for all subsets. This is the cardinality of the family of dense subsets of the reals.

A transitive set $X$ is one for which every member is a subset: $\forall y\in X(y\subseteq X)$, equivalently $\bigcup X\subseteq X$. If $x\in y\in X$, the subset condition puts $x\in X$. Conversely, if this membership implication always holds, every element of each $y\in X$ belongs to $X$, so $y\subseteq X$. Thus

Let $a\in b\in \mathcal{P}(X)$. Since $b\subseteq X$, we have $a\in X$. Transitivity of $X$ gives $a\subseteq X$, so $a\in \mathcal{P}(X)$. This is exactly the membership criterion for a transitive set, proving the power set of a transitive set is transitive.

A well-order is a strict total order in which every nonempty subset has a least element. A Von Neumann ordinal is a transitive set well-ordered by membership. Thus its predecessors are precisely its members, and its ordering is the restriction of $\in$.

Put $\alpha =\bigcup X$. Every element of $\alpha$ belongs to some ordinal in $X$ and is itself an ordinal. If $u\in v\in \alpha$, choose $\beta \in X$ with $v\in \beta$; transitivity of $\beta$ gives $u\in \beta \subseteq \alpha$. Thus $\alpha$ is a transitive set of ordinals.

Any two ordinals are comparable by membership or equality, so membership strictly totally orders $\alpha$. Every nonempty subset $A\subseteq \alpha$ has an $\in$-minimal element by the Axiom of foundation, and totality makes it the least element. Hence $\bigcup X$ is an ordinal, including $\bigcup \varnothing =0$.

Use transfinite induction. For any $\beta <\alpha$, the induction hypothesis and strict increase give $\beta \le F(\beta )<F(\alpha )$. Thus every $\beta <\alpha$ belongs to $F(\alpha )$, so $\alpha \subseteq F(\alpha )$, i.e.This includes $\alpha =0$ and does not yet use continuity of the normal function on an ordinal.

By the natural-number recursion theorem, let ${\alpha }_0=0$ and ${\alpha }_{n+1}=F({\alpha }_n)$. These ordinals form a nondecreasing sequence by the preceding bound. If ${\alpha }_{n+1}={\alpha }_n$ for some $n$, it is already a fixed point.

Otherwise the sequence is strictly increasing. Its supremum $\lambda ={\bigcup }_{n<\omega }{\alpha }_n$ is a limit ordinal, and the sequence is cofinal in it. Continuity and monotonicity giveFor the middle equality, every $\beta <\lambda$ is below some ${\alpha }_n$, while every ${\alpha }_n<\lambda$. Therefore $F$ has a fixed point. The sequence is a set by Axiom schema of replacement, since $F$ is a definable set-theoretic class function.

Repeat the preceding construction starting at ${\alpha }_0=\gamma +1$, for any given ordinal $\gamma$. A stabilized value or the strictly increasing sequence's supremum is a fixed point at least $\gamma +1$. Thus fixed points occur above every ordinal.

If the fixed points formed a set $S$, their union would be an ordinal bounding them all. Applying the construction above that bound contradicts it. HenceThis is the unboundedness part of the fixed point of a normal ordinal function theorem.

The four principles are:

In the last assertion the upper bound belongs to the partially ordered set; it need not belong to the chain.

Assume the well-ordering theorem. Every set with a chosen well-order has an order isomorphism to a unique ordinal. Any two ordinals are comparable, and the smaller embeds into the larger as an initial segment. Transporting that embedding back to the original sets proves the cardinal comparability principle.

Conversely, assume the cardinal comparability principle and let $X$ be any set. The Hartogs theorem, provable in ZF, supplies an ordinal $h(X)$ for which no injection $h(X)\hookrightarrow X$ exists. Comparison forces an injection $X\hookrightarrow h(X)$. Pulling back the well-order on its image gives a well-order on $X$. ThereforeThe assumed ordinal facts are that every well-ordered set has an ordinal order type and that any two ordinals are comparable; the other assumed theorem is precisely the stated Hartogs theorem.

For the standard definition of algebraic independence, finite tuples are required to have distinct entries. Let $\mathcal{P}$ be the set of all subsets of $L$ with algebraic independence over $K$, ordered by inclusion. It is nonempty because $\varnothing \in \mathcal{P}$.

If $\mathcal{C}$ is a chain in $\mathcal{P}$, put $U=\bigcup \mathcal{C}$. A finite tuple of distinct elements of $U$ lies in one member of $\mathcal{C}$: choose a member containing each element and take the largest of those finitely many members. A polynomial relation on that tuple would then be a polynomial relation in that member, contradicting its algebraic independence. Thus $U\in \mathcal{P}$ and is an upper bound. For the empty chain, $\varnothing$ is an upper bound. The Zorn's lemma now gives a maximal member $B$, which is a transcendence basis by the specified maximality criterion. To also recover the usual field-theoretic definition, if $a\in L$ were transcendental over $K(B)$, clearing denominators in a polynomial relation would show that $B\cup \{a\}$ still has algebraic independence over $K$, contradicting maximality. Thus $L$ is algebraic over $K(B)$. Hence every field extension has a transcendence basis.

There is a literal issue in the printed definition: it does not require the tuple entries to be distinct. With that wording, any nonempty $X$ fails the test: for $a\in X$, the nonzero polynomial $X_1-X_2$ vanishes on $(a,a)$, in every characteristic. Thus under the literal printed test the family is exactly $\{\varnothing \}$, and $\varnothing$ is its maximal member. The same chain-and-Zorn's lemma argument still proves existence for that literal notion, but it is not the usual transcendence basis notion. The conventional result above uses distinct tuple entries.

Let $\mathcal{O}$ be the set of strict total orders on $\kappa$. Each is a subset of $\kappa \times \kappa$, so the square of an infinite cardinal givesFor the lower bound, use the set $\kappa \times \{0,1\}$ and order the two-element blocks by their first coordinates, using the well-order of $\kappa$. For every $A\subseteq \kappa$, put $(\alpha ,0)$ before $(\alpha ,1)$ exactly when $\alpha \in A$, reversing them otherwise. This defines a strict total order for each $A$, and different subsets give different orders. Transport these orders to $\kappa$ along a fixed bijection $\kappa \times \{0,1\}\cong \kappa$. Thus $2^{\kappa }\le |\mathcal{O}|$, and the Cantor-Schröder-Bernstein theorem givesIf using the customary axiom of choice development of infinite cardinal arithmetic, its use here is precisely to supply $\kappa \times \kappa \cong \kappa$ and $\kappa \times 2\cong \kappa$. The ordering construction makes no further choices. It proves the cardinality of the family of strict total orders. For $\kappa$ itself an initial ordinal, these particular product identities can also be proved in ZF by well-ordering pairs according to their maximum coordinate, so full axiom of choice is stronger than this instance intrinsically requires.