Past exam of the mathematics course of the University of Cambridge 2005 ia Paper 4 5E Solution Created 2026-09-24 Updated 2026-10-14
A countable set is a set that is finite or can be put in bijection with the natural numbers; equivalently, it admits an injective function into the natural numbers. To enumerate the rational numbers, list pairs with , in increasing order of , and then list , discarding repetitions. Each level is finite and every rational eventually appears. An enumeration of the rationals then enumerates by listing in diagonals of constant . ThusTo prove that the real numbers are uncountable, suppose had an enumeration . Write each in its decimal expansion that does not end in an infinite string of nines. Define a new decimal by taking if the th digit of is , and otherwise. Then , has no ambiguous terminating/nines representation, and differs from at digit . The Cantor diagonal argument contradicts the supposed enumeration. Consequently the real numbers are uncountable.
For the discs, use the enumeration of just constructed. Every positive-radius disc contains a rational-coordinate point: its interior contains a small open rectangle, and each coordinate interval contains a rational number. For each disc , let be the least index of an enumerated rational-coordinate point in its interior. This minimum exists and requires no arbitrary simultaneous choice. Disjoint discs cannot receive the same point, so is an injective function into the natural numbers. This proves the countability of pairwise disjoint open disks and also the same conclusion for closed discs, by using their disjoint interiors.
For circles, take all concentric circles centred at the origin with radii . Two different radii give disjoint circles, and every radius is positive. The radius map is a bijection from the uncountable interval to this family. An uncountable disjoint family of nontrivial circles is therefore possible: the rational-point argument for discs relies on their nonempty interiors, which circumferences do not have.
Past exam of the mathematics course of the University of Cambridge 2015 ia Paper 4 8E b ii Solution Created 2026-09-24 Updated 2026-10-06
The integers are countable: for and for is an injection . Hence is a countable set. The map is a surjection onto the rational numbers, so the image result already proved gives is countable. Unique reduced fractions are not required for this surjection argument.
For the final unheaded geometry request, suppose for contradiction that no two distinct circles in the collection intersect. Restrict to the subcollection of circles tangent to the -axis. Each such nondegenerate circle has a unique tangency point, and the tangency-point map is a surjection by the hypothesis.
The closed disk of a circle tangent at meets the -axis only at . Two distinct members of cannot have nested disks: if one disk were inside the other, its tangency point would belong to the larger disk, so both tangency points would be equal and both circle boundaries would pass through it. That already contradicts nonintersection. Circles with disjoint boundaries and no nesting have disjoint disks. Thus their open disks are pairwise disjoint.
By the density of the rational numbers, every nonempty open disk contains a point of , which is a countable set. Fix an enumeration of and assign to each disk the first enumerated point inside it. Disjointness makes this assignment an injection. This is the countability of pairwise disjoint open disks, and proves that is a countable set. Its surjection onto would make the real numbers countable, contrary to the Cantor diagonal argument. ThereforeThe proof allows circles on either side of the axis and counts tangential contact as intersection; it does not assume that all circles in the original collection are tangent to the axis.