램지의 정리 (Ramsey's theorem)

파티에 대한 오래된 퍼즐이 하나 있다. 그 파티에는 여섯 명의 사람이 참석했는데 여섯 명 중 어느 두 명을 골라도 서로 좋아하던가 아니면 서로 싫어한다. 그런데 문제는 어느 두 명을 고르더라도 서로 좋아하는 관계에 있는 세 명이 그 파티에 있거나 아니면 어느 두 명을 고르더라도 서로 싫어하는 관계에 있는 세 명이 그 파티에 있다는 것을 보이는 일이다.

그 풀이는 다음과 같다. a 를 그 여섯 명 중하나라고 해보자. 남은 사람이 다섯이 있으므로 a 가 좋아하는 자기 이외의 사람이 (적어도) 세 명이 있거나 아니면 a 가 싫어하는 자기 이외의 사람이 세 명 있을 것이다. a 가 그들을 좋아한다고 가정해 보자. (a 가 그들을 싫어하는 경우도 논증은 비슷하다.) 그 세 사람을 b, c, d 라고 부르자. 그러면 (경우 1) b 가 c 를 좋아하거나, b 가 d 를 좋아하거나, c 가 d 를 좋아한다면, a, b, c 또는 a, b, d 또는 a, c, d 는 각각 그 세 사람 중 어느 둘을 골라도 서로를 좋아하는 세 사람이다. 그러나 (경우 2) b 가 c 를 싫어하고, b 가 d 를 싫어하고, c 가 d 를 싫어한다면, b, c, d 는 그 세 사람 중 어느 둘도 서로를 싫어하는 세 사람이다. 그리고 경우 1과 경우 2 둘 가운데 하나가 틀림없이 성립한다.

여섯이라는 수는 일반적으로 더 줄일 수 없다. 만약 다섯 사람, a, b, c, d, e 만 참석했다면 다음과 같은 상황이 생긴다.

                                

(점선은 '좋아한다' 를 뜻하고 실선은 '싫어한다' 를 뜻한다.) 이 상황에서는 세 사람 중 어느 둘을 골라도 서로 좋아하게 되는 그러한 세 사람은 a, b, c, d, e 가운데 없고, 또 세 사람 중 어느 둘을 골라도 서로 싫어하게 되는 그러한 세 사람도 없다.

같은 유형인데 더 어려운 퍼즐은 앞의 파티에 열여덟 명이 참석했다고 했을 때 어느 두 명을 고르더라도 서로 좋아하는 관계에 있는 네 사람이 있거나 아니면 어느 두 명을 고르더라도 서로 싫어하는 관계에 있는 네 사람이 있다는 것을 증명하는 것이다. (힌트 : 아홉 명이 참석한 그런 파티에서 어느 두 명을 고르더라도 서로 좋아하는 관계에 있는 네 사람이 있거나 아니면 어느 두 명을 고르더라도 서로 싫어하는 관계에 있는 세 사람이 있다는 것을 보여라.)

열여덟이라는 수는 줄일 수 없다고 알려져 있다. (F. Harary, Graph Theory, Addison-Wesley, Reading, Mass., 1969, 16-17 쪽을 보라.) 그러나 만약 앞의 파티에 m 명이 참석했을 때 어느 두 명을 고르더라도 서로 좋아하는 관계에 있는 다섯 사람이 있거나 아니면 어느 두 명을 고르더라도 서로 싫어하는 관계에 있는 다섯 사람이 있게 될 최소한의 수 m 이 얼마인지는 아직까지 (1989) 알려지지 않았다. m 이 43 과 55 사이에 있다는 것은 알려졌으나 (George R.T. Hendry, "Ramsey Numbers for Graphs with Five Vertices", Journal of Graph Theory 13(2), 1989, 246쪽.), 컴퓨터를 사용하여 정확한 'm' 값을 집어낼 수 있을 정도로 조합 가능성의 수를 줄일 수 있는 그 문제에 대한 충분한 통찰력을 아직은 갖지 못했다. 그리고 빛의 속도, 물질의 원자적인 특징, 다음 빅뱅이 있기 전까지의 짧은 시간 등이 주는 물리적인 제약들 때문에, 다섯에 대해서 그 값을 알지 못한다면 여섯, 일곱, 여덞에 대해서는 결코 알지 못할 것이라고 생각할 수 있다.

이제 이런 퍼즐들과 관련이 있는 램지 (F.P. Ramsey) 의 다음과 같은 정리를 증명하겠다. r, s, n(n≥r) 을 양의 정수라고 하자. 그러면 다음과 같은 양의 정수 m ( ≥ n) 이 존재한다. 크기 m 인 임의의 집합 X, 곧 원소를 정확히 m 개 포함하고 있는 임의의 집합 X 에 대해서 크기가 r 인 X의 부분집합이 서로 배타적인 s 개의 집합으로 어떻게 나누어지더라도 다음과 같은 성질을 만족하면서 크기가 n 인, X 의 부분집합 Y 가 언제나 있을 것이다: 그 Y 의 크기 r 인 모든 부분집합들이 s 개의 집합들 중 같은 집합에 속하게 된다. 위의 퍼즐들에서 볼 때 파티에 참석한 사람들로 이루어진 집합에서 크기가 2인 부분집합들은 서로 배타적인 집합 두 개로 나뉘어지는데 그 중 하나는 서로 좋아하는 사람들의 쌍으로 이루어진 집합이고 다른 하나는 서로 싫어하는 사람들의 쌍으로 이루어진 집합이다. 그래서 두 퍼즐에서 모두 r=s=2 이다. 첫번째 퍼즐에서는 n=3 일 때 m 은 6 이라고 할 수 있다. 두번째 퍼즐에서는 n=4 일 때 m 은 18 이라고 할 수 있다. 그리고 램지 정리의 결론을 만족하는 'm' 의 최소값은 사소하지 않은 'r', 's', 'n' 값 몇 개 빼고는 알려져 있지 않고 또 아마도 알려질 수 없을 텐데, 그럼에도 불구하고 램지의 정리는 임의의 r, s, n 에 대해서 m 이 그 값이 얼마인지 모른다 할지라도 언제나 존재한다 는 보장을 해 준다.

램지 정리의 증명은 두 부분으로 되어 있다. 첫째 부분에서는 앞 문단에서 말한 유한 형태를 '무한' 형태로 바꾸어 증명한다. 둘째 부분에서는 명제 연산에 대해서만 조밀성 정리를 사용해서 무한 형태로부터 유한 형태를 도출한다. 역시 램지가 처음 증명한 (R. B. Braithwaite (펴냄), The Foundations of Mathematics, Littelefield, Adams & Co., Paterson, N.J., 1960 에 실린 "On a Problem of Formal Logic" 참조.) 무한 형태는 다음과 같은 내용이다. r, s 를 양의 정수라고 하자. 그러면 자연수들의 크기 r 인 부분집합들이 서로 배타적인 s 개의 집합으로 어떻게 나누어지더라도 다음과 같은 성질을 만족하는 자연수들의 무한 집합 Y 가 언제나 있을 것이다. 그 Y 의 크기 r 인 모든 부분집합들이 s 개의 집합들 중 같은 집합에 속하게 된다. (따라서 만약 무한히 많은 천사들이 있고 그 중 어느 두 천사라도 서로 좋아하거나 서로 싫어한다면 어느 두 천사를 고르더라도 서로 좋아하는 관계에 있는 무한히 많은 천사들이 있든지 아니면 어느 두 천사를 고르더라도 서로 싫어하는 관계에 있는 무한히 많은 천사들이 있다.)

무한 형태의 증명을 해 보겠다.

어떤 집합 X 의 크기 r 인 부분집합들의 집합을 서로 배타적인 s 개의 집합들 C₁, ..., C_s 로 나누는 것을, X 의 크기 r 인 부분집합들 x 의 집합으로부터 s 와 같거나 작은 양의 정수들의 집합으로의 함수 f 로 생각할 수 있다. 그런데 이 함수 f 는 f(x)=j 인 경우 그리고 오직 그 경우에만 x 는 C_j 에 있다는 조건을 만족한다.

자연수들의 집합을 'ω' 로 나타내자. X 의 크기 r 인 부분집합들의 집합을 '[X]^r' 로 나타내자. 'f:W→Z' 가 'f 는 W 의 각 원소에 Z 의 한 원소를 부여하는 함수이다' 를 뜻하도록 쓰자.

그러므로 우리는 다음을 보이고 싶다. 만약 'f:[ω]^r→{1, ..., s} 이면 자연수들의 어떤 무한한 집합 Y 와 어떤 양의 정수 j≤s 에 대해서 f:[Y]^r→{j} 이다.

우리는 이것을 다음과 같은 조건을 만족하는 연산 φ 를 정의함으로써 보이겠다. 만약 'f:[ω]^r→{1, ..., s} (0<r, s) 이면 φ (f) 는 Y 의 크기 r 인 모든 부분집합 y 에 대해서 f(y)=j 인 양의 정수 j≤s 와 자연수들의 무한집합 Y 로 이루어진 순서쌍 <j, Y> 이다.

r 에 대한 귀납으로 논증을 하겠다. ('s' 는 앞으로 고정된 양의 정수를 지시할 것이다.)

토대 단계: r=1. 이 경우에 φ (f), 즉 <j, Y> 의 정의는 쉽다. 그 까닭은 이렇다. 무한히 많은 크기 1 의 집합들 {b} 각각에 대해서 f({b}) 가 유한히 많은 양의 정수들 k≤s 중의 하나라면, 무한히 많은 {b} 에 대해 f({b})=k 인 그런 k 가 적어도 하나 존재한다. 따라서 우리는 j 를 무한히 많은 {b} 에 대해 f({b})=k 를 만족하는 최소의 양의 정수 k≤s 로 정의할 수 있고, Y={b| f({b})=j} 라고 정의할 수 있다.

귀납 단계: 우리는 귀납 가설로서 φ 가 모든 g:[ω]^r→{1, ..., s} 에 대해서 알맞게 정의되었다고 전제한다. f:[ω]^r+1→{1, ..., s} 라고 가정하자. φ (f) 즉 <j, Y> 를 정의하기 위해서 우리는 각 자연수 i 에 대해 자연수 b_i, 무한 집합 Y_i, Z_i, W_i, 함수 f_i:[ω]^r→{1, ..., s}, 양의 정수 j_i≤s 를 정의하겠다. Y₀=ω 라고 하자. 우리는 이제 Y_i 가 정의된다고 가정하고 b_i, Z_i, f_i, j_i, W_i, Y_i+1 을 어떻게 정의하는지 보여주겠다.

Y_i 에서 가장 작은 원소를 b_i 라고 하자.

Z_i=Y_i-{b_i} 라고 하자. Y_i 는 무한하기 때문에 Z_i 도 무한하다. Z_i 의 원소들은 커지는 순서로 a_i0, a_i1, ... 이라고 하자.

\자연수들의 크기 r 인 임의의 집합 x 에 대해서 k₁<...<k_r 이고 x={k₁, ..., k_r} 일 때  이라고 하자. b_i 가  가운데 하나가 아니고 f 가 자연수들의 크기 (r+1) 인 모든 집합들에 대해 정의되므로 f_i 는 잘 정의된다.

귀납 가설에 의해서 어떤 양의 정수 j_i≤s 와 어떤 무한 집합 W_i 에 대해 φ (f_i)=<j_i, W_i> 이고 W_i 의 크기 r 인 모든 부분집합 x 에 대해서 f_i(x)=j_i 이다. 따라서 우리는 j_i 와 W_i 를 정의했고, 이제 Y_i+1={a_ik| k∈W_i} 라고 정의한다.

W_i 가 무한하므로 Y_i+1 도 무한하다. Y_i+1⊆Z_i⊆Y_i 이고 따라서 만약 i₁≤i₂ 이면  이다. 그리고 b_i 는 Z_i 의 모든 원소보다 작고 따라서 Y_i+1 의 모든 원소보다 작으므로 b_i 는 Y_i+1 의 가장 작은 원소인 b_i+1 보다 작다. 따라서 만약 i₁<i₂ 이면,  이다.

각 양의 정수 k≤s 에 대해서 E_k={i| j_i=k} 라고 하자. 토대 단계에서처럼 어떤 E_k 는 무한한데, E_k 가 무한하게 되는 최소의 k 를 j 라고 하고 Y={b_i| i∈E_j} 라고 하자. 이것으로써 φ (f) 의 정의가 완성되었다.

만약 i₁<i₂ 이면  이므로 Y 는 무한하다. 증명을 완성하기 위해서 우리는 만약 y 가 Y 의 크기 (r+1) 인 부분집합이라면 f(y)=j 라는 것을 보여야만 한다. 그러므로 i<i₁<...<i_r 이고  i, i₁, ..., i_r 이 모두 E_j 에 있다고 할 때  이라고 가정하자. Y_i 들은 Y_i-1 의 부분집합이므로  은 모두 Y_i+1 속에 있다. 1≤m≤r 인 각 m 에 대해서 k_m 이  을 만족하는 W_i 의 유일한 원소라고 하자. 그리고 x={k₁, ..., k_r} 이라고 하자. 그러면 x⊆W_i 이고, i₁<...<i_r 이므로  이고 따라서 x 는 W_i 의 크기 r 인 부분집합이다. 그런데 φ (f_i)=<j_i, W_i> 이므로, f_i(x)=j_i 이다. i 는 E_j 에 있으므로 j_i=j 이다. 따라서  이다. (이 증명은 선택 공리를 이용하지 않는다. 램지 (Ramsey) 는 「형식 논리의 문제에 대하여」("On a Problem of Formal Logic") 에서 만약 X 가 무한 집합이고 f:[X]^r→{1, ..., s} 이면 양의 정수 j≤s 가 존재하고 f:[Y]^r→{j} 를 만족하는 X 의 무한 부분집합 Y 가 있다는 더 강한 정리를 증명했다. 이 더 강한 진술의 증명은 어떤 것이든지 (적어도 약한 형태의) 선택 공리에 의존해야 한다.)

(잠시 본 줄거리에서 벗어나서 우리가 방금 증명한 정리를 강화한 것 두 개를 논의해 보자. s 를 양의 정수라고 하자. [k를 양의 정수라고 하자.] 그러면 자연수들의 유한한 부분집합들이 서로 배타적인 s 개의 집합으로 어떻게 나누어지더라도 다음과 같은 성질을 만족하는 자연수들의 무한 집합 Y 가 언제나 있을 것이다. 어떠한 양의 정수 r[≤k] 에 대해서도 Y 의 크기 r 인 모든 부분집합들이 s 개의 집합들 중 같은 집합에 속하게 된다. 꺾쇠표에 든 내용을 보태 강화한 것은 방금 증명한 정리에 호소하여 r 에 대한 귀납으로 쉽게 증명할 수 있다. 그러나 꺾쇠표에 든 내용이 없이 강화한 것은 s=2 에 대해서 거짓이다. x 가 x 에 있는 원소들의 개수인 수를 포함한다면 f(x)=1 이라고 하자. 그렇지 않으면 f(x)=2 라고 하자. 그러면 모든 r 에 대해서 f:[Y]^r→{1} 또는 f:[Y]^r→{2} 가 되는 무한 집합 Y 란 없게 된다. 왜냐하면 만약 r 이 Y 에 속하는 어떤 양의 정수라고 하고 b₁, b₂, ..., b_r 이 Y 의 r 개의 다른 원소들이라고 한다면,

f({r, b₂, ..., b_r})=1

이고 동시에 f({b₁, b₂, ..., b_r})=2 이기 때문이다.)

렘지 정리의 무한 형태를 증명했으므로 이제 유한 형태를 즉각 함축하는 어떤 명제를 (명제연산에 대해서만) 조밀성 정리의 도움을 받아 그 무한 형태로부터 증명하겠다. 먼저 정의가 필요하다.

(자연수의) 공집합이 아닌 유한집합의 크기가 그 집합의 가장 작은 원소보다 크면 그 집합은 (상대적으로) 크다 고 말한다. 따라서 {2, 3, 4} 와 {3, 10, 100, 1000} 은 크지만 {3, 4, 5} 와 {5, 10, 100, 1000} 은 크지 않다.

램지 정리의 유한 형태를 증명하기 위해서는 다음 명제 PH 를 증명하면 충분하다. 만약 r, s, n 이 양의 정수이고 n≥r 이라고 한다면 원소가 m 개인 집합 {0, 1, ..., m-1} 의 크기 r 인 부분집합들이 서로 배타적인 s 개의 집합으로 어떻게 나누어지더라도 다음과 같은 성질을 만족하는 양의 정수 m≥n 이 존재하다: 적어도 크기가 n 인 {0, 1, ..., m-1} 의 큰 부분집합 Y 가 있으며, 그 Y 의 크기 r 인 모든 부분집합들이 s 개의 집합들 중 같은 집합에 속하게 된다. 램지 정리의 유한 형태는 PH 로부터 바로 따라나온다. 즉 Y 가 크기가 적어도 n 인 {0, 1, ..., m-1} 의 큰 부분집합이고 Y 의 크기 r 인 모든 부분집합들이 s 개로 나뉘어진 집합들 중 같은 집합에 속하게 된다면, 램지 정리의 결론을 만족하는 Y 의 크기 n 인 (크지 않을 수도 있는) 부분집합이 있다. 임의의 크기 m 인 집합 X 의 부분집합들 대신에 {0, 1, ..., m-1} 의 부분집합에 국한시킨다고 해서 일반성을 잃지 않는다는 것은 분명하다.

PH 를 증명하기 위해서 r, s, n 을 n≥r 인 임의의 양의 정수라고 하자. 모든 양의 정수 m≥n 에 대해서 다음 주장(^*m) 이 성립한다는 가정으로부터 모순을 이끌어내는 것만으로 충분하다.

다음과 같은 조건을 만족하는 함수 f:[{0, 1, ..., m-1}]^r→{1, ..., s} 가 있다: 크기가 적어도 n 인 {0, 1, ..., m-1} 의 큰 부분집합 Y 각각에 대해서 f(Z₁)≠1, ..., f(Z_s)≠s 인 Y 의 크기 r 인 부분집합 Z₁, ..., Z_s 가 있다.

Z 가 자연수들의 크기 r 인 집합이고 1≤j≤s 일 때 모든 Z, j 에 대해서 p_Zj 가 문장문자 (서로 다른 쌍 Z, j 에 대해서는 서로 다른 문장문자) 라고 하자.

자연수들의 크기 r 인 집합 Z 에 대해서 A_z 는 문장

(p_Z1∨...∨p_Zs)&(p_Z1→-p_Z2&...&-p_Zs)&
                                (p_Z2→-p_Z3&...&-p_Zs)&...&(p_Z(s-1)→-p_Zs)& 

이다. p_Z1, ..., p_Zs) 가운데 정확히 하나만 참인 경우 그리고 오직 그 경우에만 A_Z 가 참이다.

