# Section 1.7: Problem 4 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

In 1977 it was proved that every planar map can be colored with four colors. Of course, the definition of “map” requires that there be only finitely many countries. But extending the concept, suppose we have an infinite (but countable) planar map with countries
. Prove that this infinite planar map can still be colored with four colors. (

*Suggestion*: Partition the sentence symbols into four parts. One sentence symbol, for example, can be used to translate, “Country is colored red.” Form a set of wffs that say, for example, is exactly one of the colors. Form another set of wffs that say, for each pair of adjacent countries, that they are not the same color. Apply compactness to .)
We need a set
of wffs such that truth assignments that satisfy
correspond one-to-one to “correct” colorings of the graph. So, let
be the sentence symbol corresponding to the sentence “Country
is colored using color
”, where
and
. Then, first, we must ensure that every truth assignment satisfying
colors each country into a single color. For this, we consider the set of wffs
where
and
is a quaternary connective being true iff one exactly of its operands is true. Second, we must ensure that no two adjacent countries are colored the same color. For this, we consider the set of wffs
where
is the binary relation on the set of country indexes such that
iff countries
and
are adjacent, and
(
and
cannot both be painted using color
). Let
. Now, every truth assignment (every assignment of some colors for each country) that satisfies
corresponds to a correct coloring (exactly one color is assigned to each country, and no two adjacent countries share the same color). And vice versa, every correct coloring assigns exactly one color to each country
(satisfying
) and does not assign the same color
to two adjacent countries
and
(satisfying
). Now, if we show that every finite subset of
is satisfiable, we can apply the compactness theorem to conclude that
is satisfiable and a correct coloring exists. So, let us show that every finite subset of
is satisfiable. Let
be a finite subset of
. Let
be the (finite) set of country indexes used in
, i.e.

Now, we extend
to
by including
for all
, and
and
for all
such that
and
. The truth assignments that satisfy
correspond one-to-one to correct colorings of the finite subgraph
consisting of the countries with indexes in
. Since
is finite,
is finite, and according to the 4-color theorem for finite graphs, there is a correct coloring of
, i.e.
is satisfiable, and so is
.