서로소 집합

공통된 원소가 없는 집합들. 교집합이 공집합인 집합들
(서로소 집합족에서 넘어옴)

집합론에서 서로소 집합(-素集合, 영어: disjoint sets)는 공통 원소가 없는 두 집합이다.[1] 예를 들어서 1, 2, 3}과 4, 5, 6}은 서로소이며 1, 2, 3}과 3, 4, 5}는 아니다.

서로소인 두 집합

정의

편집

두 집합   을 만족시키면, 서로소 집합이라고 한다.

집합족  가 다음 조건을 만족시키면, 서로소 집합족(영어: disjoint family of sets)이라고 한다.

  • 임의의  에 대하여,  이거나,  이다.[1]

기수  에 대하여, 두 집합   를 만족시키면,  -거의 서로소 집합(영어:  -almost disjoint sets)이라고 한다. 비슷하게  -거의 서로소 집합족(영어:  -almost disjoint family of sets)을 정의할 수 있다. 여기서  을 취하면 서로소 집합 및 서로소 집합족의 개념을 얻는다.

성질

편집
  • 모든 집합은 공집합과 서로소이다.[2]
  • 자기 자신과 서로소일 필요충분조건은 공집합이다.[2]
  • 서로소 집합족이 둘 이상의 집합으로 이루어졌다면, 그 교집합은 공집합이다.
  • 공집합은 서로소 집합족이지만, 그 교모임은 모든 집합을 포함하는 고유 모임이다.[3]
  • 하나의 집합으로 이루어진 집합족은 서로소 집합족이지만, 그 교집합은 공집합이 아닐 수 있다.
  • 교집합이 공집합인 집합족은 서로소 집합족이 아닐 수 있다.[4] 예를 들어, 집합족 {{1, 2}, {2, 3}, {1, 3}}의 교집합은 공집합이지만, 이는 서로소 집합족이 아니다.

관련 개념

편집

위상수학에는 서로 분리된 집합의 여러 종류의 개념이 있는데 이들은 서로소보다 더 엄격한 조건을 가진다. 예를 들어, 서로소인 폐포를 가지거나 서로소인 근방을 가진 두 집합을 서로 분리된 집합이라고 할 수 있다. 이와 비슷하게, 거리공간에서 양수로 분리된 집합은 0이 아닌 거리로 분리된 두 집합을 뜻한다.[5]

집합  분할은 합집합이  이고 서로소인 집합들로 이루어진 집합족이다.[6] 모든 분할은 하나의 동치 관계와 대응한다.[6] 서로소 집합 데이터 구조[7]분할 세분화[8]는 컴퓨터 과학에서 각각 합집합, 세분화 연산의 대상이 되는 집합의 분할을 효율적으로 유지하는 기술이다.

분리합집합은 두 가지 의미를 가진다. 서로소 집합들의 경우 그들의 합집합이 바로 그들의 분리합집합이고,[9] 서로소가 아닌 경우 서로소가 되게끔 변형한 뒤 합집합을 취한다.[10] 임의의 원소를 자신과 속하는 집합의 지표의 순서쌍으로 대체하는 것은 변형의 한 방법이다.[11][12]

헬리 족은 교집합이 공집합인 최소 부분집합족은 모두 서로소인 집합족이다. 여기서 '최소'는 그 부분집합족이 교집합이 공집합인 부분집합족을 가지지 않는다는 것이다. 모든 폐구간의 집합은 헬리 족의 한 예이다.[13]

같이 보기

편집

각주

편집
  1. Halmos, P. R. (1960), 《Naive Set Theory》, Undergraduate Texts in Mathematics (영어), Springer, 15쪽, ISBN 9780387900926 
  2. Oberste-Vorth, Ralph W.; Mouzakitis, Aristides; Lawrence, Bonita A. (2012), 《Bridge to Abstract Mathematics》, MAA textbooks (영어), Mathematical Association of America, 59쪽, ISBN 9780883857793 
  3. See answers to the question ″Is the empty family of sets pairwise disjoint?″[깨진 링크(과거 내용 찾기)]
  4. Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2010), 《A Transition to Advanced Mathematics》 (영어), Cengage Learning, 95쪽, ISBN 9780495562023 
  5. Copson, Edward Thomas (1988), 《Metric Spaces》, Cambridge Tracts in Mathematics (영어) 57, Cambridge University Press, 62쪽, ISBN 9780521357326 
  6. Halmos (1960, 28쪽)
  7. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), 〈Chapter 21: Data structures for Disjoint Sets〉, 《Introduction to Algorithms》 (영어) Seco판, MIT Press, 498–524쪽, ISBN 0-262-03293-7 
  8. Paige, Robert; Tarjan, Robert E. (1987), “Three partition refinement algorithms”, 《SIAM Journal on Computing》 (영어) 16 (6): 973–989, doi:10.1137/0216062, MR 917035 
  9. Ferland, Kevin (2008), 《Discrete Mathematics: An Introduction to Proofs and Combinatorics》 (영어), Cengage Learning, 45쪽, ISBN 9780618415380 
  10. Arbib, Michael A.; Kfoury, A. J.; Moll, Robert N. (1981), 《A Basis for Theoretical Computer Science》, The AKM series in Theoretical Computer Science: Texts and monographs in computer science (영어), Springer-Verlag, 9쪽, ISBN 9783540905738 
  11. Monin, Jean François; Hinchey, Michael Gerard (2003), 《Understanding Formal Methods》 (영어), Springer, 21쪽, ISBN 9781852332471 
  12. Lee, John M. (2010), 《Introduction to Topological Manifolds》, Graduate Texts in Mathematics (영어) 202 2판, Springer, 64쪽, ISBN 9781441979407 
  13. Bollobás, Béla (1986), 《Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability》 (영어), Cambridge University Press, 82쪽, ISBN 9780521337038 

외부 링크

편집