Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 9 (Ramsey Theory)

Use $\mathbb{N}=\{1,2,\dots \}$. First recall the Ramsey theorem for r-sets in its infinite form: every finite colouring of the $r$-element subsets of an infinite countable set has an infinite homogeneous subset. Here is a proof, so the combinatorial input is explicit.

For $r=1$, this is the infinite pigeonhole principle. Suppose it holds for $r$. Given a colouring of $(r+1)$-sets, choose a first point $a_1$. Colour the $r$-sets in the remaining tail by adjoining $a_1$, and use the induction hypothesis to obtain an infinite tail on which that colouring is constant, with colour $d_1$. Choose $a_2$ from that tail and repeat, always thinning the unused tail. This produces increasing $a_i$, nested infinite reservoirs containing all later selected points, and colours $d_i$ such that every $(r+1)$-set of selected points whose least point is $a_i$ has colour $d_i$. Infinitely many $d_i$ are equal. Keeping the corresponding points gives an infinite homogeneous subset. This is a successive thinning proof of the infinite Ramsey theorem.

Now let $\chi$ be the given finite colouring of positive integers. Colour each unordered pair $\{a,b\}$, with $a<b$, by $\chi (a+2b)$. Apply the proved theorem with $r=2$, and enumerate its homogeneous set increasingly as $x_1<x_2<\cdots$. Thenfor one fixed colour $\gamma$. This proves the requested monochromatic pattern without requiring the $x_i$ themselves to have that colour.

For a positive integer $n$, let $v_2(n)$ be its 2-adic valuation and let $k(n)=\lfloor {\log }_{2}n\rfloor$. Use the four-colour dyadic valuation and scale colouringSuppose an increasing infinite sequence had all its two indicated kinds of pair sums in one colour. There are two exhaustive possibilities for its valuations.

If the valuations are bounded, infinitely many terms have one fixed valuation $t$. Among them, infinitely many have the same odd part modulo four. Choose two such terms $a<b$. Their odd parts have sum congruent to two modulo four, while the odd part of $a+2b$ is odd. HenceTheir first colour coordinates differ, contradicting monochromaticity.

If the valuations are unbounded, fix one term $a$ and choose a later $b$ with $2^{v_2(b)}>a$. Put $k=\lfloor {\log }_{2}b\rfloor$. The distance $2^{k+1}-b$ is a positive multiple of $2^{v_2(b)}$, so it exceeds $a$. Similarly $2^{k+2}-2b$ exceeds $a$. Therefore adding $a$ crosses neither upper dyadic boundary:Their second colour coordinates differ, again a contradiction. Thus this four-colouring admits no such increasing infinite sequence.

Apply the Ramsey theorem for r-sets, proved in part (i), with $r=4$ to the even positive integers. Colour the four-set $\{a,b,c,d\}$ with $a<b<c<d$ by $\chi (a+b+2c+2d)$. This gives increasing even integers $u_1<u_2<\cdots$ such that every such four-index expression has one colour $\gamma$.

For the simultaneous coefficient patterns from a homogeneous four-set colouring, setBoth sequences consist of positive integers and are strictly increasing. The evenness ensures that the shared half-prefix in $y_i$ is integral. For $i<j$, the two types of sum areandIn both expressions the four indices are strictly ordered, so their colour is $\gamma$. Therefore the union of the two families is monochromatic. The common half-prefix is what permits the second family to use the same coefficient pattern despite having different generating variables.

A rational matrix $A=(a_1\cdots a_n)$ is partition regular over the positive integers if every finite colouring of $\mathbb{N}$ admits a vector $x\in {\mathbb{N}}^n$ whose coordinates all have the same colour and satisfy $Ax=0$. Equal coordinates are allowed. Rado's theorem says that this holds exactly when the columns can be partitioned into nonempty blocks $I_0,\dots ,I_t$ withThis is the columns condition. Clearing an overall denominator lets us prove necessity for an integer matrix.

