Past exam of the mathematics course of the University of Cambridge / 2006 / ii / Paper 3

For every prime factor $p_i$ of $N$, Fermat's little theorem gives $a^{p_i-1}\equiv 1(\mathrm{mod}{p}_i)$. Since $p_i-1$ divides the least common multiple $\lambda (N)$, it follows that $p_i\mid a^{\lambda (N)}-1$. The primes are distinct and hence pairwise coprime, so their product divides this integer. ThusFor the specified product, $N=1729$ and $\lambda (N)=\mathrm{lcm}(6,12,18)=36$. Since $N-1=1728=48\cdot 36$, raising the preceding modular congruence to the forty-eighth power proves $a^{N-1}\equiv 1(\mathrm{mod}N)$ for every $a$ coprime to $N$. This is the defining phenomenon of a Carmichael number.

Introduce $p_{-1}=1$, $q_{-1}=0$, $p_0=a_0$ and $q_0=1$. Composition of the Möbius transformations $z\mapsto a_j+1/z$ represents a finite continued fraction. Their matrices giveIndeed, multiplying the last factor gives the linear recurrences $p_n=a_n{p}_{n-1}+p_{n-2}$ and $q_n=a_n{q}_{n-1}+q_{n-2}$, which reproduce the continued fraction convergents of the continued fraction. Each factor has determinant $-1$. Taking determinants therefore yieldsThis identity also proves that the numerator and denominator in the first column are coprime, so no unnoticed cancellation changes the displayed matrix.

Extend the Möbius transformations to isometries of three-dimensional hyperbolic space. For any interior point $o$, the limit set of a Kleinian group is the set of boundary accumulation points of $Go$. Its definition is independent of $o$: two interior orbits stay at a bounded hyperbolic distance, so have the same boundary limits. The Kleinian limit set is closed and $G$-invariant. Iterating a loxodromic Möbius transformation in the positive and negative directions shows that its two fixed points belong to the Kleinian limit set.

The two fixed-point sets in this problem cannot have exactly one common point. Otherwise conjugate that point to infinity and the other fixed point of the first transformation to zero. The transformations then have the forms $f(z)=\alpha z$, with $|\alpha |>1$, and $g(z)=\beta z+b$, with $b\ne 0$. But $f^{-n}g{f}^n(z)=\beta z+b{\alpha }^{-n}$ is a sequence of distinct group elements converging in the Möbius group. Taking quotients of consecutive elements gives nonidentity elements converging to the identity, contrary to discrete subgroup. Consequently the Kleinian limit set contains at least three points.

Let $\xi$ be any point of the Kleinian limit set, and choose distinct $g_n$ with $g_{n}o\to \xi$. The rank-one convergence of divergent Möbius transformations supplies a subsequence converging to $\xi$ uniformly away from one exceptional boundary point $\eta$. To see the lemma directly, normalize determinant-one representing matrices by their norms. The norms tend to infinity, and a subsequential limit has rank one: its kernel is $\eta$ and its image is the attracting point. In the positive-Hermitian-matrix model of hyperbolic space, $g_{n}o$ has this same image limit, so the attracting point is indeed $\xi$.

Choose distinct ${\zeta }_1,{\zeta }_2$ in the Kleinian limit set other than $\eta$. Then $g_n{\zeta }_1$ and $g_n{\zeta }_2$ both tend to $\xi$, belong to the Kleinian limit set, and remain distinct because $g_n$ is injective. If $\xi$ were isolated, both would eventually equal $\xi$, an impossibility. The limit set has no isolated points.

