# Section 2.5: Problem 5 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

Show that an infinite map can be colored with four colors iff every finite submap of it can be.

*Suggestion*: Take a language having a constant symbol for each country and having four one-place predicate symbols for the colors. Use the compactness theorem.
This is related to Exercise 4 of Section 1.7. There, we would introduce sentence symbols
, where
would mean that country
is colored with color
, and form two groups of sentences, one group consisting of
with
iff exactly one of
,
, is true (exactly one color is applied to each country), and the other group consisting of
, for such
and
that countries
and
are adjacent, with
iff no more than one of
and
is true (adjacent countries cannot be colored the same color). We would then use the compactness theorem of sentential logic to argue that as long as any finite subset of the set
of all sentences
and
can be satisfied,
can be satisfied as well.

In our case, we form a first-order language and a set of sentences
to describe colorings of maps, and apply the compactness theorem. Instead of a sentence symbol
we are going to use an atomic formula
equal to
so that all such atomic formulas are distinct. We then form sentences
(
) and
(
) from
’s as before, and
. Here,
can be thought of as a set of points representing all countries (and possibly some other points), then
is a point in
representing country
, and
is a subset of points in
colored with color
. The sentence
ensures that exactly one of the relations
holds for
(the point corresponding to country
is colored with exactly one color), and
ensures that the relation
does not hold for both points
and
(at least one of the points corresponding to adjacent countries
and
is not colored with color
). Now,
is a model of
iff [the coloring where country
is colored with color
iff
] is correct. And according to the corollary of the compactness theorem,
has a model iff every finite subset of
has a model. So, if a correct coloring of the infinite graph exists, then
has a model, and, hence, every its finite subset has a model, in particular, the finite subset of
corresponding to correct colorings of some fixed finite subgraph has a model, i.e. the finite subgraph has a correct coloring. And vice versa, if every finite subgraph has a correct coloring, then, similar to the sentential logic, given a finite subset
of
, we, first, extend it to a finite subset
that includes all sentences from
and all sentences corresponding to a correct coloring of some finite subgraph, and then argue that a model of
(and, hence,
) exists, therefore, by compactness, a model of
exists, and the infinite graph has a correct coloring (the details of this second part are similar to Exercise 4 of Section 1.7).

Now, unlike how it is suggested, a more interesting question is whether we can manage to obtain a similar result with a finite language by utilizing the full power of first-order languages. Here, we can use the infinite number of variables instead of constants to assign colors. So, assume that
is the set of four colors (one sentence
). Then the assignment
represents a coloring of countries where we ensure that each country is colored with one color just by definition, since
is a function (so, we don’t need an analogue of
’s at all). Further, for each pair of adjacent countries
and
we simply add one wff stating that
. This wff ensures that the two adjacent countries are assigned different colors. And that is it! A structure
satisfies
with
iff
contains no more than 4 points (colors) and each variable
(country
) is assigned a point in
(a color) by
such that no two adjacent countries share the same color. And we can then apply the compactness theorem the same way to state that
is satisfiable iff every finite subset of
is satisfiable.