Suppose the columns condition fails. There are only finitely many ordered partitions of the finite column index set. For each ordered partition, choose a failing block: its sum $b_j$ is outside the rational span of preceding columns, with that span interpreted as zero for the first block. Finite-dimensional linear algebra gives a rational linear functional vanishing on that span but not on $b_j$. For completeness, take a basis of the span, append $b_j$, extend to a basis of the column space, and prescribe values zero on the first basis vectors and one on $b_j$. Clearing the functional's denominators gives an integer row functional $\ell$ with $\ell (b_j)\ne 0$.

Choose one prime $p$ larger than the absolute values of all these finitely many nonzero integers $\ell (b_j)$. Colour each positive integer by its first nonzero base-$p$ digit:Assume a monochromatic solution $x$ exists, and partition its coordinates into blocks of equal P-adic valuation, ordered by increasing valuations $v_0<\cdots <v_t$. Their first nonzero digit is a common $d\ne 0(\mathrm{mod}p)$. For this ordered partition take its chosen failing block $I_j$ and functional $\ell$. Apply $\ell$ to ${\sum }_i{a}_i{x}_i=0$. All preceding-block terms disappear exactly. Divide the remaining integer equation by $p^{v_j}$ and reduce modulo $p$. Later blocks disappear, while the current block givesThis contradicts the prime's choice. Thus the colouring has no monochromatic solution, proving necessity. This is the finite separating-functional proof of the columns condition; it needs neither a limiting argument nor a bound on the valuations themselves.

For sufficiency, suppose the blocks satisfy the columns condition. Choose rational coefficients $q_{ji}$, for $i$ in preceding blocks, such thatLet $c$ be a positive integer clearing their denominators, and choose an integer $P\ge 1$ bounding all $|c{q}_{ji}|$. Use the allowed monochromatic m-p-c set theorem with $t+1$ generators. We use the triangular convention in which the resulting positive integer set contains every numberin one colour. This is an m-p-c set, with the generator indices reversed if the alternative lower-triangular convention is used. The permitted theorem applies to either convention, since it applies to every finite number of generators. Its set lies in $\mathbb{N}$, so all of the displayed combinations are positive.

For $i\in I_j$, defineEach coordinate belongs to that monochromatic set. Summing the column contributions and collecting coefficients of $u_k$ givesFor $k=0$ the inner sum is empty and $b_0=0$. This proves sufficiency by a Rado solution inside an m-p-c set, and completes the theorem.

For the requested application, chooseThe matrix, in the coordinate order $(x,y,z,w)$, has columnsThe block $I_0=\{x,z,w\}$ has zero sum. The remaining column satisfies $a_y=-a_z/3+2a_w$, so it is in the span of the first block. By Rado's theorem, positive monochromatic $x,y,z,w$ satisfy the system. In particular,One can see the positivity directly in the same triangular construction: a monochromatic set containing $3u+\lambda v$ for $|\lambda |\le 6$, together with $3v$, givesAll four are positive because they belong to that positive m-p-c set. This is a partition-regular system forcing an ordered Schur relation.

A proper filter on a set $\mathcal{F}$ on $\mathbb{N}$ contains $\mathbb{N}$, excludes the empty set, is closed under finite intersections and is upward closed under inclusion. An ultrafilter is a maximal proper filter. Equivalently, for every $A\subseteq \mathbb{N}$ it contains exactly one of $A,A^c$. To see maximality implies this dichotomy, if $A$ is absent then adjoining it must make the generated filter improper; hence some filter member is disjoint from $A$, forcing $A^c$ into the filter. Conversely, a filter with this dichotomy cannot be properly enlarged without acquiring disjoint members.

Extend the cofinite filter to a maximal proper filter using Zorn's lemma. Every chain of proper extensions has its union as a proper filter upper bound: any finite collection of its members lies in one member of the chain, and the empty set never enters. The resulting ultrafilter contains no finite set, because it already contains that set's cofinite complement. It is therefore a free ultrafilter, or nonprincipal ultrafilter. This proves the required existence with the usual choice principle explicit.

Define the Stone-Čech compactification of the natural numbers as the set of all ultrafilters, with basic open setsThey form a basis because $\hat{\mathbb{N}}$ is the whole space and $\hat{A}\cap \hat{B}=\widehat{A\cap B}$. Also $(\hat{A}{)}^c=\widehat{A^c}$, so each basic set is clopen. Distinct ultrafilters disagree on some $A$, putting them in the disjoint open sets $\hat{A}$ and $\widehat{A^c}$. Thus this space is Hausdorff.

To prove compactness, suppose an open cover has no finite subcover and refine it by basic sets $\widehat{A_i}$. Their complements $B_i=\mathbb{N}\setminus A_i$ have the finite intersection property: otherwise finitely many $\widehat{A_i}$ would cover every ultrafilter. Here a nonempty finite intersection of the $B_i$ has a principal ultrafilter containing it, whereas an empty intersection cannot belong to any proper filter. The $B_i$ therefore generate a proper filter, which extends to an ultrafilter by the same Zorn argument. That ultrafilter lies outside every $\widehat{A_i}$, contradicting the cover. Hence $\beta \mathbb{N}$ is compact and Hausdorff. Natural number $n$ is identified with its principal ultrafilter.

Hindman's theorem asserts that every finite colouring of the positive integers has an increasing sequence $x_1<x_2<\cdots$ for which all nonempty finite sums of distinct terms have one colour. Let $\mathcal{U}+\mathcal{U}=\mathcal{U}$ be the given idempotent ultrafilter. Since $\mathbb{N}$ is positive, a principal ultrafilter cannot be idempotent: its sum with itself is principal at $2n$, not $n$. Thus $\mathcal{U}$ is nonprincipal and contains every cofinite tail. In a convention including zero, one instead uses an idempotent in the nonprincipal part, excluding the trivial principal idempotent at zero.

For $A\subseteq \mathbb{N}$ define $A-n=\{m:n+m\in A\}$. Addition on the Stone-Čech compactification of the natural numbers is characterized byOne cell $A$ of the finite colour partition belongs to $\mathcal{U}$. PutIdempotence makes $A^{\ast }\in \mathcal{U}$. Moreover, if $n\in A^{\ast }$, then $A^{\ast }-n\in \mathcal{U}$. Indeed, write $B=\{y:A-y\in \mathcal{U}\}$ so $A^{\ast }=A\cap B$. We have $A-n\in \mathcal{U}$, and idempotence applied to that set givesTheir intersection is $A^{\ast }-n$. This is the idempotent-ultrafilter star-set lemma.

Choose $x_1\in A^{\ast }$. If the finite-sums set $F_k$ of the first $k$ choices lies in $A^{\ast }$, selectEvery factor belongs to $\mathcal{U}$, so this finite intersection is nonempty. Its choice preserves $F_{k+1}\subseteq A^{\ast }$. ThereforeThis proves the requested Idempotent-ultrafilter proof of Hindman's theorem, without assuming an idempotent-existence proof.

Finally, for the first logical assertion put $P=\{x:p(x)\}$ and $Q=\{x:q(x)\}$. A proper filter contains $P\cap Q$ if and only if it contains both $P$ and $Q$: one direction is finite-intersection closure and the other is upward closure. Thus (i) is always true. This is the conjunction law for filter quantifiers.

Membership of either truth set in a filter on a set implies membership of its union, by upward closure. The converse need not hold. For the cofinite filter, take $p(x)$ to mean that $x$ is even and $q(x)$ that $x$ is odd. The union of their truth sets is all of $\mathbb{N}$, while neither truth set is cofinite.

Thus the left side of the printed equivalence is true and its right side false: (ii) can be false. An ultrafilter does satisfy the equivalence, because its dichotomy forces one member of a finite union into the ultrafilter. General filters need not have that dichotomy. This is one aspect of the Boolean failure of the cofinite-filter quantifier.

If the complement of a truth set belongs to a proper filter on a set, the truth set itself cannot belong: their intersection is empty. Hence the right side always implies the left side.

The reverse implication can fail. In the cofinite filter, the set of even integers is absent, but its odd complement is absent as well. The filter-quantified evenness assertion is false, while the filter-quantified assertion of oddness is also false. Therefore (iii) can be false.

