- #1
NasuSama
- 326
- 3
Homework Statement
Here is quite challenging problem from Enderton's popular textbook A Mathematical Introduction to Logic.
"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 ##C_1, C_2, C_3, ...##. 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 ##C_7## is colored red." Form a set ##\Sigma_1## of wffs that say, for example, ##C_7## is exactly one of the colors. Form another set ##\Sigma_2## of wffs that say, for each pair of adjacent countries, that they are not the same color. Apply compactness to ##\Sigma_1 \cup \Sigma _2##)"
2. The attempt at a solution
Since I'm not much of the math logician, it's difficult for me to make a rigorous proof. My attempt would be to first check the satisfiability of every finite subset of ##\Sigma_1## and ##\Sigma_2##. Then, take the union of those sets and finally apply compactness theorem, which states that
A set of wffs is satisfiable iff every finite subset is satisfiable.
The thing is: I wonder how the proof goes since Enderton's textbook is sometimes brief in some topics and the way he proves theorems and examples. He skips steps to the readers, assuming that they can prove them by themselves. Thus, I am a bit lost of how I should prove this (Specifically, I am not sure of the full formal proof for this problem).
Any suggestions or advices or comments?