Partition of a set

A set of stamps partitioned into bundles: No stamp is in two bundles, no bundle is empty, and every stamp is in a bundle.

수학(mathematics)에서, 집합의 분할은 모든 각 원소가 정확하게 하나의 부분집합에 포함되는 그러한 방법에서 원소를 비-빈(non-empty) 부분집합(subset)으로 그룹화하는 것입니다.

집합(set)에 대한 모든 각 동치 관계(equivalence relation)는 이 집합의 분할을 정의하고, 모든 각 분할은 동치 관계를 정의합니다. 동치 관계 또는 분할을 갖춘 집합은 전형적으로 유형 이론(type theory)과 증명 이론(proof theory)에서 때때로 집합체(setoid)라고 불립니다.

Definition and Notation

집합 X의 분할은 X에서 모든 각 원소 x가 정확하게 이들 부분집합 중 하나에 있음을 만족하는 X의 비-빈 부분집합의 집합입니다 (즉, X는 부분집합의 서로소 합집합(disjoint union)입니다).^[2]

동등하게, 집합 P의 가족이 X의 분할인 것과 모든 다음 조건이 유지되는 것은 필요충분 조건입니다:^[3]

가족 P는 빈 집합(empty set)을 포함하지 않습니다 (즉, $\emptyset \notin P$ ).
P에서 집합의 합집합(union)은 X와 같습니다 (즉, $\textstyle \bigcup _{A\in P}A=X$ ). P에서 집합들은 포괄(exhaust) 또는 덮개(cover) X라고 말합니다. 역시 집합적으로 포괄적 사건(collectively exhaustive events)과 덮개(cover)를 참조하십시오.
P에서 임의의 둘의 서로소 집합의 교집합(intersection)은 빈 것입니다 (즉, $(\forall A,B\in P)\;A\neq B\implies A\cap B=\emptyset$ ). P의 원소는 쌍별 서로소(pairwise disjoint)라고 말합니다.

P에서 집합들은 분할의 블럭, 부분, 또는 셀이라고 불립니다.^[4] 만약 $a\in X$ 이면, 우리는 a를 포함하는 셀을 $[a]$ 로 나타냅니다. 다시 말해서, $[a]$ 는 a를 포함하는 P에서 셀에 대한 표기법입니다.

모든 각 분할, P는 X에 대한 동치 관계, 즉 임의의 $a,b\in X$ 에 대해 우리가 $a\sim _{P}b$ 를 가지는 것과 $a\in [b]$ 인 것은 필요충분 조건 (동등하게, $b\in [a]$ 인 것은 필요충분 조건)을 만족하는 관계 $\sim _{P}$ 로 식별될 수 있습니다. 그 표기법은 동치 관계가 분할에서 구성될 수 있다는 아이디어를 불러일으킵니다. 반대로, 모든 각 동치 관계는 분할로 식별될 수 있습니다. 이것이 때때로 비공식적으로 "동치 관계는 분할과 같다"고 말해지는 이유입니다. 만약 P가 주어진 동치 관계 $\sim$ 로 식별된 분할이면, 일부 저자는 $P=X/\sim$ 를 씁니다. 이 표기법은 분할이 집합 X를 셀로 나뉜다는 아이디어를 암시합니다. 그 표기법은 역시 동치 관계에서 우리가 분할을 구성할 수 있다는 아이디어를 불러일으킵니다.

P의 랭크(rank)는 만약 X가 유한(finite)이면 |X| − |P|입니다.

Examples

빈 집합 $\emptyset$ 은 정확히 하나의 분할, 즉 $\emptyset$ 을 가집니다. (주목: 이것은 분할의 구성원이 아니라 분할입니다.)
임의의 비-빈 집합 X에 대해, P = { X }는 자명한 분할이라고 불리는 X의 분할입니다.
- 특히, 모든 각 한원소 집합(singleton set) {x}는 정확히 하나의 분할, 즉 { {x} }을 가집니다.
집합 U의 임의의 비-빈 적절한 부분집합(proper subset) A에 대해, 그것의 여집합(complement)과 함께 집합 A는 U의 분할, 즉, { A, U ∖ A }를 형성합니다.
집합 {1, 2, 3}은 이들 다섯 분할 (항목당 하나의 분할)을 가집니다:
- { {1}, {2}, {3} }, 때때로 1 | 2 | 3로 쓰입니다.
- { {1, 2}, {3} }, 또는 1 2 | 3.
- { {1, 3}, {2} }, 또는 1 3 | 2.
- { {1}, {2, 3} }, 또는 1 | 2 3.
- { {1, 2, 3} }, 또는 123 (숫자와 혼동되지 않을 문맥에서).
다음은 {1, 2, 3}의 분할이 아닙니다:
- { {}, {1, 3}, {2} }는 (임의의 집합)의 분할이 아닌데 왜냐하면 그것의 원소 중 하나가 빈 집합(empty set)이기 때문입니다.
- { {1, 2}, {2, 3} }는 (임의의 집합)의 분할이 아닌데 왜냐하면 원소 2는 하나의 블록보다 많은 것에 포함되기 때문입니다.
- { {1}, {2} }는 {1, 2, 3}의 분할이 아닌데 왜냐하면 그것의 어떤 블록도 3을 포함하지 않기 때문입니다; 어쨌든, 그것은 {1, 2}의 분할입니다.