For an ultrafilter the equivalence is true, precisely because it contains exactly one of any set and its complement. The filter quantifier preserves conjunction for arbitrary proper filters, but its full classical Boolean behaviour requires the ultrafilter property.

Define $D_{\mathcal{G}}(A)=\{x:A-x\in \mathcal{G}\}$. The proposed addition of filters on the natural numbers isBecause addition of positive integers stays in $\mathbb{N}$, $D_{\mathcal{G}}(\mathbb{N})=\mathbb{N}$ and $D_{\mathcal{G}}(\varnothing )=\varnothing$. Thus the sum contains the whole set and excludes the empty set. If $A\subseteq B$, upward closure of $\mathcal{G}$ gives $D_{\mathcal{G}}(A)\subseteq D_{\mathcal{G}}(B)$, so upward closure of $\mathcal{F}$ gives upward closure of the sum.

Finally, for every $x$,The conjunction property for $\mathcal{G}$ proved in (i) consequently givesFinite-intersection closure of $\mathcal{F}$ proves the same closure for its sum. All proper-filter axioms hold, so (iv) is always true. No ultrafilter assumption is needed here.

Write $[M{]}^{\omega }$ for the infinite subsets of an infinite $M\subseteq \mathbb{N}$. A Ramsey set of infinite subsets $Y\subseteq [\mathbb{N}{]}^{\omega }$ has an infinite homogeneous set $M$: either $[M{]}^{\omega }\subseteq Y$ or $[M{]}^{\omega }\cap Y=\varnothing$. The proof below actually supplies homogeneous refinements within every infinite reservoir, and with any fixed initial finite stem; this stronger property is that of a completely Ramsey set.

For a non-Ramsey example, identify two infinite sets when their symmetric difference is finite, and choose one representative $R$ for each equivalence class. Define a two-colouring bywhere $R$ is the representative of $A$'s class. Removing one point changes this parity. Thus, for every infinite $M$, the two subsets $M$ and $M\setminus \{\min M\}$ have opposite colours. The zero-colour family meets every $[M{]}^{\omega }$ and so does its complement. Hence the zero-colour family is not Ramsey. This finite-symmetric-difference parity colouring uses a choice of representatives; no definability or regularity is being claimed for that first example.

To prove the open-set assertion, for a finite increasing set $s$ and an infinite tail $A$ above $\max s$ defineThe star topology, or Ellentuck topology, has these sets as basic open sets. For an empty stem there is no lower-bound restriction. More generally $[s,A]$ always uses only the points of $A$ above $\max s$. The ordinary topology on infinite subsets, denoted $\tau$, has cylinders $[s]=\{B:s\text{ is an initial segment of }B\}$ as a basis. The two topologies must not be confused.

Fix any family $Y$, initially without any openness assumption. An infinite $A$ accepts a stem $s$ if $[s,A]\subseteq Y$, and rejects it if no infinite subset of its tail accepts $s$. Every infinite reservoir has an infinite refinement deciding $s$: take an accepting refinement if one exists, and otherwise the reservoir itself rejects. Acceptance and rejection are both inherited by infinite refinements. These facts follow from the definitions, giving acceptance and rejection of finite stems.

First refine the initial reservoir to decide the empty stem. If it accepts, its infinite subsets already lie in $Y$. Otherwise start from an infinite reservoir rejecting the empty stem. Choose an increasing point $a_1$, then thin its remaining tail finitely many times to decide all subsets of $\{a_1\}$. Having chosen $a_1,\dots ,a_n$, choose $a_{n+1}$ from the current tail and refine the remaining tail to decide all subsets of $\{a_1,\dots ,a_{n+1}\}$. Each stage has only finitely many stems to handle. Let $L=\{a_1,a_2,\dots \}$.

For every finite $s\subset L$, at the stage of its largest point the reservoir was made to decide $s$, and all later chosen points remain inside that reservoir. Heredity therefore makes the tail of $L$ decide $s$. Moreover $L$ still rejects the empty stem. This proves deciding all finite stems by fusion without assuming a separate fusion theorem.

Suppose $L$ rejects a finite $s\subset L$. There are only finitely many $a\in L$ above $\max s$ for which $L$'s tail above $a$ accepts $s\cup \{a\}$. For if there were infinitely many, collect them into $C$. Every infinite $B\subset C$ has least point $a$ of this kind, and its remaining tail lies in the accepting tail of $L$. Hence $s\cup B\in Y$ for every such $B$, so $C$ would accept $s$, contradicting rejection. This proves finitely many accepting extensions of a rejected stem.

Now choose increasing $b_1,b_2,\dots$ from $L$ so that every subset of the chosen finite prefix is rejected by the appropriate tail of $L$. The empty prefix is rejected. At the next step, for each of the finitely many already chosen subsets $s$, avoid the finitely many accepting successors just identified. All other successors are rejected, since the previous fusion made every finite stem in $L$ decided. Thus one can choose the next point beyond the finite forbidden union. With $M=\{b_1,b_2,\dots \}$, every finite $s\subset M$ is rejected.

Now assume $Y$ is star-open. If some infinite $B\subset M$ lay in $Y$, there would be a basic neighbourhood $[s,A]\subseteq Y$ containing $B$. Here $s$ is a finite initial segment of $B$, and its infinite tail $C=B\setminus s$ lies in $A$ and in the relevant tail of $L$. Then $[s,C]\subseteq [s,A]\subseteq Y$, so $C$ accepts $s$, contradicting rejection. Therefore $[M{]}^{\omega }\cap Y=\varnothing$. In the earlier acceptance case, $[M{]}^{\omega }\subseteq Y$. We have provedThe construction works with any infinite starting reservoir. Keeping an initial finite stem fixed and applying the same acceptance/rejection argument to its tails proves the completely Ramsey set conclusion as well. This supplies the full fusion proof for open Ellentuck sets; no unproved course combinatorial lemma has been used.

For the final request, a family has the Baire property in the ordinary infinite-subset topology if it differs from a $\tau$-open family by a $\tau$-meagre set. We construct a non-Ramsey family which is already $\tau$-nowhere dense. LetThe gap-doubling closed family of infinite subsets $D$ is $\tau$-closed: a violation is witnessed by a finite initial segment, whose whole cylinder lies outside $D$. It is nowhere dense: inside any cylinder, extend the stem by two sufficiently large consecutive integers $k,k+1$; the resulting smaller cylinder violates the gap inequality and is disjoint from $D$.

For every infinite $M$, the set $D\cap [M{]}^{\omega }$ has cardinality $\mathfrak{c}=2^{{\aleph }_0}$. To prove the lower bound, build a binary tree of finite gap-doubling sequences using points of $M$, choosing two distinct next points above twice the previous point at every node. Distinct infinite binary branches give distinct increasing sets. The upper bound follows because all these sets are subsets of the countable set $\mathbb{N}$.

Well-order all infinite subsets as $(M_{\alpha }{)}_{\alpha <\mathfrak{c}}$, using the initial ordinal of that cardinality. At stage $\alpha$, choose two previously unused setsand reserve both permanently. There are fewer than $\mathfrak{c}$ previously reserved sets but $\mathfrak{c}$ candidates, so this recursion always continues. This argument does not assume that the continuum is a regular cardinal. Set $X=\{R_{\alpha }:\alpha <\mathfrak{c}\}$. Every cone $[M_{\alpha }{]}^{\omega }$ contains its red choice in $X$ and its blue choice outside $X$; the blue choices can never become later red choices. Therefore $X$ is not Ramsey.

But $X\subseteq D$, and $D$ is closed nowhere dense, so the closure of $X$ also has empty interior. Thus $X$ is nowhere dense, hence meagre, and $X△\varnothing =X$ proves its ordinary Baire property. We have obtained a meagre set meeting every Ramsey cone in both colours:This explains why ordinary Baire regularity cannot replace the star-topology regularity in the open-set theorem. A family supported only on the infinite subsets of a fixed sparse set would not suffice for this counterexample: another infinite set could give an entirely disjoint cone. The gap-doubling family used here instead meets every cone in continuum many candidates.