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 .