Drawing Blanks

Premature Optimization is a Prerequisite for Success

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.…

This theorem is very powerful, but kind of weird. Curiously, why the Compactness Theorem holds – is a chicken-egg type of question, a question of methodology.

In formal logic we put the syntax before the meaning: The compactness with respect to consistency is “obvious”: if there are no contradictions in finite parts – there are no contradictions at all. And consistency is the same as satisfiability by the Completeness theorem. So we have compactness with respect to satisfiability. (I follow Chang, Keisler, 1973). But in order to prove Completeness we must wander into the semantic realm and use some set theory and transfinite induction. Or for the countable case – some less sophisticated, but still semantic stuff.

In model theory we put the meaning first: Consistency is satisfiability by definition. Now we can cut all the philosophy and apply the set-theoretic proof based on transfinite induction. (I follow Stephen G. Simpson, 1998).

You can put topology first and say that Tychonoff’s theorem implies the compactness theorem. Which is nice because it shows that the topological compactness is the same as the logical compactness.

You may even pretend that you put Compactness before set theory and topology, and prove it using some “pre-topological” ultrafilters and ultraproducts (I follow Bruno Poizat). But those ultrafilters still need a set-theoretical justification.

I would guess, you can use Category Theory somehow and avoid the set-theoretical stuff.

But in essence, (in my amateurish opinion), Compactness works because Induction works. You just need transfinite induction in the uncountable case. In other words, it works because you can enumerate stuff, put it in order.

Advertisements

Written by bbzippo

02/04/2011 at 4:51 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: