• Support PF! Buy your school textbooks, materials and every day products Here!

Four Colour Theorem proof help!

  • Thread starter NasuSama
  • Start date
  • #1
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?
 

Answers and Replies

  • #2
verty
Homework Helper
2,164
198
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.
 

Related Threads for: Four Colour Theorem proof help!

Replies
0
Views
809
Replies
0
Views
6K
  • Last Post
Replies
12
Views
2K
  • Last Post
Replies
1
Views
4K
  • Last Post
2
Replies
25
Views
2K
  • Last Post
Replies
2
Views
3K
Top