From: ikastan@uranus.uucp (Ilias Kastanas)
Subject: Re: Godel's Incompleteness Theorem
Date: 15 Nov 1999 09:18:17 GMT
Newsgroups: sci.math
Keywords: Paris-Harrington variation on Ramsey's theorem

In article <19991115000402.15906.00000239@ngol01.aol.com>,
Keith Ramsay <kramsay@aol.commangled> wrote:
@In article <01bf2eec$5510ff00$0100a8c0@mgreen>,
@"Martin Green" <testware@pangea.ca> writes:
@...
@|[Ilias Kastanas] once provided a good example of a true statement
@|that could be shown to be "undprovable" with the traditional
@|"starter's kit" of number theory axioms. (Something to do with Ramsay
@|numbers).
@
@It's the Paris-Harrington variation on Ramsey's theorem. (Ramsey
@isn't related to me, BTW.) For every positive integers n, k, and r,
@there exists an N such that if we define a coloring f with domain the
@set of k-element subsets of {n,...,N} and range the "colors" {1,...,r},
@then there exists a subset S of {n,...,N} which is monochromatic, in
@the sense that the value of f on each of the k-element subsets of S is
@the same, and such that S is "large", meaning the number of elements
@of S is greater than the smallest element of S.


	Let's call this the Strong Finite Ramsey theorem ("SFR").

@
@|I don't know exactly what axiom had to be "added in"
@|to make the axiom set powerful enough.


	Well,  SFR -> Consis(PA)  (provably in PA);  so the thing you
add in must be at least as strong as Consis(PA).  In fact, identifying
it is not difficult:   SFR  <->  Sigma_1 -Reflection  (again, provably
in PA).  "Reflection" is, roughly, "for every  phi, if  PA proves  phi,
then  phi";  here, it is restricted to Sigma_1  phi, i.e. of the form
Ex Ey ... Eu (quantifier-free).

	Incidentally,  Consis(PA) <->  Sigma_0 -Reflection.

 
@The Paris-Harrington variant in some vague sense falls "just outside"
@the scope of elementary arithmetic (i.e., PA-- first order formalized
@Peano arithmetic). In order to prove it, it's enough to assume certain
@very intuitive properties of sets of integers, whereas PA only has
@variables ranging over integers.


	Yes; one simple approach is to prove the Infinite Ramsey theorem
(any coloring on a countably infinite domain, i.e.  w, has an infinite
homogeneous set) and deduce  SFR  from it.  Essentially, this involves
repeated applications of  "if you split an infinite set into two parts,
at least one part will be infinite".

@
	Another "natural" example like  SFR  is the theorem about
Goodstein sequences; I've posted on that some time ago in sci.logic.



						Ilias