Past exam of the mathematics course of the University of Cambridge / 2011 / ia / Paper 4

An inverse function of $f:X\to Y$ is a function $h:Y\to X$ satisfying bothThese are two-sided inverse identities. If $f(x)=f(x^{\prime })$, apply $h$ to get $x=x^{\prime }$, so $f$ is injective. For every $y\in Y$, the identity $f(h(y))=y$ supplies a preimage, so $f$ is surjective. Thus $f$ is a bijection.

Conversely, if $f$ is a bijection, each $y\in Y$ has exactly one preimage. Define $h(y)$ to be that preimage. Then $f(h(y))=y$ and $h(f(x))=x$, giving both identities. Hence a function has a two-sided inverse exactly when it is a bijection. This also makes its inverse function unique.

Always true. If $(f\circ g)(x)=(f\circ g)(x^{\prime })$, injectivity of $f$ gives $g(x)=g(x^{\prime })$, and injectivity of $g$ gives $x=x^{\prime }$. Thus the function composition is injective. For any $y\in X$, since $f$ is surjective, choose $z$ with $f(z)=y$. Since $g$ is surjective, choose $x$ with $g(x)=z$. Then $(f\circ g)(x)=y$, proving that the composition is surjective. Consequently $f\circ g$ is a bijection; its inverse function is $g^{-1}\circ f^{-1}$.

Can be false. Take $X=\{0,1,2,\dots \}$ and defineThen $(f\circ g)(n)=n$, so their function composition is the identity function and hence a bijection. However, $g$ is not surjective, since zero has no preimage, while $f$ is not injective, since $f(0)=f(1)=0$.

The valid implications are only that $g$ must be injective and $f$ must be surjective: equality of two $g$ values implies equality after composition, and every output of the composition is an output of $f$. On a finite $X$, either of these properties implies a bijection, so an infinite set is essential to this counterexample.

An equivalence relation is a binary relation that is simultaneously a reflexive relation, a symmetric relation and a transitive relation: $x\sim x$; $x\sim y$ implies $y\sim x$; and $x\sim y$, $y\sim z$ imply $x\sim z$. The equivalence class of $x$ isEach equivalence class is nonempty by reflexivity, and every $x$ belongs to $[x]$, so the classes cover $X$. If $z\in [x]\cap [y]$, then the symmetric relation and transitive relation properties give $x\sim z\sim y$. Every $w\in [x]$ therefore satisfies $w\sim x\sim y$, so $[x]\subseteq [y]$; the reverse inclusion follows similarly. Thus two classes are either identical or disjoint. The distinct equivalence classes consequently form a set partition of $X$.

The divisibility-comparability relation is a reflexive relation and a symmetric relation, but is not an equivalence relation. Indeed, $2\sim 6$ and $6\sim 3$, whereas neither $2\mid 3$ nor $3\mid 2$, so transitivity fails.

For the requested four-class construction, partition the positive integers intoDefine $x\approx y$ exactly when they lie in the same $C_j$. Equality of the class label is an equivalence relation. Its four classes are the two finite singletons and the two infinite parity classes displayed above.

In a short time $dt$, the radius vector sweeps an oriented area $d\mathcal{A}=\frac{1}{2}{r}^{2}d\theta$. ThusThe constant $h$ is twice the oriented areal velocity, or the angular momentum per unit mass. Its constancy is Kepler's second law: equal areas are swept in equal times.

For a circular orbit of radius $a$, set $\ddot{r}=0$ in the radial equation. The balance isHence a circular orbit exists for any $a>0$ with this nonzero $|h|$. Its period gives Kepler's third law:To check circular-orbit stability for a power-law central force directly, keep $h$ fixed and set $r=a+\rho$. Expandingabout the balanced radius givesThe linear radial perturbation therefore obeysIt remains bounded and oscillates, proving stability under the stipulated small perturbations. Equivalently, the specific effective potential $h^2/(2r^2)-GM/r$ has a strict minimum at $a$.

