Codex @codex  0

The relation $A\subseteq B$ means that the domain of $A$ is a subset of the domain of $B$ and the inclusion map is an $L$-embedding. Thus it contains all named constants, is closed under every named function, and uses the restrictions of the ambient relations.

The stronger relation $A\preccurlyeq B$ means that for every first-order formula $\varphi (\bar{x})$ and tuple $\bar{a}$ from $A$,This includes formulas with quantifiers ranging over the respective domains. Elementary inclusion implies ordinary substructure inclusion, but the latter need only preserve quantifier-free truth. In particular an existential witness available in $B$ need not lie in an arbitrary substructure.

The complete theory $\mathrm{Th}(A)$ is the set of all $L$-sentences true in $A$. The existential theory of a structure ${\mathrm{Th}}_{\exists }(A)$ consists of those true sentences of the form $\exists \bar{x}\theta (\bar{x})$ with quantifier-free $\theta$. The universal theory ${\mathrm{Th}}_{\forall }(A)$ uses $\forall \bar{x}\theta (\bar{x})$ with quantifier-free matrix. Allow equivalent formulas and empty quantifier blocks, or insert dummy variables in nonempty domains. These are sentences in the original language, distinct from diagrams, which add constants naming Elements of the structure.

The term $x+z$ is free for substitution for $z$. The only free occurrence of the target $z$ is in the outside disjunct $y<z$, beyond both quantifier scopes. The occurrences under $\forall z$ are bound variables and are not replaced. Therefore no renaming is required, andThe new $x$ and $z$ in the last disjunct are free. First-order substitution replaces the original free occurrences once; it does not recursively substitute into the inserted term.

The term $x+z$ is not free for substitution for $y$. The occurrence of $y$ in $x<y$ is under $\exists x$, which would capture the inserted $x$. The other occurrence, in the outside disjunct $y<z$, has no enclosing quantifier. The inner $\forall z$ does not bind the occurrence of $y$ in its antecedent, so it creates no additional capture at that substitution site.

Rename the bound $x$ to a fresh $u$, then carry out capture-avoiding first-order substitution. The result isThe inserted $z$ in $u<x+z$ remains free because it lies outside the scope of $\forall z$. One may additionally rename that bound $z$ for readability, but it is not necessary for correctness.

The printed expression has one unmatched closing parenthesis. Remove that final surplus parenthesis and read the first disjunct as $\exists xP(x)$; the other disjunct has outer universal quantification over the displayed implication. To distinguish the two independent bound uses of $x$, rename the first to $u$.

Push the outer negation through the logical disjunction and through the quantifiers. Negating the implication preserves its existential antecedent and negates its consequent. Applying De Morgan's laws and the quantifier negation rules gives the negation normal formEach negation is now directly before an atomic formula. No bound variable has been captured, and no original existential quantification in the antecedent has accidentally been negated twice.

Solutions to all eight questions of the Oxford Preliminary Examination held on 15 June 2023. Source release: released examination archive, member 2022/T/a10101w1.pdf. The cover identifies Trinity Term 2023. The three section headings and all question labels below follow this historical paper; its grouping is independent of subsequent course changes. Although candidates were asked to attempt at most five questions, every marked subpart is solved here.

In 8(b), the source's parenthetical definition describes a dominating set, while its name suggests a vertex cover. Both readings are treated explicitly. In 8(c)–(d), we make the scopes of the printed quantifiers explicit; in particular, the opening universal quantifiers in 8(c) govern both irreflexivity and transitivity. As usual in first-order logic, domains are nonempty, and graphs are finite simple graphs unless an infinite domain is specified.

The nonempty simple graphs having an independent vertex cover of size at most two. The witnesses $x,y$ select the cover. The clause $\neg E(x,y)$ makes the selected vertices nonadjacent; the universal clause forbids every edge whose two endpoints both lie outside the selected set.

The witnesses need not be distinct, so a one-vertex cover is permitted by choosing $x=y$. A nonempty edgeless graph also satisfies the formula. The empty graph does not, because the existential quantifiers have no witnesses. Here independent vertex cover has its standard vertex cover meaning; 8(b)'s differing parenthetical definition is addressed separately below.

Read the initial universal quantifiers as governing the conjunction of irreflexivity and transitivity. Explicitly, the intended first-order sentence assertsThus $Q$ is an irreflexive relation, a transitive relation, and a serial relation.

Suppose a first-order model had a finite nonempty domain of cardinality $N$. Choose $a_0$. Seriality supplies successive elements $a_1,\dots ,a_N$ with $Q(a_i,a_{i+1})$. By the pigeonhole principle, $a_i=a_j$ for some $i<j$. Repeated transitivity along that part of the chain gives $Q(a_i,a_j)=Q(a_i,a_i)$, contradicting irreflexivity. Hence there is no finite nonempty model. This is the infinite-model property of a serial strict partial order.

An infinite model exists: take domain $\mathbb{N}$ and $Q(x,y)$ to mean $x<y$. It is irreflexive and transitive, and $y=x+1$ witnesses seriality for every $x$.

The quantifier-scope convention matters: giving each printed universal quantifier only the immediately following atomic scope would leave the transitivity implication with free variables and would not express the claimed theorem. The explicit parenthesisation above records the reading under which the source's requested assertion is valid.

Push the outer negation inward using De Morgan's laws and the duality of universal and existential quantifiers. Negating the outer universal quantifier first gives an existential $x$. Negating its conjunction produces either $\forall y\neg P(x,y)$ or a witness $z$ for failure of the other conjunct. The implication fails precisely when $\neg Q(z)$ holds but its consequent fails. Therefore a negation normal form isAll negations now apply directly to atomic formulas. In particular, the $\neg Q(z)$ remains negative: failure of an implication requires its antecedent to be true.

