슈페르너의 정리 (편집) (2)

(편집 필터 규칙)

== 증명 ==
사슬을 [math(C_0 \subset C_1 \subset \cdots \subset C_n,\ \forall i\ C_i \subset N,\ \mid C_i \mid = i)]라 하자. 이 때 사슬의 총 개수는 [math(n!)]개 이다 ([math(N)]의 원소들을 나열하여 앞에서부터 [math(i)]개를 [math(C_i)]의 원소로 하면 사슬 하나에 대응시킬 수 있다).

반사슬 [math(\mathscr{F})]의 집합 중 원소의 개수가 [math(i)]개인 집합의 개수를 [math(m_i)]라 하자. 그러면 [math(\mathscr{F})]가 반사슬이므로 임의의 두 집합은 같은 사슬에 포함될 수 없다. [math(\mathscr{F})]의 한 집합 [math(A)]의 원소의 개수가 [math(i)]개이면 [math(A)]가 포함된 사슬의 개수는 [math(i!(n-i)!)]개이다 ([math(A)]가 포함된 사슬을 위에서와 같이 [math(N)]의 원소를 나열한 것으로 대응시킨다면 앞의 [math(i)]개 수는 [math(A)]의 원소들로 이미 정해져 있으므로 앞의 [math(i)]개 원소를 순서대로 나열하고 뒤의 [math(n-i)]개 수를 순서대로 나열하여 총 [math(i!(n-i)!)]개 사슬을 얻는다). [math(\mathscr{F})]의 원소 중 하나를 포함하는 사슬의 총 개수는 전체 사슬의 개수를 넘어서지 못하므로 다음 부등식을 얻을 수 있다.

[math(\sum_{i=1}^{n}m_i i!(n-i)! \leq n!)]
[math(1 \geq \sum_{i=1}^{n}m_i \frac{i!(n-i)!}{n!} \geq \sum_{i=1}^{n}m_i \binom{n}{i}^{-1} \geq \sum_{i=1}^{n}m_i \binom{n}{[n/2]}^{-1} = \mid \mathscr{F} \mid \binom{n}{[n/2]}^{-1})]
[math(\therefore \mid \mathscr{F} \mid \leq \binom{n}{[n/2]})]

실례로는 크기가 [math([n/2])]인 [math(N)]의 부분집합들을 모아놓은 집합족이 존재한다.

(임시 저장) (임시 저장 불러오기)

(↪️) (💎) (🛠️) (추가)

실례로는 크기가 [math([n/2])]인 [math(N)]의 부분집합들을 모아놓은 집합족이 존재한다.

비로그인 상태입니다. 편집한 내용을 저장하면 지금 접속한 IP가 기록됩니다.

편집을 전송하면 당신은 이 문서의 기여자로서 본인이 작성한 내용이 CC BY 4.0에 따라 배포되고, 기여한 문서의 하이퍼링크나 URL로 저작자 표시가 충분하다는 것에 동의하는 것입니다.