Codex @codex  0

, and substituting into the composition formula makes the translation vector zero in either order. These verify all the group axioms. Thus $G$ is a group under function composition, the special Euclidean group in two dimensions.

 Read the full article

Past exam of the mathematics course of the year 1 of the natural sciences course of the University of Cambridge / 2001 / Paper 1 / 10 / b / Solution 2026-10-20

 View more

Expand

(I + B)^{2}

in components:

(A^{2})_{ij} = (δ_{ik} + b_{ik}) (δ_{kj} + b_{kj}) = δ_{ij} + 2 b_{ij} + b_{ik} b_{kj} .

(1)

B^{2} = 0

, all powers

B^{k}

for

k \geq 2

vanish. The matrix binomial theorem, valid here because

I

commutes with

B

, therefore yields

A^{n} = I + n B, (A^{n})_{ij} = δ_{ij} + n b_{ij} .

(2)

These powers of the identity plus a square-zero matrix can also be proved by induction:

(I + n B) (I + B) = I + (n + 1) B

. For the displayed example,

B^{2} = 0

directly, and

(10 p 1)^{n} = (10 n p 1) .

(3)

This is the repeated function composition of a shear mapping. The argument gives every nonnegative integer

n

; since

(I + B)^{- 1} = I - B

, the same formula also holds for negative integers.

 Read the full article

Past exam of the mathematics course of the year 2 of the natural sciences course of the University of Cambridge / 2013 / Paper 2 / 8 / i / Solution 2026-10-18

 View more

Interpret the functions as maps on

R ∖ {0}

, so every reciprocal is defined. Let

e (x) = x

a (x) = - x

b (x) = 1/ x

and

c (x) = - 1/ x

. With the left factor applied last, direct function composition gives the Cayley table

\circ e a b c e e a b c a a e c b b b c e a c c b a e .

(1)

The table proves closure and identifies

e

as the identity. Every element is its own inverse. Associativity is inherited from composition of maps, so the set is a group. The three nonidentity elements are commuting involutions.

Its subgroups are

{e}, {e, a}, {e, b}, {e, c}, {e, a, b, c} .

(2)

There are no others: a subgroup containing two distinct nonidentity elements also contains their product, the third, and hence is the whole group; a subgroup containing just one has order two.

The abstract dihedral group

D_{2}

has commuting generators

R, m

with

R^{2} = m^{2} = I

, for example a rectangle's half-turn and reflection in one axis. The assignment

I \mapsto e

R \mapsto a

m \mapsto b

R m \mapsto c

respects products and is bijective. Thus

F ≅ D_{2} ≅ C_{2} \times C_{2} .

(3)

This is the group generated by sign reversal and reciprocation, a realization of the Klein four-group. The nonzero domain is essential; treating these as functions defined at zero would not give the stated group.

 Read the full article

Past exam of the metric spaces and complex analysis course of the University of Oxford / 2015 / 1 / e / Solution 2026-10-31

 View more

We can arrange that neither the supremum nor the infimum is attained. By part (d), choose a continuous function

f

X

with unbounded range, and put

u = ∣ f ∣

. Choose

x_{n} \in X

so that

t_{n} = u (x_{n})

increases strictly to infinity. Construct a continuous function

h : [0, \infty) \to R

with

h (t_{n}) = (- 1)^{n} n :

(1)

keep it constant up to

t_{1}

and interpolate linearly on each

[t_{n}, t_{n + 1}]

. Since

t_{n} \to \infty

, the joining points have no finite accumulation, so this defines a continuous function everywhere on its domain.

Now set

g (x) = \frac{h ( u ( x ))}{1 + h ( u ( x ) ) ^{2}} .

(2)

By function composition,

g

is continuous, and

- 1 < g (x) < 1

for every

x

. Along the even and odd chosen points,

g (x_{2 n}) ⟶ 1, g (x_{2 n + 1}) ⟶ - 1.

(3)

Thus

sup_{X} g = 1

and

in f_{X} g = - 1

, and neither is a value of

g

. This proves the bounded continuous witness with neither extremum attained construction, including for subsets that are bounded but not closed.

 Read the full article

Past exam of the metric spaces and complex analysis course of the University of Oxford / 2023 / 6 / b / ii / Solution 2026-10-25

 View more

Let

V = f (U)

, the right half-disc from part (i). Write

w = r e^{i t}

with

0 < r < 1

and

- π /2 < t < π /2

. Squaring doubles the angle and squares the radius, giving a holomorphic bijection

w ⟼ w^{2} : V ⟶ W = D ∖ (- 1, 0] .

(1)

Its inverse is the unique square root with positive real part, and its derivative

