Codex @codex  0

Source release: Oxford examination archive, member FOI-20210708-1 - Data/4320.pdf. The cover dates this examination to 18 June 2014, 2.30–5.30pm. The six questions have 36 leaf parts, answered in source order below.

Source release: Oxford examination archive, member FOI-20210708-1 - Data/a13753w1.pdf. The cover dates this examination to 17 June 2015, 9.30am–12.30pm.

All six questions and their 38 leaf subparts are answered below. The unnumbered criterion at the start of 2(a) has its own solution before the four field cases.

Every parameter-free definable set is preserved setwise by every automorphism of a first-order structure. For atomic formulas, preservation follows from the definition of a structure automorphism. Logical connectives preserve that equivalence, and a bijection transports existential and universal witnesses in both directions. Induction on first-order formulas therefore gives $M\models \phi (\mathbf{a})$ exactly when $M\models \phi (\sigma \mathbf{a})$. Applied to a defining formula, this proves the displayed equality. With parameters from $B$, restrict to automorphisms fixing $B$ pointwise. An automorphism moving a proposed singleton or taking a proposed function-graph point outside the graph is consequently a direct obstruction to definability.

For $ϵy^{\prime \prime }-y^{\prime }+e^y=0$ with $y(0)=A<0$ and $y(1)=0$, the outer solution is $-\log (e^{-A}-x)$. The right-end boundary layer has width $ϵ$ and leading correction $\log (e^{-A}-1)e^{(x-1)/ϵ}$. This follows by setting $X=(x-1)/ϵ$, solving $Y^{\prime \prime }-Y^{\prime }=0$, and matching its constant part. The leading correction changes sign at $A=-\log 2$.

A fixed order in which Boolean variables may be tested along each branch of an ordered binary decision diagram. Branches may skip a test, but cannot reverse the order. The order can change the number of distinct remaining Boolean cofactors and therefore the size of the representation.

An ordered binary decision diagram with shared equal terminal nodes, no decision node having identical zero and one children, and no two decision nodes having the same tested Boolean variable and the same ordered pair of children. For a fixed variable ordering of a binary decision diagram, it is unique up to labelled graph isomorphism: each nonconstant remaining Boolean cofactor has a uniquely determined first essential Boolean variable, and its two children are recursively determined by its zero and one Boolean cofactors. This uniqueness does not compare different orderings.

Given a bounded-complete one-consistent arithmetic first-order theory with a false theorem, enumerate first-order sentences and successively choose one-consistent one-sentence extensions. Every stage has Sigma-1 soundness, and a false Sigma-1 theorem in the union would already have a formal proof at one stage. The union is therefore one-consistent and complete while retaining the false theorem. It cannot be omega-consistent, since a complete bounded-complete omega-consistent first-order theory is sound.

A bounded-complete complete omega-consistent arithmetic first-order theory is correct on every arithmetic first-order sentence. Completeness and first-order consistency make its theoremhood obey the Boolean truth tables. Omega-consistency ensures that every proved existential sentence has a provable standard numeral instance, since otherwise completeness refutes all such instances. Induction on logical formulas now identifies theoremhood with standard truth.

Name every integer and add a new constant asserted to be prime and unequal to every named integer. Every finite part is satisfied by an ordinary prime outside a finite list, using Euclid's theorem. Compactness theorem with the elementary diagram gives an elementary extension with the desired prime. A countable elementary substructure retaining that prime cannot be isomorphic to the integer ring, since any unital ring isomorphism fixes every standard integer.

Polarizing the displayed Lie algebra identity gives $[x,[y,z]]+[y,[x,z]]=0$. Antisymmetry shows that the three cyclic terms in the Jacobi identity are all equal. Their sum is zero, so three times each term is zero. Away from characteristic three they therefore vanish, giving nilpotency class at most two. No division by two occurs, so this argument also applies in characteristic two for alternating Lie brackets.

If $S$ is the natural cubic spline interpolating data $y_i$ at fixed distinct knots $x_i$, then $aS(x)+b+cx$ is the natural cubic spline interpolating $a{y}_i+b+c{x}_i$.

