Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 14 4 i by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 14 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
An ultrafilter on is a family satisfying the proper filter axioms: , , closure under finite intersections, and upward closure under inclusion. In addition, for every , exactly one of and belongs to . Equivalently, an ultrafilter is a maximal proper filter. The principal ultrafilter at consists of all subsets containing ; an ultrafilter not of this form is a nonprincipal ultrafilter.
To prove existence, start with the cofinite filter and order the proper filters containing it by inclusion. The union of a chain is still a proper filter: finitely many of its members lie in one filter of the chain, and no constituent contains the empty set. Thus Zorn lemma supplies a maximal such filter . If , adjoining cannot generate a proper filter; otherwise maximality fails. Consequently some has , so by upward closure. This proves the ultrafilter alternative. No finite can belong to , because is cofinite and already belongs to . In particular contains no singleton and is a nonprincipal ultrafilter. The same argument, starting from any proper filter, proves the ultrafilter lemma used below.
Define to be the set of all ultrafilters on , with basic open setsThey form a topological basis because and . Moreover , so they are clopen sets. This is the compact Hausdorff topology on ultrafilters. If , some belongs to but not , and then and are disjoint open neighbourhoods of the two points. Thus is Hausdorff.
For compactness, take an open cover and refine it by basic open sets . If no finite subfamily covers, then for every finite collection of indices the intersection is nonempty. Indeed, if that intersection were empty, the corresponding would cover , and every ultrafilter would contain at least one of them by the finite ultrafilter alternative. The complements therefore have the finite intersection property and generate a proper filter. Extend it to an ultrafilter by the proved ultrafilter lemma. Then for every , so belongs to none of the covering , a contradiction. A finite basic subcover lies inside a finite subcover of the original cover. HenceThe map , where is the principal ultrafilter at , identifies the discrete natural numbers with a dense subset: any nonempty has and contains for .
Hindman theorem states that every finite colouring of the positive integers admits an increasing sequence whose finite-sums setis monochromatic. We now give the Idempotent-ultrafilter proof of Hindman's theorem. For , write . The addition on is defined byTake an idempotent ultrafilter on the natural numbers , whose existence is allowed, so . It is a nonprincipal ultrafilter: addition of principal points is , whereas no positive integer satisfies .
Exactly one colour class belongs to . DefineBy idempotence, . The idempotent-ultrafilter star-set lemma needed for the recursion is that whenever . To prove it, put . Idempotence again givesFor , we have and , hence . Thus , proving the lemma by upward closure.
Choose . Suppose has been constructed. Every factor ofbelongs to : the translate factors do by the just-proved lemma, and the last factor does because it is cofinite and is a nonprincipal ultrafilter. The finite intersection is therefore nonempty. Choose in it. Then and every with lie in , so . This constructs a strictly increasing sequence, indeed , and proves Hindman theorem.
Finally apply Hindman theorem to obtain a monochromatic finite-sums set . We construct a divisibility chain inside a finite-sums set using disjoint successive blocks of indices. Start with . If , take unused terms after all indices used so far, and split them into two groups of consecutive terms. In each group its partial sums, including , contain two in the same congruence class modulo by the pigeonhole principle. Their difference is a nonempty consecutive sum divisible by , and positivity makes it at least . Let be the sum of these two selected sums. Then and .
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 14 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-11-05
Van der Waerden theorem says that for every pair of positive integers there is such that every finite colouring of using at most colours contains a monochromatic arithmetic progression of length and positive common difference. Consequently every finite colouring of contains arbitrarily long monochromatic arithmetic progressions.
Here is a colour-focusing proof of Van der Waerden theorem. Induct on , simultaneously for all . For , take . Suppose exists for every number of colours , and fix . We will construct finite bounds , , with the following property: every finite colouring of using at most colours contains either a monochromatic length- arithmetic progression, or length- arithmetic progressions of pairwise distinct colours, all focused at the same point . Specifically, their terms are“Focused” means that adjoining completes the corresponding length- arithmetic progression if has its colour.
For , put . Find a monochromatic length- arithmetic progression in the first points. Its next point is at most and supplies the focus. For , give the selected singleton common difference .
Suppose has been constructed. SetDivide into consecutive blocks of length . Colour the first block indices by their full colour profiles, that is, the ordered list of their colours. There are at most profiles, so the induction hypothesis on gives equally profiled blocks with indicesWhen , choose . Otherwise and , since the last selected block is at most and .
Assume the original finite colouring contains no monochromatic length- arithmetic progression. Applying the property of to the common profile gives focused length- arithmetic progressions at a position , with common differences and distinct colours . The colour of position differs from every : otherwise the profile already contains a length- monochromatic arithmetic progression, and so does any selected block.
Put and , a point in the original interval. For , the pointlies in a selected block at profile position , so has colour . Similarly has colour . Thus length- arithmetic progressions of distinct colours focus at . This proves the step in . At , the focus necessarily has the colour of one of the progressions, giving a monochromatic length- arithmetic progression. Hence exists, completing the mathematical induction and the proof of Van der Waerden theorem.
For the partition regularity deduction we first prove a strengthened progression lemma, the Brauer progression theorem: for positive with , there is such that every finite colouring of using at most colours contains a monochromatic setInduct on . For , take and . Given the result for , putVan der Waerden theorem supplies a colour- arithmetic progression , , inside . If some , , also has colour , take and use the terms . They are in the progression because .
Otherwise the integers , , use at most colours. Colour by the colour of and apply the induction hypothesis. It supplies a monochromatic set . Multiplying by gives the required configuration with and : its distinguished member is . All of these points are at most , so the finite bound is valid. This proves the Brauer progression theorem using only the just-proved Van der Waerden theorem.
A row is a partition regular matrix over the positive integers if every finite colouring of admits a positive vector whose coordinates have one colour and whose product with the row is zero. Coordinates may repeat. Since the coefficients are rational numbers, multiplying them by a common positive denominator leaves the equation and every zero subset sum unchanged, so write the row as nonzero integer coefficients .
To prove necessity, suppose no nonempty subset of the sums to zero. Choose a prime and use the last nonzero digit coloringwhere is the p-adic valuation. If positive all had the same colour and satisfied , let and . After division by and reduction modulo , the equation becomesAs , this says . The latter sum is nonzero and has absolute value at most , a contradiction. This explicitly proves the necessary obstruction without invoking a general partition regularity criterion.
Conversely, suppose and . Select an index , and putFor any finite colouring, the Brauer progression theorem gives one-coloured . The indices and both lie between and . Define positive, same-coloured coordinates byThenThis also covers equal to the whole index set and . Reversing the clearing of denominators proves the exact criterion:
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact





