[FOM] Correction about claim on RT(2)
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
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.
More information about the FOM