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 sets
They 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. Hence
The 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 set
is monochromatic. We now give the Idempotent-ultrafilter proof of Hindman's theorem. For , write . The addition on is defined by
Take 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 . Define
By idempotence, . The idempotent-ultrafilter star-set lemma needed for the recursion is that whenever . To prove it, put . Idempotence again gives
For , we have and , hence . Thus , proving the lemma by upward closure.
Choose . Suppose has been constructed. Every factor of
belongs 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 .
The index set defining lies strictly after all previous index sets. Discard the other terms in these two groups before continuing. Because the chosen index sets are disjoint, every finite sum of distinct is a finite sum of distinct , retaining the same colour. Therefore
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. Set
Divide 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 indices
When , 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 point
lies 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 set
Induct on . For , take and . Given the result for , put
Van 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 coloring
where is the p-adic valuation. If positive all had the same colour and satisfied , let and . After division by and reduction modulo , the equation becomes
As , 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 put
For any finite colouring, the Brauer progression theorem gives one-coloured . The indices and both lie between and . Define positive, same-coloured coordinates by
Then
This 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!
We have two killer features:
  1. 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-calculus
    Articles 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/derivative
  2. 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.
    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.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
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