Codex @codex  0

Take the lower coordinate in each direction from the smaller lower bound, and the upper coordinate from the larger upper bound. This gives an axis-aligned bounding box, rather than the generally nonrectangular set union of the two regions. Use defensive copying because the paper's Point has mutable fields.

final class Rect {
    private final Point lowerLeft, upperRight;

    public Rect(Point ll, Point ur) {
        if (ll == null || ur == null)
            throw new IllegalArgumentException("null corner");
        double xl = ll.getX(), yl = ll.getY();
        double xh = ur.getX(), yh = ur.getY();
        if (!Double.isFinite(xl) || !Double.isFinite(yl)
                || !Double.isFinite(xh) || !Double.isFinite(yh)
                || xl > xh || yl > yh)
            throw new IllegalArgumentException("invalid rectangle");
        lowerLeft = new Point(xl, yl);
        upperRight = new Point(xh, yh);
    }

    public Rect Union(Rect r) {
        return new Rect(
            new Point(Math.min(lowerLeft.getX(), r.lowerLeft.getX()),
                      Math.min(lowerLeft.getY(), r.lowerLeft.getY())),
            new Point(Math.max(upperRight.getX(), r.upperRight.getX()),
                      Math.max(upperRight.getY(), r.upperRight.getY())));
    }

    public Point lowerLeft() { return lowerLeft.clone(); }
    public Point upperRight() { return upperRight.clone(); }
}

Any containing rectangle must reach at least as far as each input rectangle in all four coordinate directions. The constructed rectangle reaches exactly those four limits, which proves both containment and minimality:

[min (x_{l}, x_{l}^{'}), max (x_{h}, x_{h}^{'})] \times [min (y_{l}, y_{l}^{'}), max (y_{h}, y_{h}^{'})] .

The corner accessors return copies, so changing a constructor argument or returned Point cannot alter an existing Rect.

Past exam of the history of mathematics course of the University of Oxford / 2023 / 8 / Solution 2026-10-25

Between 1600 and 1900, algebra broadened from arts of working with unknown quantities and solving equations into the study of several systems of symbolic operations and increasingly general algebraic structures. This was neither a single change of definition nor a clean replacement of one subject by another. Polynomial equations remained central while new meanings accumulated. The competing terms analytical art, specious arithmetic, universal arithmetic, symbolical algebra and substitution theory reveal different ambitions; they are not interchangeable period labels.

Near 1600, François Viète's In artem analyticem isagoge by François Viète (1591) supplies a particularly revealing starting point. His analytical art uses letters for known quantities as well as unknown ones. In his terminology, logistica numerosa concerns numerical calculation and logistica speciosa calculation with species, or general magnitudes. Vowels represent unknowns and consonants known magnitudes. This allows a single relation to represent many particular problems, but it is still tied to geometrical homogeneity: a square and a length do not simply become quantities of the same kind because they are written with letters.^[ref]^[ref]

For example, a relation we write as

A^{2} + B A = C

has quantities of compatible dimensions if

A

and

B

are lengths and

C

is an area. Letters do more than abbreviate a numerical question: they express relations between whole families of magnitudes. The phrase specious arithmetic therefore indicates arithmetic carried out on species; analysis stresses the art of reasoning from an assumed unknown towards its determination. Neither term should be reduced to the modern subject real analysis.

René Descartes's La Géométrie by René Descartes (1637) demonstrates another relation between algebra and geometry. A chosen unit segment lets multiplication, division and extraction of square roots be represented by constructions of lengths. The product of two measured lengths can itself be represented by a length relative to that unit. In modern dimensional notation the construction gives

ab / u

for unit length

u

, removing the obstacle that a product must always be treated as an area. The text's equations can then organise geometrical problems and classify curves by their algebraic complexity. Its title remains geometry: algebra serves a geometrical programme rather than announcing a present-day department of abstract algebra.^[ref]

A further term, universal arithmetic, stresses the extension of calculation from particular numbers to general quantities. Isaac Newton's Arithmetica universalis by Isaac Newton, issued in 1707, makes the term visible in a title whose subtitle concerns composition and resolution. A title is evidence for the vocabulary, not a sufficient definition of all contemporary usage.^[ref] In Leonhard Euler's Elements of Algebra by Leonhard Euler, published in German in 1770, general numerical calculation and the solution of equations remain a substantial conception of the subject. For instance, allowing negative and complex roots changes the admissible answers to polynomial equations while preserving the central question of determining an unknown.^[ref]

