Drawing Blanks

Premature Optimization is a Prerequisite for Success

Archive for February 2011

Coloring of an infinite map: Model-theoretic proof

leave a comment »

Previously:

I formulated the problem (“coloring an infinite planar map using 4 colors”): https://bbzippo.wordpress.com/2011/01/18/coloring-of-an-infinite-map/

Then I offered 2 elementary solutions of the problem: by inductively extending colorings  and by using compactness of closed intervals of real numbers .

The second proof may seem very short but that’s because I gave it in a relaxed form. In fact one still needs to do some work in order to show that the limit point of the sequence indeed encodes a proper coloring.

And then I claimed that there exists a one-line proof that is based on the more fundamental compactness property.

Now:

Alright, how do we apply the Compactness Theorem to map coloring? All we have to do is to build a theory of map colorings. More precisely, let’s take one infinite map and build a theory of colorings of this map.

Let N be the set of natural numbers and K be the set {0, 1, 2, 3}. Our theory will contain the following three sets of propositions (propositions are in italic, all the quantifiers just describe the schemas):

  1. For All n from N, “C(n,0) or C(n,1) or C(n,2) or C(n,3)  is in the theory
  2. For All n from N, For All k from K, for All m from K\{k}: “C(n,k) => ~C(n,m)” is in the theory
  3. For each pair of adjacent regions r_i, r_j, for All k from K: “C(i,k) => ~C(j,k)” is in the theory

C(n,k) are just a propositional symbols, I use the parenthesis just for clarity. I emphasize, it is just a symbol, without any meaning on its own. But we are going to assign meaning and the truth value to them (that is, build a model). Pick any finite subset of the propositions of our theory. For all n that occur in that subset, properly color the corresponding regions of the map. Then assign truth to C(n,k) : it is true in the model (which is the coloring) only if the region r_n is colored by the color k. Easy to see that all the propositions in this finite subset turn out true (duh! because 1 means each region has a color, 2 means each region has only one color, 3 means no adjacent regions have same color). So any finite subset of the theory has a model. Hence, by Compactness Theorem, the whole theory has a model. I.e. there exists a truth assignment for the whole theory. Let’s color the map in accordance with that truth assignment. Obviously, since all our propositions are satisfied, that will be a proper coloring.

The above paragraph may sound like a bunch of tautologies; in addition, it doesn’t look like a “one-line proof” that I promised. Well, I wanted to make the proof accessible to those who have a hard time telling apart theories and models. (and I probably did a poor job).

In fact, the whole proof is “define a theory that describes proper colorings, then apply the compactness theorem”.

Advertisements

Written by bbzippo

02/11/2011 at 4:14 am

Posted in math

Back to Compactness

leave a comment »

Previously:

I formulated the problem (“coloring an infinite planar map using 4 colors”) and showed that in order to prove some statement about an infinite set it is not generally enough just to show that the statement holds for any finite subset: https://bbzippo.wordpress.com/2011/01/18/coloring-of-an-infinite-map/

Then I offered 2 elementary solutions of the problem: https://bbzippo.wordpress.com/2011/01/20/coloring-of-an-infinite-map-inductive-solution/  https://bbzippo.wordpress.com/2011/01/21/coloring-of-an-infinite-map-proof-by-compactness/ 

That was an attempt to demonstrate that in order for us to be able to describe an infinite set in terms of its finite subsets, that infinite set must posses some property that we call compactness (anagram of “men, cats, cops”)

Now:

I’d like to mention the mother of all compactness, the most foundational occurrence of compactness – the compactness of theories with respect to satisfiability .

The Compactness Theorem basically says: You have an infinite set of statements in some language. Assume that for any finite subset of them you can build a dictionary that assigns meaning to words in such manner that the statements are true when interpreted. Then you can build a dictionary that makes all the statements true.

In the next post I will give a one-line proof of the infinite map coloring based on the Compactness theorem.

In the meantime, some meta-math thoughts about the theorem.…

Read the rest of this entry »

Written by bbzippo

02/04/2011 at 4:51 am

Posted in math

Another explanation of Monsky’s theorem

leave a comment »

Written by bbzippo

02/02/2011 at 2:38 pm

Posted in math