크기가 적어도 n 인 큰 집합 Y 에 대해서 B_Y 를 문장

-∧{p_Z1:Z⊆Y}&...&-∧{p_Zs:Z⊆Y}

라고 하자. ('∧θ' 는 'θ 의 모든 원소들의 연언' 을 뜻한다.)

S 는 문장들 A_Z 와 B_Y 모두를 포함하는 집합이라고 하자. S_m 은 S 의 부분집합으로 문장문자 p_Zj 가 C 에 나타날 때마다 Z⊆{0, 1, ..., m-1} 이 되는 그런 S 의 문장들 C 모두를 그리고 오직 그런 문장들만을 포함하는 집합이라고 하자. 각 S_m 은 S 의 유한한 부분집합이고 S 의 모든 문장들은 어떤 S_m 에 있다. 우리는 이제 각 S_m 이 만족가능하다는 것을 알고자 한다. 만약 m≤m′ 이라면 S_m⊆S_m′ 이므로 우리는 m≥n 이라고 가정할 수 있다.

그러면 (^*m) 은 성립한다. (^*m) 이 존재한다고 주장하는 함수를 f 라고 하자.  는 모든 문장문자 p_Zj 에 대해서 (p_Zj)=1 인 경우 그리고 오직 그 경우에만 f(Z)=j 이게 하는 해석이라고 하자. f:[{0, 1, ..., m-1}]^r→{1, ..., s} 이므로 S_m 에 있는 모든 문장들 A_Z 는  에서 참이다. B_Y 를 S_m 에 나오는 문장이라고 하자. 그러면 Y 는 적어도 크기 n 의 큰 집합이다. 더구나 Y⊆{0, 1, ..., m-1} 이다. 왜냐하면 만약 k 가 Y 에는 있으나 k≥m 이라면 k 는 크기가 r 인 어떤 Z⊆Y 의 원소이고, 그러면 p_Z1, ..., p_Zs 가 B_Y 에 나타나게 되는데 이는 B_Y 가 S_m 에 있으므로 불가능하다. 만약 B_Y 가  에서 거짓이라고 한다면 ∧{p_Z1:Z⊆Y}, ..., ∧{p_Zs:Z⊆Y} 가운데 하나는  에서 참이고, 그러면 Y 의 크기 r 인 모든 부분집합 Z 에 대해 f(Z)=1 또는 ... 또는 그런 모든 부분집합에 대해 f(Z)=s 가 성립하게 되어 (^*m) 에 위배된다. 따라서 S_m 에 나타나는 모든 문장들은  에서 참이고S_m 은 만족가능한다.

