멱집합(r14 Blame)
| r14 | ||
|---|---|---|
| r11 | 1 | [[분류:집합론]][[분류:떡밥위키 학문 프로젝트]] |
| r1 (새 문서) | 2 | [목차] |
| 3 | == 개요 == | |
| r3 | 4 | 주어진 [[집합]]의 모든 [[부분집합]]을 [[원소]]로 가지는 [[집합]]. 즉, 다음과 같이 정의되는 집합이다. |
| r2 | 5 | |
| r3 | 6 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\mathcal P(A) = \{S \mid S \subset A\})]|| |
| 7 | ||
| r13 | 8 | ZFC 공리계에서의 엄밀한 전개를 위해 [math(\in)] 술어로만 기술하면 다음과 같다. |
| 9 | ||
| 10 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\mathcal P(A) = \{S \mid \forall s \in S \to s \in A \})]|| | |
| 11 | ||
| r3 | 12 | == 예시 == |
| r6 | 13 | 세 여성, 폰은정, 박근혜, 혜정이가 있다고 가정하자. 이들이 톡방을 만드는 것은 멱집합에 해당한다. |
| r7 | 14 | |
| r6 | 15 | [math(C = \{\text{폰은정},\ \text{박근혜},\ \text{혜정이}\})] |
| 16 | ||
| r5 | 17 | [math(P(C) = \{ |
| 18 | \varnothing,\ | |
| 19 | \{\text{폰은정}\},\ | |
| 20 | \{\text{박근혜}\},\ | |
| 21 | \{\text{혜정이}\},\ | |
| 22 | \{\text{폰은정},\ \text{박근혜}\},\ | |
| 23 | \{\text{폰은정},\ \text{혜정이}\},\ | |
| 24 | \{\text{박근혜},\ \text{혜정이}\},\ | |
| 25 | \{\text{폰은정},\ \text{박근혜},\ \text{혜정이}\} | |
| 26 | \})] | |
| r4 | 27 | |
| r5 | 28 | [math(|P(C)| = 2^{|C|} = 2^3 = 8)] |
| r9 | 29 | |
| r10 | 30 | == 멱집합의 존재성 == |
| 31 | ZFC에서는 멱집합 공리(axiom of power set)를 통해 멱집합의 존재성을 보장한다. 보통 ZFC에서 철저하게 subset이나 succ을 위주로 명백한 집합을 정의하는 것과 다르게 다소 급격해(?) 보일 수 있는 공리. 다만 멱집합이 없으면 집합론에서 대부분의 정리가 사실상 쓰레기이기 때문에 필수적으로 필요하다. 생각보다 많은 object들이 멱집합으로 만들어지는 편. | |
| 32 | ||
| r9 | 33 | == 멱집합의 농도 == |
| 34 | [[집합]] 문서에 써있듯이 어떤 원소가 집합에 포함되는지는 포함되느냐([math(\in)]) 포함되지 않느냐([math(\notin)]) 두 가지 경우의 수만이 존재한다. 만약 크기 [math(n)]짜리 유한집합 [math(A)]의 모든 원소 [math(x)]에 대해 특정 집합에 포함 여부를 기준으로 조건을 형성하면 이는 [math(A)]의 모든 부분집합을 유일하게 결정하게 되고, 그 경우의 수는 각 원소마다 2가지이므로 총 [math(2^n)]개가 된다. | |
| 35 | ||
| r12 | 36 | == 멱집합의 상등 == |
| 37 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\mathcal P(A) = \mathcal P(B) \iff A = B)]|| | |
| 38 | ||
| r14 | 39 | 개요 문단에 나온 정의를 기억하고 있으면 증명은 졸라 쉽다. |
| 40 | ||
| r4 | 41 | == 순서론에서 == |
| 42 | 멱집합 그 자체로 subset relation에 대해 poset을 이루기 때문에 맨날 집합론이나 lattice theory 초장에 멱집합 얘기가 나온다. | |
| r8 | 43 | |
| 44 | 물론 멱집합의 모든 부분집합은 poset이지만 아무래도 멱집합이 하세 다이어그램으로 그렸을 때 가장 예쁘장하게(?) 나오기 때문인 듯. 특히 크기 8짜리 멱집합 다이어그램이 가장 자주 나온다. 집합론 시간에 졸지 않았다면 거의 외울 수 있을 수준. | |
| 45 |