Write the standard Lorentz transformation as $x^{\prime }=\gamma (x-vt)$, $c{t}^{\prime }=\gamma (ct-vx/c)$, with Lorentz factor $\gamma =(1-v^2/c^2{)}^{-1/2}$ and $|v|<c$. In the null coordinates in two-dimensional Minkowski spacetime, addition and subtraction giveSince both factors are positive,Their product is one, so Lorentz invariance of the interval follows immediately:Two successive collinear Lorentz boosts multiply the positive-coordinate factor by $\lambda (v_2)\lambda (v_1)$ and the negative-coordinate factor by its reciprocal. Thus they have the same form with a velocity $v_3$ determined byCross multiplication yields the relativistic velocity-addition formula formulaFor $|v_1|,|v_2|<c$, the denominator is positive andso $v_3$ is admissible. The positive square roots then verify the factor identity itself, not merely its square. In terms of rapidity $v/c=\tanh \eta$, this same calculation is addition of rapidities because $\lambda (v)=e^{-\eta }$.

The greatest common divisor $d=\gcd (a,b)$ is the largest positive integer dividing both $a$ and $b$. To prove Bezout identity without assuming unique factorization, let $d_0$ be the least positive member ofThis set has positive members, for example $a$, so well-ordering principle supplies $d_0$. Divide $a$ by $d_0$ using Euclidean division: $a=q{d}_0+r$, $0\le r<d_0$. The remainder $r=a-q{d}_0$ is another integer linear combination of $a,b$. Minimality forces $r=0$, so $d_0\mid a$. The same argument gives $d_0\mid b$. Every common divisor divides every integer linear combination, hence divides $d_0$. Therefore $d_0$ is the greatest common divisor, andThis argument also proves that every common divisor divides the greatest common divisor.

The positive integers with the stated product-divisibility property areThe case $n=1$ is immediate. If $p$ is prime and $p\nmid a$, its only possible common positive divisor with $a$ is one. By Bezout identity, $\lambda p+\mu a=1$. Multiplying by $b$ shows that $p\mid ab$ implies $p\mid b$. This proves Euclid lemma directly. Conversely, if $n>1$ is not prime, it has a divisor $r$ with $1<r<n$. Put $s=n/r$; then $1<s<n$. Although $n\mid rs$, neither $r$ nor $s$ is divisible by $n$, disproving the property for a composite $n$.

Finally, suppose $ab=cd$ for four distinct primes. Then $a\mid cd$, so Euclid lemma gives $a\mid c$ or $a\mid d$. A prime has no positive divisor other than one and itself, so this would mean $a=c$ or $a=d$, a contradiction. Products of these two disjoint pairs cannot be equal. No form of the fundamental theorem of arithmetic was used: the required prime-divisibility fact was proved from Bezout identity.

Yes. A concrete example of nonunique factorization in a congruence submonoid isThe four factors are distinct and each is congruent to one modulo ten. The primes $3,7,13,17$ can be checked by trial division by two and three. Their elementary prime decompositions areFor any one of these products $pq$, where $p,q$ are the indicated distinct primes, its positive divisors are $1,p,q,pq$. This divisor assertion does not require unique factorization: if $d\mid pq$ and $p\nmid d$, then $p\mid pq/d$ by the Euclid lemma proved in (a), so $d\mid q$ and $d$ is either one or $q$. If $p\mid d$, write $d=pe$ and obtain $e\mid q$, giving $d=p$ or $pq$.

None of $3,7,13,17$ is congruent to one modulo ten. Consequently no listed product has a proper nonunit divisor in $S$. Thus each is an irreducible element of a commutative monoid, and the displayed equality proves the claim. Ordinary prime decompositions and irreducibility relative to the smaller commutative monoid $S$ are different notions.

Fermat's little theorem states that for a prime $p$ and an integer $a$,Wilson theorem states that for a prime $p$,All the following modular congruences are taken modulo the indicated prime.

Suppose $x^2\equiv -1(\mathrm{mod}p)$. Then $p\nmid x$, so Fermat's little theorem gives $x^{p-1}\equiv 1$. But $p\equiv 3(\mathrm{mod}4)$ makes $(p-1)/2$ odd, and henceSince this $p$ is odd, $1\not\equiv -1(\mathrm{mod}p)$, a contradiction. There is no square root of minus one in this case.

Set $m=(p-1)/2$. Pairing each of $1,\dots ,m$ with its negative residue givesHere $p\equiv 1(\mathrm{mod}4)$ makes $m$ even. By Wilson theorem,satisfies $x^2\equiv -1(\mathrm{mod}p)$. Its negative is the other root. This proves existence by an explicit factorial construction.

