수학의 집합 이론(set theory) 및 관련된 분야에서, 주어진 집합(set) S의 부분집합(subset)의 모음 F는 S의 부분집합의 가족 또는 S에 걸쳐 집합의 가족이라고 합니다. 보다 일반적으로, 임의의 집합의 모음은 무엇이든지 집합의 가족 또는 집합-가족 또는 집합-시스템이라고 불립니다.
용어 "모음"은 여기에서 사용되는데, 왜냐하면, 일부 문맥에서, 집합의 가족은 임의의 지정된 구성원의 반복된 복사본을 포함하도록 허용될 수 있고, 다른 문맥에서 그것은 집합이라기보다는 적절한 클래스(proper class)를 형성할 수 있기 때문입니다.
유한 집합 S의 부분집합의 유한 가족은 역시 초월그래프(hypergraph)라고 불립니다.
Examples
- 거듭제곱 집합 P(S)는 S에 걸쳐 집합의 가족입니다.
- 집합 S의 k-부분집합 \(S^{(k)}\) (즉, 부분집합 원소의 숫자를 k로 갖는 S의 부분집합)은 집합의 가족을 형성합니다.
- S = {a,b,c,1,2}라고 놓습니다. S에 걸쳐 집합의 가족의 예제는 (중복집합(multiset) 의미에서) \(F=\{A_1, A_2, A_3, A_4\}\)에 의해 제공되며, 여기서 \(A_1 = \{a,b,c\}\), \(A_2 = \{1,2\}\), \(A_3 = \{1,2\}\), 및 \(A_4 = \{a,b,1\}\)입니다.
- 모든 순서 숫자(ordinal number)의 클래스 Ord는 집합의 큰 가족입니다. 즉, 그것은 집합 자체가 아니지만 대신 적절한 클래스(proper class)입니다.
Properties
- S의 부분집합의 임의의 가족은 그것이 반복된 구성원을 가지지 않으면 거듭제곱 집합 P(S)의 자체 부분집합입니다.
- 반복없이 집합의 임의의 가족은 모든 집합 (우주(universe))의 적절한 클래스 V의 부분클래스(subclass)입니다.
- Philip Hall에 기인한 홀의 결혼 문제(Hall's marriage theorem)는 개별 대표의 시스템(system of distinct representatives)을 가지기 위한 비-빈 집합 (반복 허용됨)의 유한 가족에 대해 필요충분 조건을 제공합니다.
Related concepts
수학의 다른 영역에서 가져온 특정 유형의 대상은 순수하게 일부 유형의 대상의 집합의 모음으로 설명될 수 있다는 점에서 집합의 가족과 동등합니다:
- 초그래프(hypergraph)는, 역시 집합 시스템이라고 불리며, 각각 임의적인 집합일 수 있는 또 다른 초가장자리(hyperedges)의 집합과 함께 꼭짓점 집합에 의해 형성됩니다. 초그래프의 초가장자리는 집합의 가족을 형성하고, 임의의 집합의 가족은 꼭짓점으로 집합의 합집합을 가지는 초그래프로 해석될 수 있습니다.
- 추상적 단순 복합체(abstract simplicial complex)는 단순 복합체(simplicial complex), 면을 맞대어 연결된, 선분, 삼각형, 사면체, 및 고차원 심플렉스(simplices)의 합집합에 의해 형성된 모양의 개념의 조합론적 추상화입니다. 추상 단순 복합체에서, 각 심플렉스는 단순히 그것의 꼭짓점의 집합으로 표현됩니다. 가족에서 임의의 집합의 부분집합이 역시 가족에 속해 있는 반복없이 유한 집합의 임의의 가족은 추상적 단순 복합체를 형성합니다.
- 발생 구조(incidence structure)는 점의 집합, 선의 집합, 및 발생 관계라고 하는 (임의적인) 이항 관계(binary relation)로 구성되며, 어떤 점이 어떤 선에 속하는지 지정합니다. 발생 구조는 집합의 가족 (심지어 둘의 구별되는 선이 같은 점의 집합을 포함하더라도), 각 선에 속하는 점의 집합에 의해 지정될 수 있고, 집합의 임의의 가족은 이러한 방식에서 발생 구조로 해석될 수 있습니다.
- 이진 블록 코드(block code)는 코드단어의 집합으로 구성되며, 각각은 0과 1, 모두 같은 길이의 문자열(string)입니다. 각 코드단어 쌍이 큰 해밍 거리(Hamming distance)를 가지면, 그것은 오류-수정 코드(error-correcting code)로 사용될 수 있습니다. 블록 코드는 역시 각 코드단어를 1을 포함하는 위치의 집합으로 설명함으로써 집합의 가족으로 설명할 수 있습니다.
- 토폴로지적 공간(topological space)은 쌍 (X, τ)으로 구성되며 여기서 X는 집합 (점이라고 함)이고 τ는 X에 걸쳐 집합 (열린 집합이라고 함)의 가족입니다. τ는 빈 집합과 X 자체를 모두 포함해야 하고, 집합 합집합과 유한 집합 교집합 아래에 닫혀 있어야 합니다.
Special types of set families
슈페르너 가족(Sperner family)은 집합 중 어느 것도 다른 집합을 포함하지 않는 집합-가족입니다. 슈페르너의 정리(Sperner's theorem)는 슈페르너 가족의 최대 크기를 경계짓습니다.
헬리 가족(Helly family)은 빈 교집합을 갖는 최소 부분가족이 경계진 크기를 가짐을 만족하는 집합-가족입니다. 헬리의 정리(Helly's theorem)는 경계진 차원의 유클리드 공간에서 볼록 집합이 헬리 가족을 형성한다고 말합니다.
추상적 단순 복합체(abstract simplicial complex)는 아래방향-닫힌 것인 집합-가족 F입니다. 즉, F에 있는 집합의 모든 각 부분집합은 역시 F에 있습니다. 매트로이드(matroid)는 증대 속성(augmentation property)이라고 하는 추가 속성을 갖는 추상적 단순 복합체입니다.
References
- Biggs, Norman L. (1985), Discrete Mathematics, Oxford: Clarendon Press, ISBN 0-19-853252-0
- Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Upper Saddle River, NJ: Prentice Hall, ISBN 0-13-602040-2
- Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9
External links
- Media related to Set families at Wikimedia Commons