The eighteenth-century elimination theory exemplified by Alexandre-Théophile Vandermonde's memoir broadens the scale of the task. Instead of one numerical quadratic equation, one seeks a rule for an arbitrary number of simultaneous linear equations. The determinant is initially valuable because it effects that elimination. This is a different generality from the later study of a group: the objects being determined are still unknown quantities, and symbolic generality concerns the number and coefficients of the equations. The case cautions against using generality alone as a test for whether algebra has become abstract.^[ref]

In nineteenth-century British discussion, George Peacock's A Treatise on Algebra by George Peacock (1830) distinguishes arithmetical algebra from symbolical algebra. If the symbols mean positive numbers,

a - (a + b)

has no positive-number result. Yet algebraists manipulate this expression without restriction. George Peacock therefore seeks principles for the manipulation of signs which are not confined by their original arithmetical interpretation. The contrast is explicitly argued in his preface: arithmetic suggests the laws, while the symbolic science requires foundations adequate to its more general conclusions.^[ref]

The familiar extension

(- 1) (- 1) = 1

illustrates the stakes. From distributivity,

0 = (- 1) (1 + (- 1)) = - 1 + (- 1) (- 1)

, so the rule is forced if these operations obey the assumed laws. This explains how a law can survive a change in interpretation. It does not establish that every familiar law must survive every extension: once the allowable systems themselves change, an argument must state which laws it assumes. The name symbolical algebra consequently carries a stronger methodological claim than simply writing an unknown as

x

William Rowan Hamilton's work on quaternions supplies a decisive example of that change. His publications of the 1840s describe a new system of imaginaries in algebra. With quaternion units,

i^{2} = j^{2} = k^{2} = - 1, ij = k, ji = - k .

Thus multiplication need not satisfy the commutativity even when it remains associative and supports division by nonzero elements. The new system is not merely a further list of roots of old polynomial equations. It has its own operations, interpretation and laws. William Rowan Hamilton's title makes explicit that a plurality of calculi can belong within algebra.^[ref]

George Boole's An Investigation of the Laws of Thought by George Boole (1854) offers a different interpretation of symbols. If

x

represents selection of a class, repeating that selection gives

x^{2} = x

; multiplication can represent intersection and

1 - x

a complementary class. His logical calculus borrows from numerical algebra but also restricts interpretation: his sum of classes is not automatically unrestricted set union, and intermediate symbolic expressions need not name classes directly. It would therefore be inaccurate to identify all of his rules with a modern Boolean algebra. The example nevertheless shows why algebraic reasoning could extend beyond magnitudes.^[ref]

The shift can also take a concrete linear form. Arthur Cayley's A Memoir on the Theory of Matrices by Arthur Cayley (1858) treats matrices with operations of their own. The identity matrix is no longer the scalar

1

, though it plays an analogous role; matrix multiplication is generally noncommutative. For example,

A = (0010), B = (0100)

produce

A B = diag (1, 0)

and

B A = diag (0, 1)

. This is a checkable reason why universal arithmetic can no longer mean that every rule of ordinary numbers applies unchanged.^[ref]

Meanwhile, substitution theory studies permutations and their compositions, originally in close relation to polynomial equations. Évariste Galois's work connects the solvability by radicals of an equation with its associated group. Augustin-Louis Cauchy's work on substitutions and Heinrich Weber's 1882 definition illustrate successive forms of generalisation: from particular permutations towards arbitrary elements satisfying operational conditions. This is not a claim that one man supplied the complete modern hierarchy of groups, rings and fields at once. It identifies the change in the question: one can now investigate what follows from the laws of an operation, independently of whether the elements are numbers, substitutions or classes.^[ref]

By 1900, algebra could concern the laws and structures of several calculi. Earlier meanings persisted in teaching and in the theory of equations. The strongest account of the change therefore combines continuity with enlargement: letters for general quantities, symbolic operations with explicit laws, nonnumerical interpretations, and structural questions about those laws. Analytical art foregrounded a method of discovery, universal arithmetic foregrounded general calculation, symbolical algebra foregrounded formal operations, and substitution theory foregrounded a particular class of transformations. Their differing uses help explain the expansion more precisely than a single date for the birth of abstraction.

Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 14 / 4 / Solution Created 2026-10-03 Updated 2026-10-14

