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.