S 의 모든 문장들이 어떤 S_m 의 원소이고 만약 m≤m′ 라면 S_m⊆S_m′ 이므로 S 의 모든 유한한 부분집합은 어떤 S_m 의 부분집합이고, 따라서 S 의 모든 유핞나 부분집합은 만족가능하다. 조밀성 정리에 의해서 S 는 만족가능하고 S 의 모든 문장들은 어떤 해석  에서 참이다. 모든 문장들 A_Z 는  에서 참이므로 자연수들의 크기 r 인 임의의 집합 Z 에 대해서 (p_Zj)=1 인 j=1, ..., s 가 정확히 하나 있다. (p_Zj)=1 인 경우 그리고 오직 그 경우에만 f(Z)=j 라고 하자. 그러면 f:[ω]^r→{1, ..., s} 이다. 크기가 적어도 n 인 큰 집합 Y 모두에 대해서 B_Y 는  에서 참이고 따라서 ∧{p_Z1:Z⊆Y}, ..., ∧{p_Zs:Z⊆Y} 는 모두 거짓이므로 Y 에는 f(Z₁)≠1, ..., f(Z_s)≠s 가 되는 크기 r 의 부분집합들 Z₁, ..., Z_s 가 존재한다.

그러나 이것은 불합리한다. 램지 정리의 무한 형태에 의하면 ω 의 무한 부분집합 W 의 크기 r 인 모든 부분집합 Z 에 대해서 f(Z)=1 또는 ... 또는 W 의 크기 r 인 모든 부분집합 Z 에 대해서 f(Z)=s 가 되는 그런 ω 의 무한 부분집합 W 가 있다. 따라서 만약 w 가 W 의 가장 작은 원소이고 k=max(w+1, n) 일 떄 Y 가 W 에 속한 k 개의 가장 작은 원소들로 구성된 집합이라면 (W 가 무한하므로 Y 는 존재한다), Y 는 적어도 크기 n 인 큰 집합이고, Y 의 크기 r 인 모든 부분집합 Z 에 대해서 f(Z)=1 이거나 또는 ... 또는 Y 의 크기 r 인 모든 부분집합 Z 에 대해서 f(Z)=s 이고, 따라서 f(Z₁)≠1, ..., f(Z_s)≠s 인 그런 Y 의 크기 r 인 부분집합들 Z₁, ..., Z_s 는 존재하지 않는다.

