In some nonstandard frameworks there are infinite sets that can be "approximated"
by hyperfinite sets. From the discussion in Chapter 14 we
know that in an enlargement of a universe over a set A there will be a
hyperfinite set B with
A B o*A.
This phenomenon suggests a new methodology for analysing infinite structures
by "lifting" a corresponding analysis that is known for finite ones.
The steps involved are as follows:
(1) Obtain information about finite structures by standard reasoning.
(2) Use transfer to lift this to hyperfinite structures, including the set B
above.
(3) Find some way of "pushing down" the results from B to the infinite
set A.
This procedure will now be illustrated with three applications: colouring of
graphs, representation of Boolean algebras, and the Hahn-Banach theorem
about extensions of linear functionals on vector spaces. For the first two
of these, the pushing-down step (3) is immediate. For the Hahn-Banach
theorem, however, it requires a little further nonstandard analysis in the
form of an appeal to the shadow map.
260 19. Hyperfinite Approximation
19.1 Colourings and Graphs
An r-colouring of a set G is a sequence C1, ... , Cr of pairwise disjoint sets
satisfying
Thus each member of G belongs to exactly one of the sets Ci. This situation
induces a partition of G, which we regard as being given by an assignment
of r different colours to the members of G. G n Ci is the set of elements of
G that are assigned colour i ( cf. Section 17.1).
Notice that the way we have defined this notion ensures that any rcolouring
of G is also an r-colouring of any subset of G.
In any nonstandard framework for G we will get
with *Ci n *Cj = 0 whenever i # j. Hence the enlarged sets *C1, ... , *Cr
form an r-colouring of *G, which moreover agrees with the original colouring
when restricted to G.
A graph is a structure ( G, E) comprising a nonempty set G with a binary
relation E on G that is irreflexive and symmetric:
(Vx E G) (x, x) ¢. E,
(Vx,ny E G) ( (x,y) E En--+ (y,x) E E).
This is visualised as a collection of nodes, or vertices, labelled by the members
of G, with a line connecting the nodes labelled by x and y whenever
(x, y) E E. A pair (x, y) that belongs tonE is called an edge with vertices x
andoy.
Any subset H of G defines the subgraph of (G, E) determined by retaining
just those edges whose vertices both belong to H. In other words, there is
a line connecting x and y in this subgraph precisely when x, y E H and
(x,y) E E.
In a nonstandard framework for G the structure (*G, *E) is a graph,
since transfer ensures· that * E is irreflexive and symmetric: Moreover, the
subgraph of this enlarged graph defined by G is just the original graph
(G, E), because
( x, y) E E iff ( x, y) E *E
for each x, y E G by transfer (note here that *(x, y) = (*x, *y) = (x, y),
since x andny are individuals in a nonstandard framework for G).
An r-colouring of a graph is an r-colouring of its set of nodes with the
additional property that the vertices of any edge have different colours, i.e.,
19.1 Colourings and Graphs 261
there is no line connecting two nodes of the same colour. This requires that
each of the statements
(Vx, y E G) ( (x, y) E E 1\ x E Ci y Ci)
must hold true forni= 1, ... , r. An r-colouring of any graph is automatically
an r-colouring of any of its subgraphs.
Now, the assertion
"C1, ... , Cr is an r-colouring of (G, E)"
can be expressed by a formula that we abbreviate as
Colour( C1, ... , Cn G, E).
If 01(, ... , Cr, G, E are all taken to be constants naming particular entities
in a universe over G, then this formula is a sentence whose *-transform
asserts that *Cb ... , *Cr is an r-colouring of the enlarged graph (*G, *E). If,
however, we take 01(, .n. , Cr to be variables, then we can form the sentence
.
(301, .o. , Cr E P(G)) Colour(C1, ... , Cn G, E),
.
which states that there exists an r-colouring of (G, E). This can be modified
further to express the assertion that every finite subgraph of (G, E) has an
r-colouring: replace G by a variable H and form
(VH E PF(G)) (301, ... , Cr E P(G)) Colour(C1, ... , Cr, H, E). (i)
Note that for (i) to be true it is required only that each finite subgraph
have its own r-colouring. The colourings of different finite subgraphs need
not agree with each other, so it is not obvious from (i) that the whole graph
(G, E) can itself be r-coloured. Nonetheless, it is true that
• if every finite subgraph of a graph has an r-colouring, then the graph
itself has an r-colouring.
A proof of this result will now be given by a simple application of the
hyperfinite approximation methodology. We work in an enlargement of a
universe over G, and observe first that by applying transfer to (i) we can
infer that each member of *PF(G) defines a subgraph of (*G, *E) that has
an r-colouring. Thus the fact that every finite subgraph of ( G, E) has an
r-colouring can be lifted to the conclusion that
every hyperfinite subgraph of (*G, *E) has an r-colouring.
But in the enlargement there is a hyperfinite approximant of G, i.e., a set
HE *PF(G) with G H o*G. Then the subgraph of (*G, *E) defined by
H has an r-colouring, and it remains only to push this situation down to
(G, E) itself. But this is immediate, since (G, E) is a subgraph of the graph
defined by H, so the r-colouring of H is also an r-colouring of ( G, E).
Exercise 19.1.1
Write out explicitly the formula Colour(C1, ... , Cn G, E).
262 19. Hyperfinite Approximation
19.2 Boolean Algebras
George Boole (1815-1864) was a pioneer of mathematical logic. He showed
that the study of logical connectives, and the validity of inferences, could
be carried out by a mathematical analysis of equations involving operations
that constitute what we now refer to as Boolean algebra.
To explain this, consider first the collection P(A) of all subsets of a set
A. This is closed under the binary operations n and U of intersection and
union of sets, and under the unary operation -of complementation relative
to A. The structure
(P(A); n, U, , 0, A)
-
is the power set algebra of A. More generally, a field of sets is any nonempty
collection B of subsets of a set A (i.e., B P(A)) that is closed under n,
U, andn-. Then
(B; n, U, .,...., 0, A)
is a subalgebra of the power set algebra of A.
These are concrete examples of the abstract notion of a Boolean algebra,
which can be defined as any structure
(B; n, u, ', o, 1)
in which B is a nonempty set that contains elements 0 (the zero) and 1
(the unit) and carries binary operations n and U and a unary operation 1
such that the following equations hold for all x, y, z in B:
xny ynx,
xUy yUx,
x n (y u z) (xny)u(xnz),
xu (y n z) (xuy)n(xuz),
xn1 x,
xUO x,
X nx' 0,
x Ux' 1.
From these many other properties are deducible, including
xnx x,
xux x,
x n (y n z) (xny)nz,
xU (y U z) (xuy)Uz,
xU(ynx) x,
19.2 Boolean Algebras 263
x n (y u x) x,
(x n y)' x' U y',
(xU y)' x' n y',
xU1 1,
xno 0,
' 1,
1' 0,
x n y' = o iff xny = x.
The element x n y is called the meet of x and y, while x U y is their join.
A relation is defined in any Boolean algebra by
X y iff X n y = X (iff X U y = y iff Xn y' = 0).
Thenn proves to be a partial ordering (reflexive, transitive, antisymmetric)
in which the meet x n y is the greatest lower bound of x and y, and the
join x U y is the least upper bound. In a field of sets, is the relation of
set inclusion.
Notice that in any nonstandard framework fornB, the operations n, U, 1
will extend to corresponding operations on *B, for which we continue to use
the same symbols. The Boolean algebra axioms hold for these operations by
transfer, and so *B becomes a Boolean algebra having Bas a subalgebra.
Of singular importance is the two-element algebra based on the set {0, 1},
in which 1 is identified with "true" and 0 with "false"n, and n, U, 1 are the
operations specified by the truth tables that give the usual meanings of the
logical connectives /\, V, '
This algebra is denoted by 2. It is isomorphic
to the power set algebra
·
of any one-element set {a}, identifying 1 with
{a} and 0 with 0. The algebra 2 is a fundamental building block: from
the representation to be discussed below it can be shown that any Boolean
algebra is isomorphic to a subalgebra of an algebra that is constructed as
a direct product of copies of 2. This implies that any equation satisfied by
2 will be satisfied by every Boolean algebra.
Now, the properties of the set operations n, U,(-follow from their definitions,
CnD -{x : x E C and x E D},
CUD {X : X E C or X E D},
-C {x E A : not x E C},
-
and hence depend on the meaning of the words and, or, not. Thus it is the
behaviour of these logical connectives that dictate that P(A) should be a
Boolean algebra, indicating a natural connection between the algebra of sets
and the algebra of connectives. This is further exemplified by a construction
that builds Boolean algebras out of formulae. Let II be a nonempty set,
264 19. Hyperfinite Approximation
whose members will be called sentence letters, and consider the class of
II-formulae generated inductively from members of II by the connectives
1\, V, ---,, , f--7. A II -valuation is a function v : II { 0, 1} assigning a truth
value to each sentence letter. Any valuation extends in a unique way to all
formulae by the usual truth conditions:
v(•