This is related to Exercise 4 of Section 1.7. There, we would introduce sentence symbols $A_{i,j}$ , where $v(A_{i,j})=T$ would mean that country $i$ is colored with color $j$ , and form two groups of sentences, one group consisting of $B_{i}$ with $\overline{v}(B_{i})=T$ iff exactly one of $v(A_{i,j})$ , $j\in\{1,2,3,4\}$ , is true (exactly one color is applied to each country), and the other group consisting of $D_{i,j,k}$ , for such $i$ and $k$ that countries $i$ and $j$ are adjacent, with $\overline{v}(D_{i,j,k})=T$ iff no more than one of $v(A_{i,j})$ and $v(A_{k,j})$ 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 $\Sigma$ of all sentences $B_{i}$ and $D_{i,j,k}$ can be satisfied, $\Sigma$ can be satisfied as well.

In our case, we form a first-order language and a set of sentences $\Gamma$ to describe colorings of maps, and apply the compactness theorem. Instead of a sentence symbol $A_{i,j}$ we are going to use an atomic formula $\alpha_{i,j}$ equal to$P_{j}c_{i}$ so that all such atomic formulas are distinct. We then form sentences $\beta_{i}$ ($B_{i}$ ) and $\delta_{i,j,k}$ ($D_{i,j,k}$ ) from $\alpha_{i,j}$ ’s as before, and $\Gamma=\{\beta_{i},\delta_{i,j,k}\}_{i,j,k}$ . Here, $|\mathfrak{A}|$ can be thought of as a set of points representing all countries (and possibly some other points), then $c_{i}^{\mathfrak{A}}$ is a point in $|\mathfrak{A}|$ representing country $i$ , and $P_{j}^{\mathfrak{A}}$ is a subset of points in $|\mathfrak{A}|$ colored with color $j$ . The sentence $\beta_{i}$ ensures that exactly one of the relations $P_{j}^{\mathfrak{A}}$ holds for $c_{i}^{\mathfrak{A}}$ (the point corresponding to country $i$ is colored with exactly one color), and $\delta_{i,j,k}$ ensures that the relation $P_{j}^{\mathfrak{A}}$ does not hold for both points $c_{i}^{\mathfrak{A}}$ and $c_{k}^{\mathfrak{A}}$ (at least one of the points corresponding to adjacent countries $i$ and $k$ is not colored with color $j$ ). Now, $\mathfrak{A}$ is a model of $\Gamma$ iff [the coloring where country $i$ is colored with color $j$ iff $<c_{i}^{\mathfrak{A}}>\in P_{j}^{\mathfrak{A}}$ ] is correct. And according to the corollary of the compactness theorem, $\Gamma$ has a model iff every finite subset of $\Gamma$ has a model. So, if a correct coloring of the infinite graph exists, then $\Gamma$ has a model, and, hence, every its finite subset has a model, in particular, the finite subset of $\Gamma$ 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 $\Gamma_{0}$ of $\Gamma$ , we, first, extend it to a finite subset $\Gamma'$ that includes all sentences from $\Gamma_{0}$ and all sentences corresponding to a correct coloring of some finite subgraph, and then argue that a model of $\Gamma'$ (and, hence, $\Gamma_{0}$ ) exists, therefore, by compactness, a model of $\Gamma$ 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 $|\mathfrak{A}|$ is the set of four colors (one sentence $\forall v_{1}\ldots\forall v_{5}v_{1}=v_{2}\vee v_{1}=v_{3}\vee\ldots\vee v_{4}=v_{5}$ ). Then the assignment $s:V\rightarrow|\mathfrak{A}|$ represents a coloring of countries where we ensure that each country is colored with one color just by definition, since $s$ is a function (so, we don’t need an analogue of $B_{i}$ ’s at all). Further, for each pair of adjacent countries $i$ and $k$ we simply add one wff stating that $\neg v_{i}=v_{k}$ . This wff ensures that the two adjacent countries are assigned different colors. And that is it! A structure $\mathfrak{A}$ satisfies $\Gamma$ with $s$ iff $|\mathfrak{A}|$ contains no more than 4 points (colors) and each variable $v_{i}$ (country $i$ ) is assigned a point in $|\mathfrak{A}|$ (a color) by $s$ such that no two adjacent countries share the same color. And we can then apply the compactness theorem the same way to state that$\Gamma$ is satisfiable iff every finite subset of $\Gamma$ is satisfiable.