Drawing Blanks

Premature Optimization is a Prerequisite for Success

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: