From: Robin Chapman <rjc@maths.ex.ac.uk>
Subject: Re: compactness argument
Date: Thu, 01 Jun 2000 20:58:38 GMT
Newsgroups: sci.math
Summary: compactness theorem of first-order logic

In article <8h64gm$71d$1@news.acns.nwu.edu>,
  lerma@math.nwu.edu (Miguel A. Lerma) wrote:
> In a proof in Ramsey Theory I found the sentence "now apply
> compactness or a finitely branching tree argument". I understand
> the part "a finitely branching tree argument"; which I assume is
> a version of Koenig's Infinity Lemma. But what does "compactness"
> mean in this context?

Using the compactness theory of first order logic. This states
that if one has a set S of sentences in a first order language,
and if every finite subset of S is satisfiable then the whole
set S is satisfiable.

> As an example, take the Four Color Theorem, valid in principle for
> finite planar maps. It can be extended to infinite maps in the
> following way. Let M be an infinite planar map (with the usual
> restrictions of the 4-color theorem). Take an increasing sequence
> of finite parts (subsets of countries) M_k of M with limit M, i.e.,
> each M_{k} is contained in M_{k+1} and their union is M. For
convenience
> we may take M_0 = empty set. Next make a tree in which the nodes
> at level k are all possible 4-colorings of M_k (with 4 fix colors,
> say red, blue, green, yellow), and a node u at level k is connected
> to a node v at level k+1 iff v is an extension of u (i.e., if the
> coloring v of M_{k+1} restricted to M_k is precisely u). The result
> is a finitely branching tree with arbitrarily long branches, so it
> must have an infinite branch. That infinite branch defines a
> 4-coloring of the whole M.
>
> Now prove it by "compactness" so that I can see what that means.

Take four colours say R, G, B, Y. For each vertex v of the graph
and each p each colour introduce a sentence variable, e.g, Rv whose
interpretation is "v is red". Consider the set of sentences S
of the following two types
(i) for each vertex v: (Rv or Gv or Bv or Yv) and not(Rv and Gv) and ...
(ii) for each edge vw: not(rv and rW) and not (Gv and Gw) and ...
So (i) sez that each vertex is a unique colour and (ii) sex
no adjacent vertices have the same colour. The finite 4-colour
theorem says that if the graph is planar then every finite subset
of S is satisfiable. By the compactness theorem S is satisfiable;
bingo! the infinite 4-colour theorem.

> Note that this sort of argument must have some limitations.
> For example, there are arbitrarily large finite sets of points
> in the plane separated by integer distances, but there is no
> infinite set of points in the plane with that property. So whatever
> is meant by "compactness argument", it cannot be applied to this
> example - the "finitely branching tree argument" cannot be applied
> here because the associated tree (a sort of decision tree determining
> how to extend a set of points with integer distances) is not finitely
> branching (e.g., there are infinitely many choices for the distance
> between the first two points).

You can't capture the notion of an infinite set of points having
integer distance in a set of first order sentences.

--
Robin Chapman, http://www.maths.ex.ac.uk/~rjc/rjc.html
 "`The twenty-first century didn't begin until a minute
  past midnight January first 2001.'"
   John Brunner, _Stand on Zanzibar_ (1968)


Sent via Deja.com http://www.deja.com/
Before you buy.