[FOM] Correction about claim on RT(2)

Andreas Weiermann weiermann at math.uu.nl
Sun Oct 10 12:32:16 EDT 2004

There has been a subtle error in my proof concerning my claim
about RT(2,2). 
I am very sorry about this.
What can be said is now the following.

Let DENSE(2,3) be the principle:

For every $n$ there is an $y$ such that
$[0,y]$ is $n$-dense(2,3).

Here a $0$-dense(2,3) set is by definition a finite set
satisfying $card(X)\geq min(X)$.
A finite set $X$ is $n+1$-dense(2,3) if for every
$F:[X]^2\to 3$ there exists a monochromatic
set $Y\subseteq X$ such that $Y$ is $n$-dense(2,3).

Theorem: PRA does not prove DENSE(2,3)

The reason is that DENSE(2,3) proves over RCA_0
the totality of the Ackermann function.
(It seems that the proof also applies to 
the case of two colors.)

I thought that WKL_0+RT^2_2 suffices for a routine proof of
DENSE(2,3) but there was a mistake
(and perhaps the claim is just false).
In any case DENSE(2,3) is provable in RCA_0 plus the
one consistency (uniform reflection principle) for WKL_0+RT^2_2.
A proof is contained in the Friedman, McAloon and Simpson
paper from the Patras Logic Symposium Proceedings 1982.

Best regards,
Andreas Weiermann.

More information about the FOM mailing list