Paris–Harringtonの定理

wikipedia:Paris–Harrington theorem
'strengthened finite Ramsey theorem'という定理がPA（一階のペアノ算術）からは証明できないらしい。PAで証明できない定理の例として、かなり面白いと思った。
wikipediaの記事にも書いてあるが、"strength finite Ramsey theorem"は以下のような主張。

任意の正の整数n,k,mに対して十分大きく自然数Nをとれば、{1,2,3,...,N}のn点部分集合全体をk色で塗り分けたとき、どんな塗り分け方をしても、m個以上の要素からなる部分集合Y⊂{1,2,3,...,N}が存在し、Yのn点部分集合はすべて同じ色になり、またYの要素の数は、Yに含まれる最小の数以上になる。