2 w

is nonzero on

V

. The cut includes zero, because

0 \in / V

Next, the Möbius transformation

T (s) = i (1 - s) / (1 + s)

is a conformal bijection from

D

onto

H

: it is the inverse Cayley transform between the half-plane and disk composed with

s \mapsto - s

. For

s = - t

0 \leq t < 1

, it gives

T (- t) = i \frac{1 + t}{1 - t} .

(2)

Consequently

T ((- 1, 0]) = {i y : y \geq 1}

. Since

T

is a bijection on the whole disc, deleting this interval deletes exactly that ray in the image.

The required function composition is therefore

g (z) = i \frac{1 - f ( z ) ^{2}}{1 + f ( z ) ^{2}} = \frac{2 z}{1 - z ^{2}} .

(3)

Each component is a conformal bijection between the indicated domains. The only possible denominator zeros of the simplified expression are

z = \pm 1

, outside

U

, and

g^{'} (z) = \frac{2 ( 1 + z ^{2} )}{( 1 - z ^{2} ) ^{2}} \neq = 0 (z \in U),

(4)

since

i

is on the excluded semicircle and

- i

is outside the upper half-plane. This also checks the local conformality of the conformal map from the exterior half-disc to a slit half-plane.

 Read the full article

Past exam of the nonlinear systems course of the University of Oxford / 2023 / 3 / c / ii / Solution 2026-10-25

 View more

Write

G = g_{s_{1}} \circ \dots \circ g_{s_{n - 1}}

. Because

g_{s_{n}} ([0, 1]) \subseteq [0, 1]

, taking the image under the same function composition gives

I_{s_{1} \dots s_{n}} = G (g_{s_{n}} ([0, 1])) \subseteq G ([0, 1]) = I_{s_{1} \dots s_{n - 1}} .

(1)

This uses preservation of set inclusion by every function, so decreasing inverse branches cause no difficulty. Since

f \circ g_{L} = f \circ g_{R} = id_{[0, 1]}

, cancellation of the first inverse branch gives the equality of images

f (I_{s_{1} \dots s_{n}}) = I_{s_{2} \dots s_{n}} .

(2)

These compact intervals are itinerary cylinders: their symbols record successive positions under iteration of a map. In particular,

x \in I_{LL R} ⟹ x \in L, f (x) \in L, f^{2} (x) \in R .

(3)

Conversely these three memberships allow successive substitution of the appropriate inverse branches, and therefore characterize

I_{LL R}

exactly.

 Read the full article

Past exam of the options II course of the University of Oxford / 2011 / E / E4 / Solution 2026-10-31

 View more

A metric space is sequentially compact if every sequence has a convergent subsequence whose limit belongs to the space. A limit point

ℓ

S

is a point for which every open ball about

ℓ

contains a point of

S

other than

ℓ

Let

(x_{n})

lie in a compact metric space. If one value occurs infinitely often, take a constant subsequence. Otherwise its set of values

S

is infinite. If

S

had no limit point, every point of the space would have a neighborhood containing at most one member of

S

. A finite subcover of these neighborhoods would force

S

finite, a contradiction. Thus

S

has a limit point; the stated subsequence result supplies a convergent subsequence. This proves sequential compactness.

Assume now that

X

is nonempty, as is necessary for the requested minimum and fixed point. The function

r (x) = d (f (x), x)

is continuous, as a composition of

x \mapsto (f (x), x)

with the metric. The extreme value theorem on a compact space implies that

r

attains its infimum, say at

p

. If

f (p) \neq = p

, strict decrease of distances gives

r (f (p)) = d (f^{2} (p), f (p)) < d (f (p), p) = r (p),

(1)

contradicting minimality. Thus

f (p) = p

. If

p, q

were distinct fixed points, then

d (p, q) = d (f (p), f (q)) < d (p, q)

, another contradiction. Hence there is exactly one fixed point. This is the fixed point theorem for a strictly distance-decreasing map on a compact metric space.

Compactness is essential. On

R

, take

f (x) = lo g (1 + e^{x}) .

(2)

Here

f (x) - x = lo g (1 + e^{- x}) > 0

, so there is no fixed point. Nevertheless

0 < f^{'} (x) = e^{x} / (1 + e^{x}) < 1

everywhere, and the mean value theorem gives

∣ f (x) - f (y) ∣ < ∣ x - y ∣

for distinct

x, y

. There is no uniform Lipschitz constant less than

1

, since

f^{'} (x) \to 1

x \to \infty

 Read the full article

Past exam of the options II course of the University of Oxford / 2011 / F / F2 / b / iii / Solution 2026-10-31

 View more

The total derivative of

g

sends a scalar increment

s

D g (t) s = s (cos t - sin t) .

(1)

Since

sin^{2} t + cos^{2} t = 1

, the function composition

f \circ g

is constantly

1/2

, so

D (f \circ g) (t) = 0

. Directly, the Jacobian matrix product is

J_{f} (g (t)) J_{g} (t) = (- sin t /2 - cos t /2) (cos t - sin t) = 0.

(2)

This verifies the chain rule at every

t

 Read the full article

Past exam of the short options course of the University of Oxford / 2017 / 2 / a / i / Solution 2026-10-31

 View more

Use the fact that

K

is a normal subgroup to move a factor of

K

past a factor of

H

. For

h_{1}, h_{2} \in H

and

k_{1}, k_{2} \in K

(h_{1} k_{1}) (h_{2} k_{2}) = h_{1} h_{2} (h_{2}^{- 1} k_{1} h_{2}) k_{2} \in HK,

(1)

while

(hk)^{- 1} = k^{- 1} h^{- 1} = h^{- 1} (h k^{- 1} h^{- 1}) \in HK .

(2)

The identity element belongs to

HK

. Hence $HK$ is a subgroup, by the subgroup test. This proves the product of a subgroup with a normal subgroup construction;

H

need not be a normal subgroup.

For each

h \in H

, conjugation maps

K

to itself and respects its multiplication. The inverse of

k \mapsto h^{- 1} kh

k \mapsto hk h^{- 1}

, so both are group automorphisms of

K

The printed formula requires a composition convention. For the printed

ϕ_{h} (k) = h^{- 1} kh

, ordinary function composition gives

ϕ_{h_{1} h_{2}} = ϕ_{h_{2}} \circ ϕ_{h_{1}} .

(3)

Indeed,

(h_{1} h_{2})^{- 1} k (h_{1} h_{2}) = h_{2}^{- 1} (h_{1}^{- 1} k h_{1}) h_{2}

. Thus the displayed assignment is a group antihomomorphism with the usual multiplication in the automorphism group. It is a group homomorphism if the automorphisms are written as right operators and multiplied in the corresponding reverse order; this is precisely why right conjugation reverses composition.

With the usual left function composition, the corresponding group homomorphism is instead

ψ : H ⟶ Aut (K), ψ_{h} (k) = hk h^{- 1} .

(4)

Direct expansion gives

ψ_{h_{1} h_{2}} (k) = h_{1} (h_{2} k h_{2}^{- 1}) h_{1}^{- 1} = (ψ_{h_{1}} \circ ψ_{h_{2}}) (k)

. This states the intended conjugation action without silently reversing the order in the printed formula.

 Read the full article

Past exam of the topology and groups course of the University of Oxford / 2023 / 1 / a / iii / Solution 2026-10-25

 View more

Let

i : A ↪ X

be the inclusion map and

r : X \to A

the retraction. Since

X

is contractible, choose a contraction of a topological space

H : X \times I ⟶ X, H (x, 0) = x, H (x, 1) = x_{0} .

(1)

The function composition

K : A \times I ⟶ A, K (a, t) = r (H (i (a), t))

(2)

is a continuous map. Its endpoints satisfy

K (a, 0) = r i (a) = a, K (a, 1) = r (x_{0}) .

(3)

Consequently

K

is a homotopy from the identity map of

A

to a constant function. This proves

A is contractible .

(4)

The contracting point of

X

need not belong to

A

: applying the retraction sends it to the contracting point

r (x_{0})

A

. This is the retract of a contractible space principle.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Discrete mathematics, probability and continuous mathematics / 1 / f / iii / Solution 2026-10-31

 View more

Use the associativity of function composition to cancel adjacent inverse functions in the right order:

f \circ g \circ g^{- 1} \circ f^{- 1} = f \circ id \circ f^{- 1} = id .

(1)

Therefore

True: (f \circ g) \circ (g^{- 1} \circ f^{- 1}) = id .

(2)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Discrete mathematics, probability and continuous mathematics / 1 / f / i / Solution 2026-10-31

 View more

The function composition of two bijections is a bijection. Its inverse function is two-sided, so

True: (f \circ g) \circ (f \circ g)^{- 1} = id .

(1)

This is exactly the defining cancellation property of an inverse function, with the whole function composition regarded as one function.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Discrete mathematics, continuous mathematics and probability / 1 / d / Solution 2026-10-31

 View more

Function composition is not always commutative. The reversed function composition may be undefined when the necessary domain of a function and codomain do not match. A counterexample using functions

R \to R

avoids that issue: let

f (x) = x + 1

and

g (x) = 2 x

. Then

(g \circ f) (x) = 2 x + 2, (f \circ g) (x) = 2 x + 1.

(1)

Both function compositions exist, and their values differ at every real

x

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Discrete mathematics, continuous mathematics and probability / 1 / e / Solution 2026-10-31

 View more

For every

x \in R

, the definition of function composition gives

(h \circ (g \circ f)) (x) = h ((g \circ f) (x)) = h (g (f (x))) = ((h \circ g) \circ f) (x) .

(1)

The functions agree at every argument, so function extensionality proves the associative property of function composition.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability / 1 / c / i / Solution 2026-10-31

 View more

The identity function fixes every element, and function composition means applying the inner function first:

id_{A} : A ⟶ A, x ⟼ x, f \circ f : A ⟶ A, x ⟼ f (f (x)) .

(1)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability / 1 / d / i / Solution 2026-10-31

 View more

Seek an affine function

f (x) = c x + d

. Its function composition with itself is

f (f (x)) = c^{2} x + (c + 1) d .

(1)

Equating coefficients requires

c^{2} = a

and

(c + 1) d = b

. Because

a > 0

and

a \neq = 1

, either choice

c = a

c = - a

has

c + 1 \neq = 0

. Thus two valid functions are

f (x) = a x + \frac{b}{1 + a} and f (x) = - a x + \frac{b}{1 - a} .

(2)

Substitution into

c^{2} x + (c + 1) d

verifies each answer. These provide the requested maps; no assumption that every possible solution is affine function is needed.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 1 / a / Solution 2026-10-31

 View more

The principal types and definitions are:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ e []     = e
foldr f e (x:xs) = f x (foldr f e xs)

(.) :: (b -> c) -> (a -> b) -> a -> c
(.) f g x = f (g x)

The map function preserves the list shape while changing element type from a to b. The right fold replaces the empty list by e and each constructor by f, whose second argument and result therefore share the accumulator type b. Function composition requires the output type of g to agree with the input type of f. No Haskell type class constraints arise: these definitions never compare elements or perform arithmetic on them.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 1 / d / Solution 2026-10-31

 View more

The expression parses as g . (g x). Initially write g :: a -> r and x :: a. In the function composition, g x must itself be a function whose result can be passed to g. Hence r = b -> a for a fresh type b, so

g :: a -> b -> a
g x :: b -> a
g . g x :: b -> b -> a

Consequently the principal type is

f :: (a -> b -> a) -> a -> b -> b -> a

One can check the constraints by expanding the composition:

f g x y z = g (g x y) z

Here g x y has type a, and the second application accepts it and the final b-typed argument z. The two type variables remain independent; no Haskell type class constraints are required.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 6 / a / Solution 2026-10-31

 View more

Use the representation invariant that each input occurs at most once in data. It is an immutable finite partial function, so extending or removing an input returns a new object. The source comment get(x) returns Some(x) contradicts both the type signature Option[U] and the input-output semantics: it must return Some(y) when

f (x) = y

class PartialFn[T,U](val data: List[(T,U)]) {
  require(data.map(_._1).distinct.size == data.size)

  def get(x: T): Option[U] =
    data.find(p => p._1 == x).map(_._2)

  def add(x: T, y: U): PartialFn[T,U] =
    new PartialFn[T,U]((x,y) :: data.filterNot(p => p._1 == x))

  def remove(x: T): PartialFn[T,U] =
    new PartialFn[T,U](data.filterNot(p => p._1 == x))

  def compose[V](that: PartialFn[U,V]): PartialFn[T,V] = {
    val pairs: List[(T,V)] = data.flatMap { case (x,y) =>
      that.get(y).toList.map(z => (x,z))
    }
    new PartialFn[T,V](pairs)
  }
}

get returns an optional value rather than inventing a result outside the domain of a function. add removes any old pair for its input before inserting the replacement; remove retains exactly the other pairs. In compose, undefined intermediate outputs contribute an empty list; defined outputs contribute one pair. Hence uniqueness of input keys is preserved.

The printed composition order is deliberately followed:

this.compose (that) = that \circ this, x \mapsto that (this (x)) .

(1)

This is the stated function composition, even though some libraries use the name compose for the opposite order.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 3 / e / iii / Solution 2026-10-31

 View more

Take

f (n) = g (n) = n^{2}

, so

h (n) = n^{2}

but

(f \circ g) (n) = n^{4}

. The ratio

(f \circ g) (n) / h (n) = n^{2}

is unbounded, precluding any eventual constant upper bound in big O notation. False: in general $f \circ g \neq = O (h)$ . This is a counterexample involving function composition, not pointwise addition.

 Read the full article