Past exam of the mathematics course of the University of Cambridge 2013 ia Paper 4 5E ii Solution Created 2026-09-24 Updated 2026-10-07
The empty-set cases for Cartesian projections matter here. For , write for the other factor. If is nonempty, any can be paired with an element of , so is surjective. If is empty, the Cartesian product is empty and its image is empty. ConsequentlyThe possibility is included because the empty function onto the empty set is surjective.
If is empty, has empty domain and is injective. If has at most one element, an ordered pair is determined by its th coordinate, so is also injective. Conversely, when is nonempty and contains two different elements, pairing those two elements with one fixed gives distinct ordered pairs with the same projection map. Therefore
Past exam of the mathematics course of the University of Cambridge 2013 ia Paper 4 7E ii Solution Created 2026-09-24 Updated 2026-10-07
For the cardinality of integer-periodic function spaces, fix a positive period first. A periodic function with that period is completely and uniquely determined by its values at , so this class is in bijection with . The integers are a countable set, and repeated pairing shows that a finite Cartesian product of countable sets is countable. Taking the union over positive and using the countable union of countable sets proves that the integer-domain periodic functions form a countable set.
For the rational domain, even period one leaves infinitely many independent choices. Let for ; these are distinct members of . For every subset , defineThe fractional part is unchanged by adding one, so is an integer-valued periodic function on . Distinct subsets give distinct functions because records whether . Thus the uncountable power set of injects into these functions. The rational-domain periodic functions form an uncountable set. The difference is that has only finitely many residue classes modulo a fixed integer period, whereas has infinitely many.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 13 4 Solution Created 2026-10-03 Updated 2026-10-06
For each element of the product set , let count its representations as with . The ratio equality is equivalent to . Swapping the two coordinates is a bijection between the ratio-equality quadruples and the equal-product quadruples. Therefore the multiplicative energy satisfiesThe Cauchy-Schwarz inequality gives the energy lower bound:For the upper bound, place the Cartesian product in the strictly positive quadrant. For every occupied Euclidean ray from the origin let be its points and . The slope is , soTake to be the natural logarithm and put , using the non-triviality assumption . Partition the possible occupancies into classes: for , and for the last class. This last closed endpoint ensures that the partition works even when the top endpoint is attained. Within each class the ratio of any two occupancies is at most .
Fix one class and order its occupied Euclidean rays by increasing slope, with occupancies . Write , the cardinality of . If , then , since adding any fixed element gives an injection of into its sumset , and similarly for .
If , the sums contain exactly different points, by injectivity of sums on two distinct rays. Indeed, the two direction vectors are linearly independent, so the coefficients of a sum uniquely recover its two summands. Positivity puts every sum strictly inside the open planar sector between those two Euclidean rays. The sectors between successive selected Euclidean rays are disjoint, even if there are additional unselected rays between them. All these sums belong to , and henceFor neighbouring occupancies their ratio lies between and , soSumming covers every at least once, and gives . The same bound holds for empty or singleton classes by the preceding observations. Adding over the classes proves the multiplicative energy sumset bound . Combining both bounds yields the sum-product conclusion:If instead is interpreted as base two, use the same occupancy classes with in place of ; proves that convention as well. Positivity is essential to the sector argument.
Past exam of the mathematics course of the University of Cambridge 2015 ii Paper 4 13I ii Solution Created 2026-09-24 Updated 2026-10-06
Use the Kuratowski ordered pair . Its rank of a set is . Every pair in the Cartesian product has finite rank, but those ranks are unbounded in . Therefore .
Past exam of the mathematics course of the University of Cambridge 2016 ia Paper 4 5E b i Solution Created 2026-09-24 Updated 2026-10-06
Write and enumerate . Each injective function is determined by the finite tuple . Thus these functions form a subset of the finite Cartesian product . A finite Cartesian power of a countable set is countable: for example, group the index tuples by the maximum of their coordinates, obtaining a countable union of countable sets consisting of finite groups.
There are also infinitely many such injective functions, sincedefines pairwise distinct examples. Therefore is a countably infinite set.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 112 1 iii Solution Created 2026-10-03 Updated 2026-10-06
No: the Lebesgue measure can decrease when separate components of the Minkowski sum merge. A one-dimensional example is enough to disprove the assertion in general. TakeThe Minkowski sum consists of four open intervals, with left endpoints and common length . At the four open intervals are disjoint, soAt the middle two open intervals coincide and the remaining three are disjoint, soFor a counterexample in any prescribed dimension , take Cartesian products of these open sets with in the remaining coordinates. Compare with , where is sufficiently small, and choose the interval width so small that . The four intervals remain disjoint at , givingChoosing makes the latter smaller. Here and . The Brunn–Minkowski inequality gives a lower bound at each value of ; it does not give the claimed monotonicity for arbitrary open sets.
Past exam of the mathematics course of the University of Cambridge 2017 ia Paper 4 2D a Solution Created 2026-09-24 Updated 2026-10-05
A binary relation on a set is a subset of its Cartesian product; means . It is an equivalence relation when it is a reflexive relation, a symmetric relation, and a transitive relation:An equivalence relation partitions into equivalence classes: two elements belong to the same class exactly when they are related.
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 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 and each set , the set 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 exist. These are finitely many first-order closure assertions with 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 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 and agree with the actual ones. Thus the first-order assertion is absolute whenever belong to a transitive structure satisfying : require that each member of has such a finite formula-and-parameter definition, and that each coded definition contributes a member of . Codes are finite objects; no truth predicate for the ambient universe is being used.
Write for the coded relative constructible stage assertion: is an ordinal and there is a function with domain , with , , at nonzero limit ordinals, and . Under , 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 formulaAll displayed abbreviations expand into first-order formulas of the membership language.
Suppose is transitive, , and . Let be the externally defined set of indices of stage codes in . It contains , is downward closed by restricting codes, and has no largest member by the last conjunct. Thus is a nonzero limit ordinal . Correctness of stage codes gives for , hence by transitivity. Conversely the exhaustion conjunct puts every in some such level. Therefore
For the converse, every with nonzero limit satisfies : 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 for are available in , the correct predicate defines their graph of endpoints as a subset of . No endpoint with can belong to , because would then give , contradicting Axiom of foundation. The defined graph therefore has domain exactly . Adjoining its final pair takes finitely many more stages. Together with finite successor extensions, this proves by transfinite induction that every belongs to for some finite .
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 129 3 Solution Created 2026-10-03 Updated 2026-10-05
Work in positive dimension . A cap set has no distinct zero-sum triple. Over the finite field , if two elements of a zero-sum triple agree then all three agree, since . Thus a zero-sum triple in a cap set must be diagonal. We prove the Ellenberg–Gijswijt cap-set bound by the polynomial method in combinatorics, keeping the exponential constant explicit and removing the fixed prefactor.
First prove the needed slice rank of a diagonal tensor over any field. The slice rank of a three-variable tensor is the least number of terms in a decomposition of the forms , , and . A diagonal tensor on a set of cardinality , with every diagonal entry nonzero, has slice rank at most by one slice for each entry. For the reverse inequality, suppose a decomposition has slices in the direction, in the direction, and in the direction, with . LetThe rank-nullity theorem gives . The maximum-support vector in a finite-dimensional subspace lemma supplies with at least nonzero coordinates: choose of maximum support of a vector; restriction must be injective, or adding a nonzero kernel of a linear map element would strictly enlarge that support of a vector. This argument is valid over finite fields, without any assumption that a generic vector avoids all coordinate hyperplanes.
Contract the proposed tensor decomposition in against . The diagonal tensor becomes a diagonal matrix of matrix rank at least . All slices vanish. Each remaining or slice becomes a matrix of matrix rank at most one, so subadditivity of matrix rank gives matrix rank at most , a contradiction. Therefore the slice rank of a diagonal tensor is exactly .
Now, for a cap set , consider the polynomialEach factor is one when its argument is zero and zero otherwise, because the two nonzero elements of have square one. Thus is the indicator function of . Restricted to , it is a diagonal tensor with every diagonal entry one, and its slice rank is .
Every monomial in the expansion has individual exponents at most two and total polynomial degree at most . Consequently at least one of its , , or blocks has polynomial degree at most . Assign each monomial to one such block, breaking ties in a fixed way, and collect assigned terms by the monomial in that block. Each collection is a slice. Ifthere are at most slices in each direction. Thus .
The low-degree monomial count for the cap-set bound follows directly from a weighted sum. Each exponent vector counted by satisfies , soThis supplies its own elementary exponential estimate; no unstated probabilistic estimate is required. Since , we have , but alone would leave a fixed prefactor.
Use Cartesian powers of cap sets to remove that prefactor. The -fold Cartesian product is still a cap set: in each block, a zero-sum triple of its elements must have all three entries equal. Hence . Taking th roots and letting tend to infinity proves the removal of an exponential prefactor by Cartesian powers:The strict middle inequality follows by cubing: . We can therefore takeFor every , a set with cannot be a cap set, and hence contains the required distinct triple. If zero dimension were included, the singleton would be another small-case exception; positive dimension is the convention used here.
Past exam of the mathematics course of the University of Cambridge 2019 ia Paper 2 4F Solution Created 2026-09-24 Updated 2026-09-29
Independence of random variables and the two unit-rate exponential distributions giveThe linear transformationhas determinant and inverseThe inequalities become . By the change-of-variables formula for probability densities,The variables and are not independent: the support of their joint density is a wedge rather than a Cartesian product of one-dimensional supports. For example, conditioning on a positive value of constrains to a finite interval depending on that value.
Past exam of the mathematics course of the University of Cambridge 2021 iii Paper 130 1 Solution 2026-09-28
Fix a number of colors. For a two-point set whose points are distance apart, take the vertices of a regular simplex with vertices and side length . The pigeonhole principle gives two vertices of one color, and they form the required congruent copy. Thus every two-point set, equivalently every line segment, is a Euclidean Ramsey set.
For an equilateral triangle of side length , take a regular simplex with vertices and side length . The pigeonhole principle gives three vertices of one color, and every three vertices of a regular simplex form an equilateral triangle. Hence every equilateral triangle is Euclidean Ramsey.
To prove the product theorem for Euclidean Ramsey sets, let be a finite Ramsey witness for under colors. There are at most possible color patterns on . Choose a finite Ramsey witness for under that many colors. Given a -coloring of , color each by the complete patternThere is a copy on which this pattern is constant. The common pattern on contains a monochromatic copy . Every point of then has the same original color, and the orthogonal product is congruent to .
A rectangle is the Cartesian product of two line segments, so it is Euclidean Ramsey. Three suitable vertices of a rectangle form a right triangle; any subset of a monochromatic set is monochromatic. Thus every right triangle is Euclidean Ramsey.
It remains to show that the collinear set behaves differently. In every , use the finite coloringA congruent copy has the form with for the Euclidean norm. The parallelogram law givesPut , , and . The errors introduced by the three floor functions show thatIf all three points had one color, the integer in the middle would be divisible by ten, which is impossible. This proves the three-term unit arithmetic progression is not Euclidean Ramsey assertion.
Past exam of the mathematics course of the University of Cambridge 2022 ia Paper 4 8F c Solution Created 2026-09-24 Updated 2026-09-25
Suppose first that for every . Then an element of is determined by its first coordinates, so is in bijection withA finite Cartesian product of countable sets is countable by repeated application of the diagonal enumeration in part (b)(i). Hence is countable.
Conversely, suppose infinitely many factors contain at least two elements. Choose increasing indices and distinct elementsFix one element in every remaining factor. Each binary sequence then defines an element of by placing in coordinate and the fixed element elsewhere. This map is injective.
The set is uncountable by Cantor's diagonal argument: from any proposed list of binary sequences, form a new sequence whose th digit differs from the th digit of the th listed sequence. It is absent from the list. Thus contains an uncountable subset and cannot be countable.
Therefore
Past exam of the mathematics course of the University of Cambridge 2023 iii Paper 130 4 Solution 2026-09-28
Let be the vertices of a regular polygon, indexed cyclically so that is an isometry. We first prove the product lemma needed for the cyclic-symmetry argument.
Suppose has the property that, for every number of colors, a finite witness forces a copy of on which the vertices corresponding to are monochromatic. We claim that for every there is a finite witness forcing an -invariant copy of . Proceed by mathematical induction on . The case is the assumption. For the step, choose a finite set that forces an -invariant for a coloring with colors, and choose that forces an -monochromatic for a coloring with colors.
Given a -coloring of , color by its complete vector . In the resulting copy of in , that vector is the same for every member of . Each can therefore be colored by the vector consisting of for one and the colors for . Applying the choice of gives an -invariant copy of , and its product with the chosen copy of in is the desired -invariant copy of . This proves the lemma rather than assuming it.
We now prove by induction on that a finite witness forces a copy of whose first vertices have one color. The case is trivial. For , use that a line segment is a Euclidean Ramsey set; each occurrence of a segment congruent to can be extended to a copy of the regular polygon, and only finitely many extensions are needed for a finite witness.
Assume the assertion for , and put . The product lemma lets us work inside an -invariantly colored copy of , with as large as required. For an increasing -element subset of and , define a word by putting in coordinate , with subscripts read modulo , and putting in every other coordinate. Color by the -tupleBy the Finite Ramsey theorem, for sufficiently large there are coordinates on which all -subsets have the same tuple color.
For , let be the word whose entries in coordinates arecyclically, and whose other entries are . For , the word differs from only in coordinate , where the two entries lie in . Similarly differs from only in coordinate , again by two members of . The -invariance and the homogeneous choice of the therefore giveHence have one color.
The cyclic words form an isometric copy of : in each of the varying coordinates the cyclic shift is an isometry, so every squared distance is multiplied by . Rescaling the finite witness by gives a copy of . The induction reaches , proving that every regular polygon is a Euclidean Ramsey set.
For three consecutive vertices of a regular -gon scaled to have side length one,Since the polygon is Euclidean Ramsey, choosing large enough proves that is an approximately Euclidean Ramsey set.
In fact every finite is approximately Ramsey. First perturb each coordinate of each point onto a sufficiently fine lattice , changing all pairwise distances by less than . For each coordinate, map the finitely many required integers to consecutive vertices of a very large regular polygon, scaled so that one angular step has arc length . If the step angle is , the chord replacing a difference of lattice steps has lengthas , uniformly over the finitely many differences involved. Taking the orthogonal Cartesian product of such polygons therefore embeds the perturbed points with a further distance error below . Each polygon is Euclidean Ramsey, and their product is Euclidean Ramsey by the product theorem for Euclidean Ramsey sets. A monochromatic copy of that product contains the corresponding approximate copy of , completing the proof.
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 4 16H b Solution Created 2026-09-24 Updated 2026-10-03
Under the axiom of choice, identify every infinite cardinal with its initial ordinal. We prove by transfinite induction on infinite cardinals. The countable case follows from the usual diagonal enumeration of .
For the induction step, well-order the Cartesian product by first comparingand then using lexicographic order among pairs with the same maximum. The predecessors of lie in , where . Put . If is infinite, the induction hypothesis makes this predecessor set have cardinal at most ; if is finite, the same conclusion is immediate.
Let be the order type of this well-order. Every proper initial segment of therefore has cardinal less than . Hence , since otherwise its initial segment of order type would have cardinal . Thus . The map gives the reverse injection, and the Cantor-Schröder-Bernstein theorem yields
Product forcing 2026-10-05
The conditions are pairs with coordinatewise extension: exactly when and . The projection of a product-generic filter is a pair of factor filters whose Cartesian product is the original filter. Each is ground-model generic, and mutual genericity for product forcing makes the second generic over the extension by the first.
Product of two spheres 2026-10-07
The Cartesian product has one cell in each of dimensions , counting the two middle cells separately when . For positive , its integral cohomology ring has generators of degrees , with and . The class is a product orientation class. This follows from the Künneth theorem.
Product set Created 2026-10-06 Updated 2026-10-07
The product set of two sets of real numbers is . It is a multiplicative counterpart of a sumset, not the Cartesian product .
Product theorem for Euclidean Ramsey sets Created 2026-09-24 Updated 2026-09-24
If finite point sets and are Euclidean Ramsey, then their orthogonal Cartesian product is Euclidean Ramsey. The proof first chooses a finite Ramsey witness for , colors a witness for by the complete color pattern it induces on the first witness, and then applies the two Ramsey properties in succession.
Suppose every cap set in has cardinality at most , with independent of . Applying this to the -fold Cartesian product of a fixed cap set gives . Taking th roots and letting tend to infinity proves . More generally this argument applies to any class of finite objects closed under products with multiplicative size and additive dimension.
Triangular prism Created 2026-09-24 Updated 2026-09-24