1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Four Colour Theorem proof help!

  1. Oct 2, 2013 #1
    1. The problem statement, all variables and given/known data

    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?
  2. jcsd
  3. Oct 2, 2013 #2


    User Avatar
    Homework Helper

    I think what you are asking is, what allows us to apply the compactness theorem to the particular case of maps and colourings? The compactness theorem was proved by Kurt Gödel using the completeness theorem, which says that truth of a wff is very regular, it can be calculated (proved) from the truth values of the parts of the formula. But how do we know that this is true for maps and colourings? Is it not possible that truth works differently here? In a way, this question is about whether truth is always regular.

    I don't know how to answer this but perhaps reading this can help.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted