19/10/08 14:03:04.42 e/1pBNsJ.net
メモ
URLﾘﾝｸ(esori.hatenadiary.org)
esoriの日記
2009-05-07
Paris?Harringtonの定理
URLﾘﾝｸ(ja.wikipedia.org)
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に含まれる最小の数以上になる。