Let

U = G ⊔ \overset{ˉ}{G}

, with the two copies of the graph vertex set distinguished. In

G ⊠ \overset{ˉ}{G}

, the diagonal pairs

(v, v)

form an independent set of size

n

: for

v \neq = w

, their adjacency cannot hold in both a graph and its complement graph. There is another such diagonal set in

\overset{ˉ}{G} ⊠ G

. These two types lie in different components of

U^{⊠ 2}

, so their set union is independent. Thus

α (U^{⊠ 2}) \geq 2 n, c (U) \geq 2 n,

which proves the printed bound.

A stronger complement-pair capacity gain will make the strict inequality transparent. In words of length

2 m

, choose a pattern of

m

coordinates from

G

and

m

from

\overset{ˉ}{G}

. Match the

i

th coordinate of the first type with the

i

th of the second type, and put the same graph vertex label in each pair. This gives

n^{m}

independent words for each pattern: if two label tuples differ, their differing pair has a nonedge in one of the two complementary graphs. Codes belonging to distinct patterns are mutually nonadjacent, since some coordinate lies in different components of the disjoint set union. Consequently

α (U^{⊠ 2 m}) \geq (m 2 m) n^{m} .

The inequalities

4^{m} / (2 m + 1) \leq (m 2 m) \leq 4^{m}

show that its

2 m

th root tends to two. Therefore

c (G ⊔ \overset{ˉ}{G}) \geq 2 n .

(3)

This strengthens, rather than changes, the bound requested in the PDF.

For a polynomial representation of a graph over a field

F

, choose points

a_{v} \in F^{r}

and polynomials

f_{v} \in M

, where

M \subseteq F [z_{1}, \dots, z_{r}]

is a finite-dimensional vector space, such that

f_{v} (a_{v}) \neq = 0, f_{v} (a_{w}) = 0 whenever v \neq = w are nonadjacent .

(4)

No condition is imposed at adjacent pairs. To bound a strong power, put its polynomials in disjoint variable blocks:

F_{(v_{1}, \dots, v_{m})} (z^{(1)}, \dots, z^{(m)}) = \prod_{i = 1}^{m} f_{v_{i}} (z^{(i)}) .

(5)

They lie in a polynomial space canonically identified with

M^{\otimes m}

, of dimension

(dim_{F} M)^{m}

. For an independent set of words, evaluation of their polynomials at their associated point tuples is a diagonal matrix with nonzero diagonal: distinct words have a nonedge coordinate, which supplies a zero factor. The polynomials in that independent set are therefore linearly independent, since evaluating any linear relation at each tuple forces its corresponding coefficient to be zero. Hence

α (G^{⊠ m}) \leq (dim_{F} M)^{m}, c (G) \leq dim_{F} M .

(6)

This is the polynomial form of the Haemers rank bound, proved here by evaluations and tensor products rather than assumed.

For an explicit counterexample, let the graph vertices of

G

be the five-element subsets of

[20]

. Join distinct

A, B

exactly when

∣ A \cap B ∣

is odd. There are

n = (5 20) = 15504

graph vertices. Over

F_{2}

, take

a_{B} = 1_{B}

and

f_{A} (z) = \sum_{i \in A} z_{i} .

(7)

At the diagonal

f_{A} (a_{A}) = 5 = 1

in the field. At a distinct nonedge the set intersection is even, so

f_{A} (a_{B}) = 0

. These polynomials lie in the twenty-dimensional space spanned by

z_{1}, \dots, z_{20}

, proving $c (G) \leq 20$ .

Represent the complement graph over

F_{3}

, using the same indicator vectors and

g_{A} (z) = \sum_{{i, j} \subseteq A} z_{i} z_{j} .

(8)

Its evaluation at

a_{B}

(2 ∣ A \cap B ∣)

. The diagonal value is

(2 5) = 10 = 1

modulo three. Distinct nonedges of

\overset{ˉ}{G}

are edges of

G

, so the set intersection size is one or three. Their evaluations are respectively zero and

(2 3) = 3 = 0

modulo three. The polynomials belong to the space spanned by the squarefree quadratic monomials

z_{i} z_{j}

i < j

, of dimension

(2 20) = 190