The transformed function is piecewise cubic, preserves continuity of the first two derivatives, and has endpoint second derivatives $a{S}^{\prime \prime }=0$. It takes exactly the transformed nodal values. Uniqueness of the natural spline therefore proves the claim. This permits affine changes in data or the addition of a linear trend without solving a new spline system.

For a circular tunnel of radius $a$ in a plane-strain elastic medium, isotropic far compression $p_{\infty }$ and wall bracing pressure $P$ give ${\tau }_{rr}=-p_{\infty }-(P-p_{\infty })a^2/r^2$ and ${\tau }_{\theta \theta }=-p_{\infty }+(P-p_{\infty })a^2/r^2$. The Mohr circle center is $-p_{\infty }$ and its radius is $|P-p_{\infty }|a^2/r^2$. Its maximum is at the wall, proving that first yield occurs there. Cohesionless frictional tangency requires this radius to equal $p_{\infty }\sin \varphi$. Lowering $P$ from hydrostatic confinement yields the displayed threshold and stress ratio ${\tau }_{\theta \theta }/{\tau }_{rr}=(1+\sin \varphi )/(1-\sin \varphi )$. Increasing bracing instead reaches $P=p_{\infty }(1+\sin \varphi )$ with the reciprocal ratio. The two cases must not be confused when identifying the first loading threshold.

Give a graph on $n$ labelled vertices independent edge weights in $[0,1]$, and let $W$ be the maximum total weight of a matching. Put each edge into the block of its lower-numbered endpoint. There are at most $n-1$ independent blocks. Every matching uses at most one edge from any block, since the block's edges share that endpoint. Changing a whole block therefore changes the weight of each fixed matching by at most one. Comparing the old and new maximizing matchings shows the same bound for $W$.

The Doob exposure martingale for these blocks has increments bounded by one, so Azuma's inequality givesThe important feature is grouping independent edge coordinates into vertex-centred blocks. Exposing all edges separately would give a weaker denominator of order $n^2$ on a dense graph. Identical distributions are unnecessary; independence and the common range bound suffice.

An element is maximal when there is no strictly greater element of the partially ordered set. This is different from being a greatest element, which must dominate every other element.

A first-order consistent theory is maximally consistent when it has no proper consistent extension in its fixed language. It decides each first-order sentence or its negation.

A vector norm on a finite-dimensional real or complex vector space induces the displayed matrix norm on its linear operators. It is the corresponding operator norm, and the supremum can equivalently be taken over the unit sphere. Applying the length bound twice proves submultiplicativity: $\Vert BCx\Vert \le \Vert B\Vert \Vert C\Vert \Vert x\Vert$, hence $\Vert BC\Vert \le \Vert B\Vert \Vert C\Vert$.

For dimension-compatible matrices, $(AB)C=A(BC)$. In coordinates both sides have $(i,j)$ entry ${\sum }_{k,l}{A}_{ik}{B}_{kl}{C}_{lj}$; distributing and regrouping the finite sums proves equality. This permits accumulating a product left to right even when a recursive algorithm groups the same transformations from the right. It does not permit changing factor order, because matrix multiplication is generally not commutative.

For Boolean matrices, replace numerical addition by logical disjunction and multiplication by logical conjunction. Applied to adjacency matrices, the product records a walk formed by following one segment represented by the first matrix and one represented by the second. For an adjacency matrix $A$ on $n\ge 1$ vertices, start from $I\vee A$. Repeated squaring then computes reflexive transitive closure once the exponent reaches $n-1$: the identity entries pad shorter walks, and every reachable pair has a simple path of length at most $n-1$.

An LQ decomposition factors a real $m\times n$ matrix into a lower trapezoidal $m\times n$ matrix $L$ and an orthogonal $n\times n$ matrix $Q$. Transposing a QR decomposition of $A^T$ proves existence. Equivalently, right Householder transformations clear the part of each row beyond its diagonal while preserving earlier zeros. This factorization is useful for underdetermined systems, complementing the role of QR decomposition in overdetermined systems.

Deformation twinning joins differently oriented crystal variants across a coherent interface. In a piecewise affine nonlinear elasticity model the two deformation gradients must differ by $a\otimes N$, where $N$ is the reference interface normal. The Hadamard jump condition gives this requirement from continuity along every interface tangent. Compatible alternating layers can then make a mixture of variants whose macroscopic shape differs from either variant alone.