Partitions and equivalence relations

집합 X에 대한 임의의 동치 관계(equivalence relation)에 대해, 해당 동치 클래스(equivalence class)의 집합은 X의 분할입니다. 반대로, X의 임의의 분할 P에서, 우리는 x와 y가 P에서 같은 부분에 있을 때 정확하게 x ~ y를 설정함으로써 X에 대한 동치 관계를 정의할 수 있습니다. 따라서 동치 관계와 분할의 개념은 본질적으로 동등합니다.^[5]

선택의 공리(axiom of choice)는 집합 X의 임의의 분할에 대해 분할의 각 부분에서 정확하게 하나의 원소를 포함하는 X의 부분집합의 존재를 보장합니다. 이것은 집합에 대한 동치 관계가 주어지면 우리는 모든 각 동치 클래스에서 정식의 대표 원소(canonical representative element)를 선택할 수 있음을 의미합니다.

Refinement of partitions

집합 X의 분할 α는 만약 α의 모든 각 원소가 ρ의 일부 원소의 부분집합이면 X의 분할 ρ의 세분화입니다–그리고 우리는 α의 ρ보다 미세한 것이고 ρ가 α보다 거친 것이라고 말합니다. 비공식적으로, 이것은 α가 ρ의 뒤따른 단편화임을 의미합니다. 해당 경우에서, 그것은 α ≤ ρ라고 쓰입니다.

X의 분할의 집합에 대한 이 보다-미세한 관계는 부분 순서(partial order)입니다 (따라서 표기법 "≤"이 적합합니다). 원소의 각 집합은 그것이 격자(lattice)를 형성하고, (유한 집합의 분할에 대해) 보다 구체적으로 그것이 기하학적 격자(geometric lattice)가 되도록 최소 위쪽 경계(least upper bound)와 최대 아래쪽 경계(greatest lower bound)를 가집니다.^[6] 4-원소 집합의 분할 격자는 15 원소를 가지고 왼쪽에 하세 다이어그램(Hasse diagram)에 표시됩니다.

기하학적 격자와 매트로이드(matroid) 사이의 암호동형(cryptomorphism)에 기초된, 유한 집합의 분할의 이 격자는 매트로이드의 기본 집합이 격자의 원자(atoms), 즉 $n-2$ 한원소 집합과 하나의 이-원소 집합을 갖는 분할인 매트로이드에 해당합니다. 이들 원자 분할은 완전한 그래프(complete graph)의 가장자리와 일-대-일로 대응합니다. 원자 분할의 집합의 매트로이드 클로저(matroid closure)는 모든 파티션의 가장 미세한 공통적인 거침화입니다; 그래프-이론적 용어에서, 그것은 완전한 그래프의 꼭짓점(vertices)을 주어진 가장자리의 집합에 의해 형성된 부분그래프의 연결된 성분(connected components)으로의 분할입니다. 이러한 방법으로, 분할의 격자는 완전한 그래프의 그래픽 매트로이드(graphic matroid)의 플랫의 격자에 해당합니다.

또 다른 예제는 동치 관계의 관점에서 분할의 세분화를 묘사합니다. 만약 D가 표준 52-카드 덱에 있는 카드의 집합이면, D에 대한 같은-색상-으로 관계 – 이것은 ~_C로 표시될 수 있습니다 – 는 둘의 동치 클래스: 집합 {빨간색 카드}와 {검은색 카드}를 가집니다. ~_C에 해당하는 2-부분 분할은 {스페이드}, {다이아몬드}, {하트}, 및 {클로바}의 넷의 동치 클래스를 가지는 같음-짝-으로 관계 ~_S를 산출하는 세분화를 가집니다.