우리는 PH 에 대한 (수학적으로 옳은) 증명 을 했고, 따라서 램지의 유한 형태에 대한 증명을 했다. 무한 집합들에 대한 양화 때문에 램지 정리의 무한 형태는 산수의 언어로 진술될 수 없다. 그러나 β-함수나 그와 비슷한 다른 어떤 장치의 도움을 받아서 자연수의 유한 집합에 관한 진술들과 자연수의 유한 집합으로부터 자연수로 가는 함수들에 관한 진술들은 자연수에 관한 진술들로 부호화할 수 있고, 그렇게 부호화하면 PH 와 램지 정리의 유한 형태는 모두 산수의 언어로 표현될 수 있다. 그러나 알맞게 부호화한 다음에 램지 정리의 유한 형태는 Z 에서 증명할 수 있지만 PH 는 증명할 수 없다는 것은 주목할 만한 일이다. PH 는 Z 에서 결정불가능한 (우리가 방금 보았듯이) 참인 명제이다. Z 에서 PH 의 증명불가능성에 대한 고전적인 증명은 제프 패리스 (Jeff Paris) 와 레오 해링턴 (Leo Harrington) 의 「페아노 산수에서의 수학적 불완전성」("A mathematical incompleteness in Peano Arithmetic") 에 나와 있다. (이 논문은 『수리논리학 논문집』(Handbook of Mathematical Logic), 존 바와이즈 (Jon Barwise) 펴냄, 노스 홀랜드 출판사 (North Holland Publishing Company), 1977, 1133-1142 쪽에 수록되어 있다.)

