[일반] 컴팩트성 정리 응용 질문 (램지 정리 증명)

[바보(180.67)]

명제논리의 컴팩트성 정리를 응용하여,

색깔 수가 2일 때 무한 램지 정리에서 유한램지 정리를 증명하는 게 연습문제입니다.

검색을 해보고는 있는데, 저기서 n의 의미를 모르겠어요 ...

n = 2일 때 그래프라는데 맞나요??

n이 일반적일 때 색칠하기 문제가 도저히 상상이 안 갑니다.

필요한 정의와 정리는 적어놓았는데,

어떻게 컴팩트성 정리를 적용하는지 힌트 좀 주실 수 있나요?

읽어주셔서 감사합니다.

[익명(110.12)]

그래프로 보고싶으면 vertex set이 A인 complete n-uniform hypergraph의 edge를 색칠한다고 생각하셈

[바보(180.67)]

답변 감사합니다.

[익명(110.12)]

Compactness는 논리 안본지 오래되서 헷갈리는데 variable은 [A]^n의 각 element에 대응되는 애들을 만들고 각각이 P에 있으면 true, 아니면 false값을 가진다고 두고 각 size m인 H가 homogeneous하지 않을것을 명제논리로 쓸 수 있음. 만약 finite ramsey theorem이 false라면 이거의 finite subset은 consistence하고 compactness에 의해 infinite ramsey가 false

[바보(180.67)]

크흑 너무 감사합니다 ㅠㅠㅠㅠ

[바보(180.67)]

저 아무리 고민해 봐도 homogeneous하지 않을 것을 명제논리로 쓰는 법을 모르겠습니다. 알려주실 수 있나요?

[익명(110.12)]

not ( H의 모든 size n subset이 P에 있음 or H의 모든 size n subset이 P에 없음)

[바보(180.67)]

H가 size m 이상인 건 어떻게 명제논리로 나타낼 수 있을까요??

[바보(180.67)]

다시 질문드렸는데 봐주실 수 있나요?
https://gall.dcinside.com/mgallery/board/view/?id=math&no=20550