Noncrossing partitions

대응하는 동치 관계 ~를 갖는 집합 N = {1, 2, ..., n}의 분할은 다음 속성을 가지면 비교차하는(noncrossing) 것입니다: 만약 N의 a < b < c < d를 가지는 넷의 원소 a, b, c, 및 d가 a ~ c와 b ~ d를 만족시키면, a ~ b ~ c ~ d입니다. 그 이름은 다음 동치 정의에서 따온 것입니다: N의 원소 1, 2, ..., n이 (반시계방향 순서에서) 정규 n-각형의 n 꼭짓점으로 그려진다고 상상해 보십시오. 분할은 그런-다음 각 블록을 다각형 (꼭짓점이 블록의 원소임)으로 그림으로써 시각화될 수 있습니다. 분할이 그때에 비-교차하는 것인 것과 이들 다각형이 교차하지 않는 것은 필요충분 조건입니다.

유한 집합의 비교차하는 분할의 격자는 자유 확률(free probability) 이론에서의 역할 때문에 최근에 중요성을 갖게 되었습니다. 이것들은 모든 분할의 격자의 부분집합을 형성하지만, 부분격자는 아닌데 왜냐하면 두 격자의 결합 연산이 일치하지 않기 때문입니다.

Counting partitions

n-원소 집합의 총 분할의 숫자는 벨 숫자(Bell number) B_n입니다. 처음 여러 벨 숫자는 B₀ = 1, B₁ = 1, B₂ = 2, B₃ = 5, B₄ = 15, B₅ = 52, 및 B₆ = 203 (OEIS에서 수열 A000110)입니다. 벨 숫자는 다음 재귀(recursion)를 만족시킵니다:

B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}

그리고 다음 지수 생성 함수(exponential generating function)를 가집니다:

\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}z^{n}=e^{e^{z}-1}.

벨 숫자는 역시 각 행에서 첫 번째 값이 이전 행의 끝에서 복사되고, 후속 값은 두 숫자, 왼쪽에 숫자와 위치의 왼쪽 위에 숫자를 더함으로써 계산되는 벨 삼각형(Bell triangle)을 사용하여 계산될 수 있습니다. 위치 왼쪽. 벨 숫자는 이 삼각형의 양쪽 변을 따라 반복됩니다. 삼각형 내의 숫자는 주어진 원소가 가장 큰 한원소(singleton)인 분할을 셉니다.

정확히 k (비-빈) 부분으로 설정된 n-원소의 분할의 숫자는 두 번째 종류의 스털링 숫자(Stirling number of the second kind) S(n, k)입니다.

n-원소 집합의 비-교차하는 분할의 숫자는 카탈랑 숫자(Catalan number)입니다:

C_{n}={1 \over n+1}{2n \choose n}.

Notes

^ Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37
^ Halmos, Paul (1960). Naive Set Theory R. Springer. p. 28. ISBN 9780387900926.
^ Lucas, John F. (1990). Introduction to Abstract Mathematics. Rowman & Littlefield. p. 187. ISBN 9780912675732.
^ Brualdi 2004, pp. 44–45.
^ Schechter 1997, p. 54.
^ Birkhoff, Garrett (1995), Lattice Theory, Colloquium Publications, vol. 25 (3rd ed.), American Mathematical Society, p. 95, ISBN 9780821810255.

References

Brualdi, Richard A. (2004). Introductory Combinatorics (4th ed.). Pearson Prentice Hall. ISBN 0-13-100119-1.
Schechter, Eric (1997). Handbook of Analysis and Its Foundations. Academic Press. ISBN 0-12-622760-8.

[1] Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37

[2] Halmos, Paul (1960). Naive Set Theory R. Springer. p. 28. ISBN 9780387900926.

[3] Lucas, John F. (1990). Introduction to Abstract Mathematics. Rowman & Littlefield. p. 187. ISBN 9780912675732.

[FOOTNOTEBrualdi200444–45-4] Brualdi 2004, pp. 44–45.

[FOOTNOTESchechter199754-5] Schechter 1997, p. 54.

[6] Birkhoff, Garrett (1995), Lattice Theory, Colloquium Publications, vol. 25 (3rd ed.), American Mathematical Society, p. 95, ISBN 9780821810255.

[1]

[2]

[3]

[4]

[5]

[6]