A propositional substitution maps each atomic propositional variable to a propositional formula and extends recursively through every logical connective. Replacements are simultaneous: a variable appearing inside a replacement formula is not replaced again in the same substitution step. Since propositional logic has no variable-binding quantifiers, this operation has no variable-capture problem.

A quantified formula has a quantifier as its outermost formation: it is of the form $\forall x\theta$ or $\exists x\theta$. The quantifier binds the indicated variable occurrences according to the formation rules.

A quantifier binds a free variable in a first-order formula and specifies how its truth depends on elements of a first-order structure: universal quantification $\forall$ requires every element, while existential quantification $\exists$ requires at least one.

In the language naming addition, zero and every scalar multiplication over a fixed field, the theory of infinite underlying vector spaces eliminates quantifiers. In a conjunction of linear equations and inequations, an equation with a nonzero coefficient solves for the quantified variable. Otherwise the variable is excluded from only finitely many values, so infinitude supplies a witness. Disjunction and induction finish elimination. This works over finite fields with infinite dimension and over infinite fields with every nonzero dimension.

A uniformly continuous function has one input tolerance valid throughout its domain of a function. For $f:D\to \mathbb{R}$, with $D\subseteq \mathbb{R}$, uniform continuity meansChoose the output tolerance $\epsilon$ first, then a positive $\delta$ valid for every pair of function inputs. It may depend on $\epsilon$, the function and its domain of a function, but not on the pair’s location. The absolute values measure input and output distance.^[ref]

Compare the quantifier order with the epsilon-delta definition of continuity:Both lines end with $|x-a|<\delta \Rightarrow |f(x)-f(a)|<\epsilon$. In the first, $\delta$ can depend on the point $a$; in the second, it is chosen before $a$. Thus uniform continuity implies continuity at every point. Each requested $\epsilon$ gets its own shared tolerance.

For an exact example, take the polynomial function $f(x)=x^2$ on the closed interval $D=[0,2]$. For every pair of function inputs in that interval, polynomial factorization givesConsequently $\delta =\epsilon /4$ works everywhere on this domain of a function. With $\epsilon =0.4$, the common tolerance is $\delta =0.1$. Near the right endpoint, for example, $x=1.92$ and $y=2$ have input distance $0.08$ and output distance $4-1.92^2=0.3136<0.4$. The bound is sufficient; it does not claim the largest admissible input window at each point.

On the whole real line, the same polynomial function is a continuous function but fails uniform continuity. Take the sequences $x_n=n$ and $y_n=n+1/n$, for positive integers $n$. ThenFor any proposed $\delta >0$, choose an integer $n>1/\delta$. The inputs are closer than $\delta$, yet their outputs violate the fixed tolerance $\epsilon =1$. The sequences need not themselves have a finite limit: their mutual distance is what tends to zero. This is the obstruction captured by the sequential criterion for uniform continuity. Restricting the domain of a function to $[0,2]$ removes these escaping pairs.

A uniformly continuous function need not be a bounded function. The identity function $f(x)=x$ on the real line has $|f(x)-f(y)|=|x-y|$, so $\delta =\epsilon$ always works, although its image of a function is the unbounded real line. Uniform continuity controls changes between nearby inputs, not the overall size of outputs. Likewise, an unbounded domain of a function does not by itself prevent uniform continuity.

The square root $g(x)=\sqrt{x}$ supplies a different common tolerance on the interval $[0,\infty )$. Assuming $x\ge y\ge 0$, put $u=\sqrt{x}$ and $v=\sqrt{y}$. Since $0\le u-v\le u+v$,Interchanging the inputs when necessary provesThus $\delta ={\epsilon }^2$ guarantees uniform continuity on the entire domain of a function, including zero. For $\epsilon =0.4$, any input distance below $0.16$ suffices. The pairs $(0,0.09)$ and $(4,4.09)$ both have input distance $0.09$; their output distances are respectively $0.3$ and $0.09/(\sqrt{4.09}+2)<0.0225$. The common guarantee accommodates quite different local sensitivities.

This Hölder continuity bound allows a curved tolerance rule. It is weaker than a Lipschitz bound: at zero the output change divided by the input change isNo finite Lipschitz constant works near zero, even though uniform continuity does. A Lipschitz function does have uniform continuity, choosing $\delta =\epsilon /L$ when its Lipschitz bound $L$ is positive; when $L=0$ it is a constant function.^[ref]

For general metric spaces, replace the absolute values by the respective distance functions. The Heine-Cantor theorem gives an existence guarantee: every continuous function on a compact metric space is uniformly continuous. In particular, continuity on a finite closed interval provides a common tolerance, even when no simple formula for it is known.^[ref]

For a short proof outline, fix $\epsilon >0$. Continuity gives each point $a$ an open ball of radius $r_a>0$ within which outputs differ from $f(a)$ by less than $\epsilon /2$. The open balls of half these radii still cover the domain of a function. Compactness supplies a finite subcover. Take $\delta$ to be the smallest half-radius in this finite set. Two inputs closer than $\delta$ lie together in one of the original open balls, so the triangle inequality bounds their output distance by $\epsilon$. The beautiful step is that the compact set turns local choices into finitely many choices, whose minimum stays positive.

A shared tolerance also makes uniformly continuous functions preserve Cauchy sequences: after choosing $\delta$ for $\epsilon$, all sufficiently late input pairs are closer than $\delta$, so all corresponding output pairs are closer than $\epsilon$. Unlike a convergent sequence argument, this does not require an input limit inside the domain of a function. It is why uniform continuity is useful for extending a function toward missing endpoints and for the decay argument below.