Four Colour Theorem proof help

In summary, the conversation discusses a challenging problem from Enderton's popular textbook A Mathematical Introduction to Logic. The problem involves proving that an infinite countable planar map with countries can still be colored with four colors. The suggested approach is to partition sentence symbols into four parts and form sets of wffs that state the colors of each country and that adjacent countries cannot have the same color. The compactness theorem is then applied, but there is uncertainty about how to prove the theorem in this specific case. The question ultimately revolves around whether truth is always regular in maps and colorings.
  • #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?
 
Physics news on Phys.org
  • #2
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.
 

1. What is the Four Colour Theorem?

The Four Colour Theorem is a mathematical problem that states that any map can be coloured using only four colours, in such a way that no two adjacent regions have the same colour.

2. Who proved the Four Colour Theorem?

The Four Colour Theorem was first proven in 1976 by Kenneth Appel and Wolfgang Haken using a computer-assisted proof.

3. What is the significance of the Four Colour Theorem?

The Four Colour Theorem is significant because it was the first major theorem to be proven using a computer, and it helped pave the way for the use of computers in mathematical proofs.

4. How was the Four Colour Theorem proved?

The proof of the Four Colour Theorem involved reducing the problem to a finite number of cases and using a computer to check each case individually. This method is known as a "proof by exhaustion."

5. Are there any controversies surrounding the proof of the Four Colour Theorem?

Yes, there has been some debate over whether the proof is valid, as it relies heavily on computer calculations. However, the proof has been accepted by the mathematical community and has not been disproven.

Similar threads

  • General Math
Replies
8
Views
1K
  • General Math
Replies
21
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
Replies
2
Views
315
  • Topology and Analysis
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
11
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • General Math
Replies
1
Views
1K
Back
Top