So far, the nonstandard methodology has been applied to calculus, analysis,
and topology. This is to be expected, since the notions of infinitely small
and large numbers, infinitely close approximation, limiting concepts, etc.
belong to those subjects. But there are other areas of mathematics that
can be illuminated by the methodology of enlargement, and we will look
at one such now: the combinatorics of infinite sets.
17.1 Colourings and Monochromatic Sets
Let 01, ... , Cr be a finite sequence of pairwise disjoint sets and A a set
satisfying
(i)
If each of the sets Ci is finite, then so too is A. To put this another way:
• If A is infinite, then at least one of the Ci 's must be infinite.
This observation can be reformulated in the language of colourings. We
regard (i) as inducing a partition of the set A given by an assignment of
r different colours to the members of A. Then Bi = A n Ci is the set of
elements of A that are assigned colour i. In these terms we have we have:
• For any colouring of an infinite set A using finitely many colours,
there must be an infinite subset B of A that is monochromatic, i.e.,
all members of B get the same colour.
222 17. Ramsey Theory
This is the simplest case of a powerful principle known as Ramsey's theorem,
which has significant combinatorial applications and which forms the
basis of a subject called Ramsey theory. To formulate the general case we
introduce the notation [A]
k for the set of all k-element subsets of A (where
kEN):
[A]
k = {B A: IBI = k}.
Notice that if B A, then [B]k [A]k. Given a finite colouring
[A]k C1 u · · · u Cr
of the k-element subsets of A, a set B A is called monochromatic if all
its k-element subsets get the same colour, i.e., [B]k Ci for some i.
Ramsey's Theorem. IfA is infinite, then for any finite colouring of
[A]k
there exists an infinite monochromatic subset of A.
Here is an illustration of the use of this principle.
Theorem 17 .1.1 If ( P, ::; ) is an infinite partially ordered set, then P contains
a sequence (Pn : n EN) that is
· · ·
(1) strictly increasing: Pl < P2 < or
(2) strictly decreasing: Pl > P2 > or
· · ·
(3) an antichain, i.e., Pn and Pm are incomparable under the ordering :::::;
for all n f=. m.
Proof Take a colouring
of the 2-element subsets of Pin which
cb = {{p,q}o: p::; q or qo:::; p}
and
Cw = [P]2 Cb.
-
Thus Cb (the black sets) consists of pairs of elements that are comparable,
and Cw (white) consists of the incomparable pairs.
By Ramsey's theorem there is an infinite set Q P that is monochromatic
for this colouring. If [Qj2 Cw, then any sequence of distinct points
in Q will be an antichain fulfilling (3). If, however, [Q]2 cb, then Q is
an infinite chain, from which we can extract a sequence satisfying (1) or
(2). Indeed, if Q is not well-ordered by :::::;, then it must contain an infinite
decreasing sequence (2), and if it is well-ordered, then each of its nonempty
subsets has a least element, and we can use this fact to construct an in
creasing sequence (1) inductively.
1702 A Nonstandard Approach 223
17.2 A Nonstandard Approach
The proof of Theorem 17.1.1 reveals nothing about the structure of the
poset (P, ),nand leaves an air of mystery: we simply invoke this marvelous
new principle called Ramsey's theorem, and it delivers the set Q we need.
We do not see whether [Qj2 turned out to be black or white.
Here now is a nonstandard argument that does analyse the structure
of the partial ordering. We work in an enlargement of a universe 1U that
contains P and and in which members of Pare individuals. The extension
of the relation to * P will also be denoted by . It will be assumed that
P has a least element 0 and a greatest element 1 (we can always add such
elements and then take them away at the end to get the desired result).
Let 1r be a nonstandard member of * P in this enlargement (recall from
Section 14.1 that infinite sets from 1U always have such members). Put
L {pEP:p<1r},
U {pEP:p>7r}.
These sets are nonempty, since they contain 0 and 1 respectively. Several
cases are considered.
First, if L has no maximal member, then it must contain an increasing
sequence of the type ( 1) (p is maximal in L if there is no x E L with p < x).
Likewise, if U has no minimal member, it yields a decreasing sequence (2).
If neither of these cases holds, then L has a maximal element Ql and U has
a minimal element Qu. Since q1 < 1r < Qr, the statement
(:Jy E *P) (qz < Y < Qu)
is then true, and so by transfer it follows that the set
M = {p E P : qz < P < Qu}
is nonempty, and contains an element PI
· We will now inductively define
an antichain in M to complete the proof. The entity 1r belongs to * M and
is used to guide the construction of the antichain.
Assume that PI
, .n. Pn E M have been defined and are pairwise incom
0
parable. Now, M is disjoint from L, since all members of M are greater
than Ql
, which is maximal in L. Similarly, M is disjoint from U. But then
no member of M can be comparable with 1r, because an element of P that
is comparable with 1f must belong to L or U. Hence the statement
(:Jy E *M) (Pl i. Y i. P1 A · · · A Pn i. Y i. Pn)
is true (when y = 1r). By transfer it follows that there is some Pn+l E M
that is incomparable with each of p1, , Pn· This completes the inductive
0••
step, showing that we can indeed obtain (Pn : n E N) as an antichain in M.
224 17. Ramsey Theory
17.3 Proving Ramsey's Theorem
The essence of the inductive construction just given is that at each stage
the nonstandard element 1r ofn* M has the desired property (incomparability
with Pl
l ... , Pn), and so by existential transfer gives rise to a (standard)
element of M having the same property.
By an argument similar to this we can prove Ramsey's theorem itself, using
a nonstandard entity to guide the construction of a monochromatic set.
But first we observe that it is enough to obtain the resUlt for 2-colourings,
because the rest can be done by standard induction. Fixing the parameter
k, assume inductively that any r-colouring of a set of the form [B]k
with B infinite has an infinite monochromatic subset of B. Then given an
r + 1-colouring
[A]k C1 u u Cr+l,
···
·
put Cb = C1 u · ·u Cr and Cw = Cr+l to turn it into a 2-colouring. If
the 2-colouring case holds, then it yields an infinite monochromatic set
B A for this 2-colouring. If [B]k Cb
, then C1, ... , Cr induce an rcolouring
on [B]k that by the induction hypothesis on r has an infinite
monochromatic set B' B. Then B', being a subset of A, is an infinite
monochromatic set for the original (r + 1)-colouring of [A]k. If on the other
hand [B] k Cw = Cr+l, then B itself is a monochromatic set for the
( r + 1 )-colouring.
Thus we are reduced to proving Ramsey's theorem for 2-colourings
[A]
k Cb
UCw
for infinite sets A. Now we proceed by induction on the parameter k. The
case k = 1 is just the special case described at the beginning: [A]l can be
identified with A, via the correspondence {a} f.-+ a, and if A Cb U Cw,
then one of Cb and Cw must be infinite. For the inductive case, assume that
Ramsey's theorem holds for any 2-colouring of any set of the form [D]k.
Let
(ii)
be a 2-colouring of [A]k+I, with A infinite. Then the enlarged sets *Cb
and *Cw give a 2-colouring of [*A]k+I, i.e., the partition of (k +nI)-element
subsets of A into "black" and "white" extends to all ( k + 1 )-element subsets
of *A. To see this, observe that the fact that every (k + 1)-element subset
of A belongs to [A]
k+I can be expressed by the sentence
(Vai, ... ,ak+l E A)
(/\1ihk+I ai =I= aJ)
--+ (:Jz E [A]k+
l
) z = {a1, ... ,ak+I},
where "z = {a1, ... , ak+1}" abbreviates the formula
··· ···
a1 E z 1\ 1\ ak+l E z 1\ (Vx E z) (x = a1 V V x = ak+I
)·
17.3 Proving Ramsey's Theorem 225
By transfer of this sentence it follows that every (k + 1)-element subset of
*A belongs to *([A]k+1
):
[*A]k+I *([A]k+l
).
Exercise 17.3.1 Show that in fact, [*A]k+l = *(
[A]k+l). 0
Now by transfer of (ii),
*(
[A]k+1) *(Cb u Cw) = *Cb U *Cw
,
and *Cb and *Cw are disjoint, by transfer of the fact that Cb n Cw = 0.
Altogether then we get a 2-colouring
[*A]k+l c-*Cb u *Cw
of the claimed type.
Because A is infinite, it includes a denumerable subset, so we may as well
assume N nA. Now, let 1rE *N
-N be an unlimited hypernatural number.
Then 1r E *A, and we use 1r to control the construction of an increasing
sequence s1 < s2 < · · · of standard positive integers with the property
that whenever n1 < · · · < nk+b then
This property asserts that each member of the sequence behaves in relation
to its predecessors just like 1r.
If such a sequence exists, then putting D = { sn : n E N} A, a 2
colouring
of [D] k may be defined by
{snp· .. ,snk} E C iff {snp ... ,snk,1r} E *Cb, (v)
and C:V = [D]k
-C. (Here we list the members of any k-element subset of
D in increasing order.)
By the inductive assumption that Ramsey's theorem holds for k, it follows
that there is an infinite B D that is monochromatic for the colouring
(iv). But then B will also be our desired monochromatic set for (ii). For if
[B]k C, then [B]k+l Cb, because if
(iv)
(with n1 < · · · < nk+I
), then
{sn1, ... , Snk} E (B]k C
,
and so by (v),
226 17. Ramsey Theory
and hence by (iii),
Similarly, if [B]k C:V
, then [B]k+I Cw, because (iii) and (v) also imply
It remains now to construct a sequence of standard integers satisfying (iii).
Choose s1 < < sk arbitrarily. For n 2: k suppose inductively that
· · ·
s1, ... , sn have been defined in such a way that (iii) holds whenever n1 <
·· ·
< nk+I :::; n. We have to define Sn+I so that it behaves in relation to
its predecessors just like 1r. Thus Sn+I must satisfy the condition
(vi)
whenever n1 < < nk :::; n and
· · ·
(vii)
Likewise, sn+I must satisfy the condition
(viii)
whenever n1 < < nko:::; nnand
· · ·
(ix)
But there are only finitely many such conditions to be fulfilled, and so
our requirements can be expressed in a sentence of the formal language
-
associated with lU.
To facilite this we will list the members of any ( k + 1 )-element subset of
{s1, ... , sn} in increasing order, so that such (k + 1)-element subsets can
be identified with (k + 1)-tuples (sn1o, •••, Snk+1) having n1 < < nk+I·
· · ·
Now, let