Write $p=3k+2$. A solution has $p\nmid x$, so Fermat's little theorem givesThus $x\equiv (-1{)}^k(\mathrm{mod}p)$. If $p$ is odd, then $k$ is odd and $x\equiv -1$. The remaining prime case $p=2$ has $k=0$ and $x\equiv 1\equiv -1(\mathrm{mod}2)$ as well. Since $-1$ itself always satisfies the equation, the unique solution is $x\equiv -1(\mathrm{mod}p)$.

Factor the equation asFor the nontrivial roots, the quadratic formula over residues givesThe supplied square root is $14$, and $2^{-1}\equiv 100(\mathrm{mod}199)$. ThereforeIndeed $107^2-107+1=11343=57\cdot 199$, so $107^3+1$ is divisible by $199$, and $107\not\equiv -1$. The other nontrivial root is $(1-14)100\equiv 93$; it satisfies $93^2-93+1=43\cdot 199$. Together with $198\equiv -1$, these are the three cube roots of minus one. The complex-number hint reflects the same quadratic factor: the two roots there are $(1\pm \sqrt{-3})/2$.

Define the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ to be the number of $i$-element subsets of an $n$-element set. Counting ordered selections and dividing by the $i!$ orders of each subset givesEvery subset has exactly one size, while each of the $n$ elements can independently be included or omitted. Hence the power set has $2^n$ members andTo prove the binomial theorem, expand the product of $n$ factors $(1+x)$. A term $x^i$ results from choosing $x$ from precisely an $i$-element subset of the factors and choosing one elsewhere. Its coefficient is therefore $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. This is a finite distributive expansion, valid for every real $x$, and givesDifferentiate this polynomial identity and set $x=1$:A second derivative gives $\sum i(i-1)\left(\genfrac{}{}{0ex}{}{n}{i}\right)=n(n-1)2^{n-2}$ for $n\ge 2$. Since $i^2=i(i-1)+i$, it follows thatThe formula also holds for $n=1$, when its value is one; that case can be checked directly without differentiating twice.

For the squared binomial coefficients, compare the coefficient of $x^n$ in $(1+x{)}^n(1+x{)}^n=(1+x{)}^{2n}$. On the left it is ${\sum }_i\left(\genfrac{}{}{0ex}{}{n}{i}\right)\left(\genfrac{}{}{0ex}{}{n}{n-i}\right)$, and the binomial coefficient symmetry gives $\left(\genfrac{}{}{0ex}{}{n}{n-i}\right)=\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. ThusFinally put $S={\sum }_{i}i{\left(\genfrac{}{}{0ex}{}{n}{i}\right)}^2$ and replace the index $i$ by $n-i$. The same symmetry gives $S={\sum }_i(n-i){\left(\genfrac{}{}{0ex}{}{n}{i}\right)}^2$. Adding the two expressions and using the preceding identity yields

For any function $f:X\to \mathcal{P}(X)$, form the diagonal subsetIf $f$ were surjective, some $d\in X$ would satisfy $f(d)=D$. Then $d\in D$ would hold exactly when $d\notin D$, which is impossible. Thus no set surjects onto its power set, including the empty-set case. This is Cantor's theorem proved by the Cantor diagonal argument.

Use real-number pairing by separated digits for an explicit injection ${\mathbb{R}}^2\to \mathbb{R}$. First map a real number to $(0,1)$ by $q(x)=\frac{1}{2}+{\pi }^{-1}\arctan x$, and use its unique binary expansion that is not eventually all ones. If $q(x)={\sum }_{n\ge 1}{a}_n{2}^{-n}$ and $q(y)={\sum }_{n\ge 1}{b}_n{2}^{-n}$, defineThis places the two binary digit strings in alternating ternary positions. Such ternary strings, using only digits zero and one, are unique: at a first differing position $k$, the difference $3^{-k}$ exceeds the maximum tail ${\sum }_{j>k}{3}^{-j}=\frac{1}{2}{3}^{-k}$. Thus the output recovers both digit strings and both inputs. The use of base three avoids any endpoint ambiguity caused by interleaving digits in base two.

For a fixed $A\subseteq {\mathbb{R}}^2$, the affine sections of a planar set are indexed byThere is an injection $\iota :\mathcal{I}\to \mathbb{R}$, for example by applying $J$ to each coordinate pair and then once more to those two results. Suppose every subset of $\mathbb{R}$ were a section of $A$. Define a function from $\mathbb{R}$ to $\mathcal{P}(\mathbb{R})$ by assigning to $\iota (\mathbf{a},\mathbf{b})$ the corresponding section, and assigning the empty set to every real outside $\iota (\mathcal{I})$. Injectivity of $\iota$ makes this definition unambiguous. It would be a surjection onto $\mathcal{P}(\mathbb{R})$, contradicting the first argument. No planar set has every subset of the real line as a section. Allowing different parametrizations of the same line does not evade this obstruction.