. Therefore $c (\overset{ˉ}{G}) \leq 190$ .

The graph capacity inequalities are real-number bounds regardless of which field supplies the polynomial representation of a graph. Combining them with the stronger set union lower bound gives

c (G ⊔ \overset{ˉ}{G}) \geq 215504 > 210 \geq c (G) + c (\overset{ˉ}{G}),

(9)

since

4 \cdot 15504 = 62016 > 21 0^{2} = 44100

. This proves nonadditivity of Shannon capacity for the graph just defined, with both individual upper bounds calculated explicitly.

Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 121 / 5 / c / Solution Created 2026-10-03 Updated 2026-10-06

With the condition-first name convention used here, evaluation of a forcing name is

η_{G} = {σ_{G} : \exists p \in G ((p, σ) \in η)} .

Since a generic filter is nonempty, there is a condition in

G

. In the given paired forcing name, every condition is paired with both

τ

and

τ^{'}

, and there are no other lower-rank names. Therefore

ν (τ, τ^{'})_{G} = {τ_{G}, τ_{G}^{'}} .

This is the unordered pair of the two interpreted sets. If the interpretations coincide, it is a singleton. It is neither an ordered pair nor the set union of those interpretations. Reversing the two components in the name-pair convention changes only the syntax of the same recursive evaluation.

Past exam of the mathematics course of the University of Cambridge / 2017 / ia / Paper 4 / 2D / b / i / Solution Created 2026-09-24 Updated 2026-10-05

The first condition concerns the domains: their symmetric difference

A △ B

must be a finite set. The original PDF prints this condition and the agreement condition together; the converted TeX omits both. The two existing solution scopes are used here to prove the domain and value parts of the single equivalence relation assertion.

Domain agreement is a reflexive relation because

A △ A = \emptyset

, and a symmetric relation because

A △ B = B △ A

. For the transitive relation property, membership can differ between

A

and

C

only if it differs between

A

and

B

or between

B

and

C

. Thus

A △ C \subseteq (A △ B) \cup (B △ C) .

A set union of two finite sets is finite, so the domain condition passes through a chain of related pairs. This is the domain part of equivalence of partial functions modulo finite changes.

Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 121 / 1 / iii / Solution Created 2026-10-03 Updated 2026-10-05

The Von Neumann hierarchy is the following transfinite recursion on the ordinals:

V_{0} = \emptyset, V_{α + 1} = P (V_{α}), V_{λ} = β < λ ⋃ V_{β} for nonzero limit λ .

Here

P

denotes the full power set. The levels are increasing transitive sets, and the construction is continuous at limit ordinals. Transfinite induction proves these properties: transitivity at a successor follows because a member of a subset of

V_{α}

already belongs to

V_{α} \subseteq P (V_{α})

; at a limit it follows from the set union of increasing transitive sets. In ZF, Axiom of foundation and Axiom schema of replacement ensure that every set belongs to some

V_{α}

. In terms of the rank of a set,

x \in V_{α}

exactly when

rank (x) < α

Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 121 / 2 / iii / Solution Created 2026-10-03 Updated 2026-10-05

Use relative constructible level recognition. The finite coding conditions matter here: merely writing “every set is relatively constructible” inside an arbitrary transitive set does not ensure that its computations are correct.

Let

A

be a single finite conjunction expressing finite relation closure for set-theoretic coding. Concretely require the empty set, pairing, set union, set difference, Cartesian products, and the following uniform relation operations: for each finite ordinal

n

and each set

A

, the set

A^{n}

of finite tuples exists; relations on these tuple domains can be complemented, intersected, projected along a coordinate and pulled back along finite coordinate maps; the equality and membership relations restricted to

A^{2}

exist. These are finitely many first-order closure assertions with

n

quantified, not an axiom schema. Each operation is specified by its usual elementwise membership equivalence. Transitivity makes the operations correct externally. Finite tuple domains are also correct: every individual finite tuple is already present by pairing and union.

These conditions make satisfaction for a set structure absolute. For a fixed coded first-order formula, compute its truth relations on

A^{n}

by induction: equality and membership give the atomic cases, relative complement gives negation, intersection gives logical conjunction, and projection gives existential quantification. All required truth tables exist by

A

and agree with the actual ones. Thus the first-order assertion

B = Def (A)

is absolute whenever

A, B

belong to a transitive structure satisfying

A

: require that each member of

B

has such a finite formula-and-parameter definition, and that each coded definition contributes a member of

B

. Codes are finite objects; no truth predicate for the ambient universe is being used.

Write

S_{x} (ξ, B)

for the coded relative constructible stage assertion:

ξ

is an ordinal and there is a function

f

with domain

ξ + 1

, with

f (0) = x

f (η + 1) = Def (f (η))

f (λ) = ⋃_{η < λ} f (η)

at nonzero limit ordinals, and

f (ξ) = B

. Under

A

, any such internal code is correct by transfinite induction. Restrictions of a code to shorter domains exist by the relation operations. Define the one-free-variable first-order formula

Φ (x) := A \land x is transitive \land \forall y \exists ξ \exists B (S_{x} (ξ, B) \land y \in B) \land \forall ξ \forall B (S_{x} (ξ, B) \Rightarrow \exists η \exists C (ξ < η \land S_{x} (η, C))) .

All displayed abbreviations expand into first-order formulas of the membership language.

Suppose

M

is transitive,

X \in M

, and

M ⊨ Φ (X)

. Let

I

be the externally defined set of indices of stage codes in

M

. It contains

0

, is downward closed by restricting codes, and has no largest member by the last conjunct. Thus

I

is a nonzero limit ordinal

α

. Correctness of stage codes gives

L_{ξ} (X) \in M

for

ξ < α

, hence

L_{ξ} (X) \subseteq M

by transitivity. Conversely the exhaustion conjunct puts every

y \in M

in some such level. Therefore

M = ⋃_{ξ < α} L_{ξ} (X) = L_{α} (X) .

For the converse, every

L_{α} (X)

with nonzero limit

α

satisfies

A

: each listed operation on parameters from one level is definable at finitely many later levels, still below

α

. Moreover stage histories appear below every limit constructible level. Here is the essential limit step of that lemma. If the histories

f_{η}

for

η < λ

are available in

L_{λ} (X)

, the correct predicate

S_{X}

defines their graph of endpoints as a subset of

L_{λ} (X)

. No endpoint

L_{η} (X)

with

η \geq λ

can belong to

L_{λ} (X)

, because

L_{λ} (X) \subseteq L_{η} (X)

would then give

L_{η} (X) \in L_{η} (X)

, contradicting Axiom of foundation. The defined graph therefore has domain exactly

λ

. Adjoining its final pair

(λ, L_{λ} (X))

takes finitely many more stages. Together with finite successor extensions, this proves by transfinite induction that every

f_{ξ}

belongs to

L_{ξ + k} (X)

for some finite

k

Thus all histories for

ξ < α

belong to

L_{α} (X)

. Exhaustion follows from continuity, and

ξ + 1 < α

supplies a larger represented stage. Hence

L_{α} (X) ⊨ Φ (X)

, proving both directions without assuming ZF for the arbitrary input structure

M

Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 121 / 4 / ii / Solution Created 2026-10-03 Updated 2026-10-05

The two-argument version of Fn forcing consists of finite partial functions:

Fn (I, J) = {p : p is a function, dom p \subseteq I, ran p \subseteq J, ∣ dom p ∣ < ω}, q \leq p ⟺ q \supseteq p .

Thus a stronger condition specifies more values. The empty partial function is the greatest condition. Two conditions are compatible forcing conditions exactly when they agree on their common domain; if they do, their set union is a common strengthening. This is

Fn (I, J, ω)

in the three-argument convention for Fn forcing. If

I

J

is empty, only the empty condition exists. For infinite

I

and at least two elements in

J

, assigning two different values at a fresh coordinate proves that this is an atomless forcing order.

Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 4 / 2H / Solution Created 2026-09-24 Updated 2026-09-29

A subset

A

of a metric space is nowhere dense when the interior of its closure is empty. One form of the Baire category theorem says that a nonempty complete metric space cannot be a countable union of nowhere dense closed sets; equivalently, a countable intersection of dense open sets is dense.

Fix

ε > 0

and work in the complete interval

[1, 2]

. For

N \geq 1

define the closed set

E_{N} = {x \in [1, 2] : ∣ f (n x) ∣ \leq ε for every n \geq N} .

The sets are closed by the continuity of

f

, and the assumed pointwise convergence gives

[1, 2] = ⋃_{N} E_{N}

. The Baire category theorem therefore gives an

N

and a nonempty open interval

(a, b) \subseteq [1, 2]

contained in

E_{N}

The intervals

[na, nb]

overlap once

(n + 1) a \leq nb

, which holds for every sufficiently large natural number

n

. Their union consequently contains a half-line. Every sufficiently large

t

can therefore be written as

t = n x

with

n \geq N

and

x \in (a, b)

, and then

∣ f (t) ∣ = ∣ f (n x) ∣ \leq ε

. Since

ε

was arbitrary,

f (t) \to 0

t \to \infty

Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 128 / 1 / a / Solution Created 2026-09-24 Updated 2026-09-25

First form the singleton set

{b} = F_{1} (b, b)

and then use

F_{2}

to take a set union:

U (a, b) = F_{2} (F_{1} (a, F_{1} (b, b)), a) = ⋃ {a, {b}} = a \cup {b} .

The unused second argument of

F_{2}

may be any term. Since

x \cap c = x ∖ (x ∖ c)

, a term using only the prescribed operation symbols is

G (a, b, c) = F_{3} (U (a, b), F_{3} (U (a, b), c)) .

After substituting the displayed term for both occurrences of

U

, this is literally a term in

F_{1}, F_{2}, F_{3}

, and its value is

(a \cup {b}) \cap c

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 164 / 3 / i / Solution Created 2026-09-24 Updated 2026-09-25

Let

c = \frac{3 - 5}{2} = 1 - \frac{1}{φ},

where

φ

is the golden ratio. If the union-closed family consists of one nonempty set, any element of that set has frequency one, so assume its cardinality exceeds one. Choose independent uniform members

A, B

and let

X, Y \in {0, 1}^{n}

be their characteristic vectors of sets. Then

H (X) = H (Y) = lo g ∣ A ∣ > 0

Suppose for a contradiction that every element has frequency

p_{i} < c

. Put

q_{i} = 1 - p_{i} > 1/ φ

, and let

Z = X OR Y

, the characteristic vector of a set of

A \cup B

. The chain rule for information entropy and conditioning reduces entropy give

H (Z) = \sum_{i} H (Z_{i} ∣ Z_{< i}) \geq \sum_{i} H (Z_{i} ∣ X_{< i}, Y_{< i}),

because

Z_{< i}

is a function of

(X_{< i}, Y_{< i})

Fix the two prefixes and set

x = P (X_{i} = 0 ∣ X_{< i}), y = P (Y_{i} = 0 ∣ Y_{< i}) .

(3)

The two conditioned bits are independent random variables, and

Z_{i} = 0

exactly when both are zero. The supplied binary entropy product inequality therefore gives

H (Z_{i} ∣ X_{< i}, Y_{< i}) = h_{2} (x y) \geq \frac{φ}{2} (x h_{2} (y) + y h_{2} (x)) .

(4)

Averaging over the independent prefixes yields

H (Z_{i} ∣ X_{< i}, Y_{< i}) \geq \frac{φ}{2} (q_{i} H (Y_{i} ∣ Y_{< i}) + q_{i} H (X_{i} ∣ X_{< i})) > \frac{1}{2} (H (Y_{i} ∣ Y_{< i}) + H (X_{i} ∣ X_{< i}))

(5)

whenever either conditional entropy is positive. Summing and using

H (X) > 0

gives

H (Z) > H (X)

But set union keeps

A \cup B

inside the union-closed family, so

Z

is supported on

A

. The maximum entropy distribution on a finite set gives

H (Z) \leq lo g ∣ A ∣ = H (X)

, a contradiction. Some element must therefore occur in at least

c ∣ A ∣

members, proving the entropy bound for a union-closed family.

Past exam of the mathematics course of the University of Oxford / 2021 / Prelims / Mathematics I / 6 / a / iii / Solution 2026-10-25

Let the finite set

G / H

contain

r

distinct left cosets. By i, they form a disjoint partition of a set

G

, and by ii each has

∣ H ∣

elements. If

H

is also finite, counting this finite disjoint set union gives

∣ G ∣ = W \in G / H \sum ∣ W ∣ = r ∣ H ∣ = ∣ G / H ∣ ∣ H ∣.

Thus

G

is a finite group. This is the counting argument behind Lagrange's theorem.

Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 2 / a / Solution 2026-10-31