Insights Blog
-- Browse All Articles --
Physics Articles
Physics Tutorials
Physics Guides
Physics FAQ
Math Articles
Math Tutorials
Math Guides
Math FAQ
Education Articles
Education Guides
Bio/Chem Articles
Technology Guides
Computer Science Tutorials
Forums
Intro Physics Homework Help
Advanced Physics Homework Help
Precalculus Homework Help
Calculus Homework Help
Bio/Chem Homework Help
Engineering Homework Help
Trending
Featured Threads
Log in
Register
What's new
Search
Search
Search titles only
By:
Intro Physics Homework Help
Advanced Physics Homework Help
Precalculus Homework Help
Calculus Homework Help
Bio/Chem Homework Help
Engineering Homework Help
Menu
Log in
Register
Navigation
More options
Contact us
Close Menu
JavaScript is disabled. For a better experience, please enable JavaScript in your browser before proceeding.
You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an
alternative browser
.
Forums
Homework Help
Calculus and Beyond Homework Help
Four Colour Theorem proof help
Reply to thread
Message
[QUOTE="NasuSama, post: 4523933, member: 439500"] [h2]Homework Statement [/h2] Here is quite challenging problem from Enderton's popular textbook [I]A Mathematical Introduction to Logic[/I]. "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##)" [b]2. The attempt at a solution[/b] 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? [/QUOTE]
Insert quotes…
Post reply
Forums
Homework Help
Calculus and Beyond Homework Help
Four Colour Theorem proof help
Back
Top