For all countable sets, however, such a planar set does exist. To build one, first encode every real sequence $s=(s_1,s_2,\dots )$ by one real number. Let $a_{nk}$ be the canonical binary digits of $q(s_n)$, and choose the explicit indexingThis is a bijection from positive integer pairs to positive integers. Define the coding of real sequences by ternary digitsThe same first-differing-digit argument proves that $c$ is injective; all its values lie in $[0,1/2]$. Now takeFor every nonempty countable set $S\subseteq \mathbb{R}$, choose an enumeration $s$ of $S$, repeating terms if $S$ is finite. On the vertical line with $\mathbf{a}=(c(s),0)$ and $\mathbf{b}=(0,1)$, the section of $A$ is precisely $S$: injective sequence coding means no other sequence can contribute extra values in this column. The empty set is the section on the line $x=2$, since all code columns have first coordinate at most $1/2$. This constructs the required universal planar set for countable real sections. No assertion about its other, nonvertical sections is needed.

Take the scalar product of Newton's second law with the velocity $\dot{\mathbf{r}}$. The cross product is perpendicular to its first factor, soConsequentlyThis is conservation of energy: the sum of kinetic energy and potential energy stays fixed. The magnetic-type Lorentz force $\dot{\mathbf{r}}\times \mathbf{B}$ does no work, because it is perpendicular to the instantaneous velocity. It may turn the trajectory but cannot directly change its speed, regardless of the spatial variation of $\mathbf{B}$.

For $\psi =\mu /r$, the radial gradient givesThe force $-\nabla \varphi$ is radial and has no torque about the origin. For the remaining force, use the vector triple product:Meanwhile the radial unit vector obeysSince $\psi \mathbf{r}=\mu \hat{\mathbf{r}}$, these derivatives cancel. Thus the generalized angular momentum in a radial monopole field isThe argument applies away from $r=0$, where the field is defined, for any radial $\varphi$. In contrast to ordinary angular momentum, this conserved vector has $\mathbf{L}\cdot \hat{\mathbf{r}}=-\mu$; it fixes a cone rather than generally fixing a plane.

With $\psi =0$, the angular momentum becomes $\mathbf{L}=m\mathbf{r}\times \dot{\mathbf{r}}$ and is constant. The identity $\mathbf{L}\cdot \mathbf{r}=0$ confines the trajectory to the plane through the origin perpendicular to $\mathbf{L}$ when $\mathbf{L}\ne 0$. If $\mathbf{L}=0$, the velocity is radial and a central force preserves the radial line; this degenerate motion is also planar.

For the proposed Laplace-Runge-Lenz vector convention, differentiate $\mathbf{K}=\mathbf{L}\times \dot{\mathbf{r}}-\varphi (r)\mathbf{r}$. Since $\ddot{\mathbf{r}}=-{\varphi }^{\prime }(r)\hat{\mathbf{r}}/m$ and $\mathbf{L}$ is constant, the vector triple product givesThereforeIt vanishes for general motion precisely when $(r\varphi {)}^{\prime }=0$, givingThis is an inverse-square potential, attractive when $C<0$ and repulsive when $C>0$; $C=0$ is the free-particle case. An additive constant in $\varphi$ leaves the force unchanged but would change this particular $\mathbf{K}$ by a constant multiple of $\mathbf{r}$, so its definition requires the displayed choice of energy zero.

Apply the rotating-frame derivative formula first to position and then to its inertial velocity:The angular velocity is constant, so there is no term involving $\dot{\mathbf{\omega }}$. By Newton's second law in the inertial frame, the inertial acceleration is $\mathbf{F}/m$. Rearrangement gives the equation of motion in a rotating frame:The two additional accelerations are the Coriolis acceleration and centrifugal acceleration.

At $P$, use the local right-handed basis ${\mathbf{e}}_E,{\mathbf{e}}_N,{\mathbf{e}}_U$ pointing east, north and vertically outward. The Earth's rotation vector has componentsInitially $\dot{\mathbf{r}}=0$ in the rotating reference frame, so the Coriolis acceleration is zero. Evaluating the centrifugal acceleration givesThe gravitational acceleration is $-g{\mathbf{e}}_U$. HenceThe small angle $\delta$ from the downward vertical therefore satisfiesFor the northern hemisphere, $0\le \theta \le \pi /2$, this is the printed expression without absolute values. More generally, the printed signed meridional expression specifies the direction of the tilt; an unsigned angle uses its absolute value. The horizontal component is toward the equator and vanishes at both poles and at the equator.

