군대 문제는 언제 해결하는게 가장 좋을까? 역시 학부 중간에?



수학 이야기 : (Paris-Harrington) 음이 아닌 정수 k, m에 대해 n이 존재해 다음을 만족한다.

집합 S = {m, m+1, ..., n} 의 기수가 k인 부분집합들을 두 색으로 색칠할 때, 다음 성질을 갖는 S의 부분집합 X를 찾을 수 있다.

- X의 기수가 k인 부분집합들은 모두 같은 색으로 칠해져있다.
- X의 기수는 X의 가장 작은 원소보다 크거나 같다.



Paris-Harrington Theorem은 페아노 공리계에서 증명이 불가능하다. 더붙여, 위 명제에서 정의 할 수 있는 함수 P(k,m) = n 는 너무나도 빨리 증가하여(물론 함수표의 대각선에 있는 값만 뽑아서 일변수 함수를 만들면) 페아노 공리계로는 P가 모든 값에 대해 잘 정의되는지 조차도 증명 할 수 없다.