램지 정리의 유한 형태를 훌륭하게 응용한 슈어 (Schur) 의 정리를 보여주고 이 장을 끝내겠다. 각 자연수가 어떤 유한한 수의 '색깔' 중의 하나로 '칠해졌다' 고 가정해 보자. 그러면 x+y=z 이면서 모두 같은 색깔인 그런 양의 정수들 x, y, z 가 있다.

증명. 색깔의 수가 s 라고 가정하자. i<j 인 자연수들의 크기 2인 집합 {i, j} 각각을 자연수 j-i 와 같은 색으로 칠해라. 램지의 정리 (r=2, n=3) 에 의해서 양의 정수 m≥3 이 있고, {i, j}, {j, k}, {i, k} 가 모두 같은 색깔이면서 i<j<k 인 {0, ..., m-1} 의 크기 3인 부분집합 {i, j, k} 가 있다. x=j-i, y=k-j, z=k-i 라고 하자. 그러면 x, y, z 는 모두 같은 색깔이고 x+y=z 인 양의 정수들이다.

연습문제

슈어의 정리가 '+' 대신에 '•' 일 때 성립한다는 것을 보여라. (힌트 : ... 인 꼭 그 경우에 2^x• 2^y=2^z.)

 계산가능성과 논리 : George S. Boolos   Richard C. Jeffrey 저, 김영정.최훈.강진호 옮김, 문예출판사 (393-5681), 1996 (원서 : Computability and Logic, 3rd ed, Cambridge Univ. Press, 1989), page 324~332