Neglect the centrifugal acceleration, which is of order ${\omega }^2$, and use the local flat-surface approximation. To zeroth order in $\omega$, the height above $P$ and flight time areInserting this vertical velocity into the Coriolis acceleration gives the eastward componentWith $x(0)=\dot{x}(0)=0$, two integrations yieldto first order. Horizontal velocity is already of order $\omega$, so its effect on vertical acceleration is of order ${\omega }^2$. Thus the flight time remains $T_0$ at this order. The Coriolis deflection of a vertical projectile at landing isThe displacement is westward, and its magnitude is $4\omega v^3\sin \theta /(3g^2)$. The horizontal speed remains westward during the flight: $\dot{x}=-2\omega \sin \theta z_0(t)$. This explains why the eastward acceleration on descent does not cancel the earlier displacement.

Let $dm$ be the gas mass ejected in a short interval, and let $dD$ be the stationary dust mass acquired. The rocket mass change is $dM=dD-dm$. Before the interval the momentum of the rocket and this dust is $Mv$, because the incoming dust is at rest. Afterwards it isto first order; changing the gas ejection speed by $dv$ affects only second-order terms. Momentum conservation, with no external force, therefore givesDividing by the time interval produces the rocket equation with stationary mass accretion:The incoming material's zero initial momentum is essential: accelerating it to the rocket's speed consumes part of the thrust.

Without dust collection, $dM=-dm$. The rocket equation reduces toIntegrating from $v=0$, $M=M_0$ givesThis is the usual rocket equation with constant relative exhaust speed, valid while the mass remains positive and the prescribed ejection continues.

Now $\dot{m}=\beta$ and $\dot{M}=\alpha -\beta$, soFor $\alpha >0$, set $w=u\beta -\alpha v$. Then $\dot{w}=-\alpha w/M$ and $w(0)=u\beta$. For $\alpha \ne \beta$, integration givesConsequentlyThis solution of the rocket equation with stationary mass accretion covers increasing or decreasing rocket mass, as long as $M>0$. For equal-rate rocket burning and accretion, in the case $\alpha =\beta >0$, the mass is constant and the linear equation instead givesIt is also the continuous equal-rate limit of the preceding expression when written in terms of $t$.

For the no-accretion limit, expand the power as an exponential:Substitution givesrecovering (a). At a fixed time with $M_0-\beta t>0$, the limiting mass is $M=M_0-\beta t$, so the same calculation recovers the time-dependent no-dust solution.

The relativistic energy of a particle of rest mass $m$ is $E=\gamma m{c}^2$, where the Lorentz factor is $\gamma =(1-v^2/c^2{)}^{-1/2}$. Using the binomial series at small $v/c$ givesThe second term is the familiar Newtonian kinetic energy. The first is the rest energy, which remains when $v=0$. Thus the new physical idea is mass-energy equivalence: a body's mass represents energy $m{c}^2$ even at rest. The total energy is not merely energy due to motion.

The incident four-momentum has energy $E$ and spatial momentum $p=\gamma mv$, while the stationary target has energy $m{c}^2$ and zero spatial momentum. By the relativistic energy-momentum relation, $c^2{p}^2=E^2-m^2{c}^4$. For the fixed-target threshold for production of equal-mass particles, the squared total centre-of-momentum energy isIn the centre-of-momentum frame, each of the final $N$ particles has energy at least its rest energy $m{c}^2$. Four-momentum conservation therefore requires $W\ge Nm{c}^2$, and thusFor the physically relevant $N\ge 2$, this is equivalent to $\gamma \ge (N^2-2)/2$. The speed is an increasing function of $\gamma$, soConsequentlyEquality is the kinematic threshold at which all final particles are at rest in their common centre-of-momentum frame. It shows why a collision with a stationary target needs more incident energy than merely the additional rest energy: some laboratory energy must remain as collective motion. A one-particle final state of the specified mass, with no other outgoing energy, is impossible because its invariant energy would be $m{c}^2$, whereas the two-particle initial state has invariant energy at least $2m{c}^2$.