A binary block code is a subset $C\subseteq \{0,1{\}}^n$; its length is the common word length $n$, its size is $m=|C|$, and its minimum distance is the least Hamming distance between distinct words. There are $V(n,r)={\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ words in a radius-$r$ Hamming ball, since one chooses the positions to change.

Put $t=\lfloor (d-1)/2\rfloor$. Two radius-$t$ Hamming balls about different codewords cannot meet: otherwise the triangle inequality would make their centres at distance at most $2t<d$. Comparing their combined size with $2^n$ gives the Hamming boundFor the other direction, start with one word and repeatedly add any word at distance at least $d$ from every word already selected. Finiteness ensures that this process stops. At that point the radius-$(d-1)$ Hamming balls cover the entire cube; an uncovered word could otherwise be added. These balls may overlap, but their total size is at least $2^n$. This gives the Gilbert–Varshamov bound

In a generalized linear model, the linear predictor is ${\eta }_i=x_i^T\beta$, a linear combination of the covariates with unknown coefficients. The link function relates this predictor to the mean: $g({\mu }_i)={\eta }_i$. The canonical link function chooses the natural parameter of the exponential family, namely $g(\mu )=\theta (\mu )$. Differentiating the normalization of the density shows that $\mu =K^{\prime }(\theta )$, so the canonical link function is $(K^{\prime }{)}^{-1}$ on the admissible parameter interval.

For a Bernoulli distribution, the probability mass function can be written asThus $\theta =\log (\mu /(1-\mu ))$ and $K(\theta )=\log (1+e^{\theta })$. The canonical link is the logit:

The infection term $rIS$ is a mass-action contact rate: each infection removes one susceptible individual and adds one infected individual. Recovery at rate $aI$ transfers individuals from the infected class to the recovered class. Loss of immunity at rate $pR$ transfers recovered individuals back to the susceptible class. Thus these equations describe the SIR model with waning immunity, also called the SIRS model. Adding the equations gives $\dot{S}+\dot{I}+\dot{R}=0$, so $S+I+R=N$. The nonnegative population region is invariant because the derivative of any population on its zero boundary is nonnegative.

Since $S\le N$, the infected population satisfies $\dot{I}=(rS-a)I\le (rN-a)I$. Integration gives $I(t)\le I(0)e^{(rN-a)t}$. Hence $rN<a$ forces the infected population to decrease exponentially from the outset: there is no epidemic outbreak.

For $rN>a$ and $p>0$, a nonzero infected equilibrium requires $S_{\ast }=a/r$. Using $a{I}_{\ast }=p{R}_{\ast }$ and population conservation givesEliminate $R=N-S-I$ before assessing stability, since perturbations must preserve the total population. The resulting Jacobian matrix at this endemic equilibrium isIts trace is negative and its determinant positive, so both eigenvalues have negative real part: the endemic equilibrium is locally asymptotically stable on the fixed-population plane. The full three-variable system has a neutral direction corresponding to changing the conserved population.

Writing $\kappa =rN-a>0$, as $p\to 0$ the trace is $-prN/a+O(p^2)$ and the determinant is $p\kappa$. Hence the discriminant $(\mathrm{tr}J{)}^2-4\det J=-4p\kappa +O(p^2)<0$. As $p\to \infty$, the trace is $-p-\kappa +O(p^{-1})$ and the determinant is again $p\kappa$, giving a positive discriminant $p^2+O(p)$. Both quantities are $O(p)$ in both limits, but the eigenvalues are complex for sufficiently small $p$ and real for sufficiently large $p$.

Representative normal forms are $\dot{x}=\mu +x^2$ for a saddle-node bifurcation, $\dot{x}=\mu x-x^2$ for a transcritical bifurcation, and $\dot{x}=\mu x-x^3$ for a supercritical pitchfork bifurcation. Replacing the last cubic term by $+x^3$ gives the subcritical pitchfork bifurcation.

Treat $\mu$ as a variable with $\dot{\mu }=0$. The extended center manifold is tangent to $y=0$, so write $y=h(x,\mu )=A{x}^2+Bx\mu +C{\mu }^2+O((|x|+|\mu |{)}^3)$. Its invariance equation is $h_x\dot{x}=\dot{y}$. At quadratic order this readsMatching coefficients gives $A=2$, $B=-4$, $C=4$. Substitution into the first equation therefore givesHere $O(3)$ denotes total degree at least three in $(x,\mu )$. With $T=t$, $X=x-2\mu$ and $\tilde{\mu }=\mu$, this becomes $dX/dT=\tilde{\mu }+X^2+O(3)$. Thus $\alpha =1$, $\beta =2$, $\gamma (\mu )=\mu$, and the bifurcation is a saddle-node. For negative parameter, the negative-$X$ branch is stable and the positive-$X$ branch unstable along the center manifold; the transverse eigenvalue is near $-1$.

For real $b\ne 0$, the integrand depends only on $b^2$, so first take $b>0$. Integrate $e^{iz}/(z^2-b^2)$ over the upper-half-plane semicircle, indenting above both real poles with small clockwise semicircles. The large arc tends to zero by Jordan lemma. Each indentation contributes $-i\pi$ times its residue, and there are no enclosed poles. Thus the Cauchy principal value on the whole real axis isThe imaginary part is odd and the real part even. Taking the real part and halving givesThe right-hand side is even in $b$, completing the negative-$b$ case as well.

The bob has $\dot{x}=\ell \cos \theta \dot{\theta }$ and $\dot{y}=at-\ell \sin \theta \dot{\theta }$. Substituting these into the Lagrangian givesThe mixed term is $\frac{d}{dt}(ma\ell t\cos \theta )-ma\ell \cos \theta$. Removing this total derivative and the time-only term leaves the equivalent Lagrangian $L_{\mathrm{eff}}=\frac{1}{2}m{\ell }^2{\dot{\theta }}^2+m(g-a)\ell \cos \theta$. The Euler-Lagrange equation becomesIn free fall, $a=g$, so $\theta ={\theta }_0+{\omega }_{0}t$: a bob initially at rest relative to the lift remains at its initial angle, and otherwise moves around the pivot with constant angular speed. Every constant angle is then an equilibrium, with no restoring force. For $a\ne g$, the equilibria are $\theta =0$ and $\theta =\pi$ modulo $2\pi$.

Near $\theta =0$, the linearized equation is $\ddot{\theta }+(g-a)\theta /\ell =0$. When $a<g$ this is an harmonic oscillator, so the downward configuration is stable. Writing $\theta =\pi +\epsilon$ instead gives $\ddot{\epsilon }-(g-a)\epsilon /\ell =0$, with an exponentially growing solution. Downward is stable; upward is unstable.

When $a>g$, the signs reverse. The downward configuration has an exponentially growing disturbance, whereas near $\theta =\pi$ one obtains $\ddot{\epsilon }+(a-g)\epsilon /\ell =0$. Upward is stable; downward is unstable. The effective gravity in the descending lift points upward in this case.

A thin spherical shell has mass $4\pi r^2\rho dr$ and inward gravitational force $Gm(r)(4\pi r^2\rho dr)/r^2$. The net outward pressure force is $-4\pi r^2{P}^{\prime }(r)dr$. Their balance gives the hydrostatic equilibrium equationSince $m^{\prime }=4\pi r^2\rho$, multiplying by $r^2/\rho$ and differentiating yields $\frac{d}{dr}(r^2{P}^{\prime }/\rho )=-4\pi G{r}^2\rho$.

At the centre, require $m(0)=0$ and finite $P(0)$ and $\rho (0)$. Spherical symmetry gives $P^{\prime }(0)=0$; indeed $m(r)=O(r^3)$ makes the pressure gradient $O(r)$ for regular density. At the surface require $P(R)=P_{\mathrm{ext}}$, usually approximated by zero, because pressure matches the surrounding medium. If the stellar mass is prescribed, also impose $m(R)=M$. An equation of state is needed to close the system. A vanishing surface density is appropriate for some stellar models but is not a universal boundary condition.

After its giant phases, the Sun ejects much of its envelope and leaves a carbon–oxygen white dwarf. The remnant mass lies below the Chandrasekhar limit. Its support is chiefly electron degeneracy pressure: the Pauli exclusion principle forces electrons into distinct momentum states even at low temperature, giving $P\propto {\rho }^{5/3}$ when they are nonrelativistic. Consequently pressure support need not cease when nuclear burning ends. The white dwarf subsequently cools and fades.

The process called inverse beta decay here is electron capture, $e^{-}+p\to n+{\nu }_e$, becomes possible for free particles when the electron's total energy exceeds approximately $(m_n-m_p)c^2\simeq 2.6m_e{c}^2$, corresponding to a kinetic energy about $1.6m_e{c}^2$. Electron capture on nuclei has thresholds modified by nuclear binding energies. In a solar-mass progenitor's ordinary white dwarf remnant, the Fermi energy is below the relevant capture thresholds, so the electron population providing support is stable. At much higher density, electron capture can reduce the electron density and pressure and promote collapse; this is why stability against electron capture matters in assessing degeneracy support. The Sun ends as a cooling white dwarf, rather than a neutron star.

The Prime number theorem states that $\pi (x)\sim x/\log x$, where $\pi (x)$ counts primes not exceeding $x$. Dirichlet theorem on primes in arithmetic progressions states that if $\gcd (a,m)=1$, then the progression $a+jm$ contains infinitely many primes.

If $x^2\equiv -1(\mathrm{mod}p)$ for an odd prime $p$, the multiplicative order of $x$ modulo $p$ is four. Lagrange's theorem therefore gives $4\mid p-1$. Conversely, Wilson's theorem gives $(p-1)!\equiv -1(\mathrm{mod}p)$. Pairing the factors $j$ and $p-j$ yieldsFor $p\equiv 1(\mathrm{mod}4)$, the sign is positive, so the factorial supplies a square root of $-1$. Thus $-1$ is a quadratic residue exactly when $p\equiv 1(\mathrm{mod}4)$.

Write $P={\prod }_j{p}_j$. The odd integer $4P-1$ is $3$ modulo $4$. If all of its prime factors were $1$ modulo $4$, their product, with multiplicities, would be $1$ modulo $4$, so at least one factor is $3$ modulo $4$. Every prime factor $q$ of $4P^2+1$ is odd and satisfies $(2P{)}^2\equiv -1(\mathrm{mod}q)$; the criterion just proved gives $q\equiv 1(\mathrm{mod}4)$. Neither integer is divisible by any $p_j$, since their residues modulo $p_j$ are respectively $-1$ and $1$. Starting with any finite list thus produces a new prime in each residue class. Both classes contain infinitely many primes, independently of the general Dirichlet theorem on primes in arithmetic progressions.

In the RSA cryptosystem, choose distinct large primes $p,q$, put $N=pq$, choose $e$ coprime to $\phi (N)=(p-1)(q-1)$, and choose $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. Publish $(N,e)$ and keep the factorization and $d$ private. Encrypt a properly encoded message $M$ as $C=M^e\mathrm{mod}N$ and decrypt as $M=C^d\mathrm{mod}N$. The Chinese remainder theorem proves correctness even for nonunits: modulo either prime, the message is either zero or satisfies Fermat's little theorem.

The public exponent $65537=2^{16}+1$ has few nonzero binary digits, so exponentiation needs only sixteen squarings and one extra multiplication. It is an efficient conventional choice, subject to the required coprimality and secure randomized message encoding. The same numerical choice for the private exponent would speed decryption, but for large moduli with balanced prime factors it is disastrously small: the continued-fraction attack on a small RSA private exponent recovers $d$ when, for example, $d<\frac{1}{3}{N}^{1/4}$ and $q<p<2q$. A small public exponent and a small private exponent have very different security implications.

To factor $N$ from $e,d$, write $ed-1=2^{s}t$ with $t$ odd. Choose random $a$ modulo $N$. If $\gcd (a,N)$ is nontrivial, factoring is already done. Otherwise compute $b=a^t$ and repeatedly square; the final value is one. If a value $x$ immediately preceding the first one is neither $1$ nor $-1$ modulo $N$, then $x^2\equiv 1(\mathrm{mod}N)$ andIndeed, the signs of $x$ modulo $p$ and $q$ differ. Restart if the chain begins at one or reaches $-1$ first. The Chinese remainder theorem makes the two prime components independent for a uniformly chosen unit. Their two-primary orders differ with probability at least one half: if the two exponents of two in $p-1,q-1$ are equal, the probability of equal orders is at most one half, and if unequal it is smaller. Since odd $t$ preserves these orders, this gives a randomized factoring procedure with bounded expected repetitions.

A bit commitment must be hiding before opening and binding after it. A concrete RSA construction uses a valid public RSA permutation whose inverse is unavailable to the receiver. Choose a random unit $x$ and a random bit vector $r$, and set $h(x,r)$ to their binary inner product modulo two. Send $y=x^e\mathrm{mod}N$, $r$, and $c=b\oplus h(x,r)$. To open, reveal $x$; the receiver checks $x^e=y$ and recovers $b=c\oplus h(x,r)$. Injectivity makes the opening bit unique. The hard-core predicate theorem applied to $(x,r)\mapsto (x^e,r)$ gives computational hiding under the RSA inversion assumption. The setup must ensure a valid modulus and exponent without giving the receiver the private exponent; otherwise hiding fails. Merely encrypting $0$ or $1$ would not hide a bit, since both ciphertexts could be computed publicly.

A homogeneous equilibrium has $v_0=u_0^2$. Besides $u_0=0$, a nonzero equilibrium satisfies $r=u_0^2-u_0$, giving $u_{\pm }=(1\pm \sqrt{1+4r})/2$. Concentrations are nonnegative, so only nonnegative roots are physically admissible. At a positive equilibrium, the reaction Jacobian matrix isNegative trace and positive determinant are equivalent toThus a positive homogeneous stable branch exists precisely when $s>1/2$ and $-1/4<r<s^2-s$, on the upper root $u_{+}$. The lower positive branch has negative determinant and is unstable. At $r=-1/4$ the branches meet and have a zero eigenvalue; at $u_0=s$ the strict linear stability condition also fails.

The trivial equilibrium $(0,0)$ has eigenvalues $r,-s$, so it is asymptotically stable for $r<0$. It exists for all $r$, independently of the nonzero branches. If negative $u_0$ were allowed mathematically, the negative branch for $r>0$ would also be homogeneously stable, but it does not represent a chemical concentration.

A Fourier mode with $q=k^2\ge 0$ evolves under $J-q\mathrm{diag}({\kappa }_1,{\kappa }_2)$. Its trace remains negative for a homogeneously stable positive branch. Its determinant isIf $u_0{\kappa }_2\le s{\kappa }_1$, this is positive for every $q\ge 0$. Otherwise its minimum is attained at $q_{\ast }=(u_0{\kappa }_2-s{\kappa }_1)/(2{\kappa }_1{\kappa }_2)$. Stability requires $D(q_{\ast })>0$, orIn terms of $d=\sqrt{{\kappa }_2/{\kappa }_1}$, the boundary is the positive root of $u_0{d}^2-s=2d\sqrt{s(2u_0^2-u_0)}$:Within $1/2<u_0<s$, all modes decay for $d<d_c$; a finite band grows for $d>d_c$, giving a Turing instability. Equality is neutral at one nonzero wavenumber.

For $s=2$, the positive lower branch $0<u_0<1/2$ is unstable for every $d$. The upper branch is homogeneously stable for $1/2<u_0<2$: it is stable to all modes to the left of $d_c=2+\sqrt{4-2/u_0}$ and unstable to spatial modes to the right. For $u_0>2$ it is already homogeneously unstable. The zero branch is stable to every spatial mode when $r<0$, because its mode eigenvalues are $r-{\kappa }_1{k}^2$ and $-s-{\kappa }_2{k}^2$.

At onset the determinant has a double root, soSquaring the neutral-boundary equation and canceling the positive factors gives $u_0=s/[d(2\sqrt{2s}-d)]$. Substitution yieldsFor a positive branch with $u_0>1/2$, the actual neutral curve lies strictly between $\sqrt{2s}$ and $2\sqrt{2s}$. If $d<\sqrt{2s}$, then $d<d_c(u_0)$ for every such branch: a homogeneously stable state cannot have this Turing instability. If $d>2\sqrt{2s}$, then $d>d_c(u_0)$ for every finite positive $u_0$, so every homogeneously stable positive state is spatially unstable. The negative value yielded by the displayed formula outside its boundary domain is not a physical critical wavenumber and does not imply renewed stability. One must also keep $u_0<s$, which can restrict the attainable neutral curve further.

Write the Papperitz symbol by listing pairs of exponents at $0,1,\infty$. For $F(a,c-b;c;w)$ they are $(0,1-c)$, $(0,b-a)$, and $(a,c-b)$. Under $w=z/(z-1)$ the points $0,1,\infty$ in the $z$-plane correspond respectively to $0,\infty ,1$ in the $w$-plane. Thus the pulled-back exponents are $(0,1-c)$ at zero, $(a,c-b)$ at one, and $(0,b-a)$ at infinity.

Multiplication by $(1-z{)}^{-a}$ shifts the exponents at one by $-a$ and those at infinity by $+a$, yieldingThis is the original Gauss hypergeometric equation. Both functions are analytic and normalized to one at zero, so uniqueness of that normalized local solution proves the Pfaff transformationContinue the identity using the branch $|\arg (1-z)|<\pi$. As usual, the parameters must admit the normalized hypergeometric solution; excluded singular parameter values are treated only when their limiting solution exists.

For $F(a,1+a-c;1+a-b;w)$, the exponents at $w=0,1,\infty$ are $(0,b-a)$, $(0,c-a-b)$, and $(a,1+a-c)$. The substitution $w=1/z$ exchanges zero and infinity, giving $(a,1+a-c)$ at $z=0$, $(0,c-a-b)$ at one, and $(0,b-a)$ at infinity. Multiplication by $(-z{)}^{-a}$ shifts the zero exponents by $-a$ and the infinity exponents by $+a$. The resulting Papperitz symbol is again $(0,1-c)$, $(0,c-a-b)$, $(a,b)$. Therefore $w_1$ satisfies the same hypergeometric equation, with the stated branch $|\arg (-z)|<\pi$.

First assume $a-b\notin \mathbb{Z}$ and nonsingular parameters, so the two infinity solutions $w_1$ and $w_2$, obtained by exchanging $a,b$, are independent. Write $F=A{w}_1+B{w}_2$. Since the power series at $1/z=0$ starts at one, $w_1\sim (-z{)}^{-a}$ and $w_2\sim (-z{)}^{-b}$.

In the parameter region $\Re (b-a)>0$, let $z\to -\infty$ in the Pfaff transformation. The $w_2$ term vanishes after multiplication by $(-z{)}^a$, while $z/(z-1)\to 1$ and $(-z)/(1-z)\to 1$. The supplied value at one of the Gauss hypergeometric function therefore givesAnalytic continuation in the parameters extends this coefficient to the nonresonant parameter domain. Exchange $a,b$ to determine $B$. Hence the hypergeometric connection formula at infinity isThe branch is $|\arg (-z)|<\pi$. The existence of $F(a,b;c;1)$ alone does not exclude integer $a-b$. At such resonant values the two separate displayed terms can be singular; the correct statement takes their combined parameter limit, which can contain logarithms. This qualification is essential, for example when $a=b$.

The azimuthal coordinate is cyclic, so its canonical momentum is conserved. Time independence of the Lagrangian also conserves the energy. The two constants areFor a horizontal launch from depth $D$, take $0<D<\ell$, so $\cos {\theta }_0=D/\ell$, ${\dot{\theta }}_0=0$, and $v=\ell \sin {\theta }_0{\dot{\varphi }}_0$. Thus $h=mv\sqrt{{\ell }^2-D^2}$ and $E=\frac{1}{2}m{v}^2-mgD$. The meridional motion has effective potential $U(\theta )=h^2/(2m{\ell }^2{\sin }^2\theta )-mg\ell \cos \theta$.

Grazing the equator makes it a turning point, so $\dot{\theta }=0$ at $\theta =\pi /2$. Conservation of energy gives $\frac{1}{2}m{v}^2-mgD=h^2/(2m{\ell }^2)=\frac{1}{2}m{v}^2(1-D^2/{\ell }^2)$. ThereforeTo check that no earlier turning point prevents reaching the equator, put $c=\cos \theta$. On $0\le c\le D/\ell$, $U(c)=h^2/[2m{\ell }^2(1-c^2)]-mg\ell c$ is strictly convex. Its two endpoint values are equal for this speed, so its interior values are smaller. The trajectory can therefore move between the launch point and the equator. The equator is genuinely a turning point since $dU/d\theta =mg\ell$ there.

For fixed $\theta$, the Euler-Lagrange equation for the meridional coordinate requires ${\dot{\varphi }}^2\cos \theta =g/\ell$. Combining this with $v=\ell \sin \theta \dot{\varphi }$ and $\cos \theta =D/\ell$ givesThe resulting motion is a conical pendulum. The positive-depth condition is necessary for a nondegenerate constant-latitude orbit in gravity; the bottom point is the limiting zero-speed equilibrium.

A first-order structure consists of a nonempty domain, an interpretation of each constant as a domain element, each $k$-ary function symbol as a map from the $k$-fold domain product to the domain, and each $k$-ary relation symbol as a subset of that product. Under an assignment of values to variables, terms are evaluated recursively. Atomic formulas assert equality of term values or membership in an interpreted relation. Boolean connectives act on truth values, and quantifiers range over the whole domain. The set $[[\phi ]{]}_A$ consists of assignments to the free variables making the formula true.

For a substructure $B\subseteq A$, constants lie in $B$, functions restrict to $B$, and relations restrict to tuples from $B$. Induction on terms shows that every term with arguments from $B$ has the same value in both structures. Atomic formulas consequently have the same truth values, and induction on Boolean connectives givesfor every quantifier-free formula.

For a nonempty chain of $T$-model substructures, form their union $U$. Every finite tuple belongs to one member of the chain, so $U$ is closed under all interpreted functions and contains the constants. Consider any inductive axiom $\forall x\exists y\psi (x,y)$. A specified finite tuple $x$ lies in one member, which supplies witnesses $y$ there. The quantifier-free formula $\psi$ has the same truth value in that member and $U$, so $U$ satisfies the axiom. Hence $U$ is a $T$-model and the least upper bound of the chain. The poset is complete for nonempty chains. If chain-complete is defined to include the empty chain, a least element must additionally exist, which the stated hypotheses do not ensure.

The reflexivity, antisymmetry, transitivity and totality axioms for a total order are universal with quantifier-free formula matrices, and hence inductive with an empty existential block. Add $\forall x\exists y(y<x)$ and $\forall x\exists z(x<z)$, with strict inequalities expressed using $\le$ and inequality. These exclude least and greatest elements. This theory is inductive.

For each positive integer $n$, the finite ordered interval $[-n,n]\cap \mathbb{Z}$ has a greatest and a least element, and these intervals form a chain of substructures. Their union is $\mathbb{Z}$, which has neither. An inductive first-order theory must be preserved by such unions, as proved above. The theory with both endpoints cannot be axiomatized inductively, even though it has an ordinary first-order axiomatization with existential–universal endpoint sentences.

Define the asymmetric Ramsey number $R(s,t)$ for a red $K_s$ or a blue $K_t$. The base cases $R(1,t)=R(s,1)=1$ are finite. If $n=R(s-1,t)+R(s,t-1)$, choose a vertex of $K_n$. Its red neighbors number at least $R(s-1,t)$, or its blue neighbors number at least $R(s,t-1)$. Apply the appropriate smaller Ramsey number inside that neighborhood: either the opposite-color clique already exists, or a same-color clique extends by the chosen vertex. Thus $R(s,t)\le R(s-1,t)+R(s,t-1)$, proving finiteness by induction, in particular for $R(s)=R(s,s)$.

In a graph of maximum degree $d\ge 2$, a ball of radius $k-1$ about a vertex has at most ${\sum }_{j=0}^{k-1}{d}^j=(d^k-1)/(d-1)<d^k$ vertices. Hence a connected graph of order $d^k$ has a vertex outside this ball, at distance at least $k$. The argument also applies whenever the graph has at least $d^k$ vertices.

Now take a connected graph of order $R(s{)}^s$. If some vertex has at least $R(s)$ neighbors, apply the two-color Ramsey theorem to their pairs, coloring an edge red and a nonedge blue. A red $K_s$ is an induced complete graph, while a blue $K_s$ is an independent set of $s$ neighbors, which with the centre induces $K_{1,s}$. Otherwise the maximum degree satisfies $d<R(s)$. For $s\ge 2$, connectedness and the vertex count rule out $d\le 1$. The ball bound then provides vertices at distance at least $s$. A shortest path between them has no chord, since a chord would shorten it; its first $s$ edges induce $P_s$. The case $s=1$ is immediate. Therefore

The polynomial $X^m-1$ is separable, since its derivative $m{X}^{m-1}$ has no common root with it when the characteristic does not divide $m$. Its roots form a cyclic multiplicative group of order $m$. For completeness, any finite subgroup of a field's multiplicative group is cyclic: if its exponent is $e$, all its elements are roots of $X^e-1$, so its size is at most $e$, while the elementary decomposition of a finite abelian group gives an element of order $e$.

Choose a primitive root $\zeta$. Then $L=K(\zeta )$, and every field automorphism sends $\zeta$ to ${\zeta }^a$ for a unique unit $a$ modulo $m$. Composition multiplies the exponents, and fixing $\zeta$ fixes all of $L$. This is the required injective homomorphismFor $K={\mathbb{F}}_q$, the least extension ${\mathbb{F}}_{q^d}$ containing a primitive $m$th root is characterized by $m\mid q^d-1$, since its multiplicative group is cyclic of order $q^d-1$. Thus $[L:K]$ is the multiplicative order of $q$ modulo $m$. The successive powers of $4$ modulo $11$ are $4,5,9,3,1$, so