서로소 집합

위키백과, 우리 모두의 백과사전.
(서로소 (집합론)에서 넘어옴)
이동: 둘러보기, 검색
서로소인 두 집합

집합 A, B에 공통의 원소가 없으면, 즉 AB교집합공집합이면(AB = ∅) AB서로소(-素, 영어: disjoint)라고 하고 이러한 두 집합 AB서로소 집합(-素集合, 영어: disjoint sets)이라고 한다.[1] 예를 들어서 {1, 2, 3}{4, 5, 6}은 서로소 집합이며 {1, 2, 3}{3, 4, 5}는 아니다.

정의[편집]

집합들의 족 \mathcal S에 대하여, 모든 S_i,S_j\in\mathcal S,S_i\ne S_j에 대하여 S_i\cap S_j=\varnothing일 경우, \mathcal S서로소 집합족(영어: family of disjoint sets)이라고 한다.[1]

두 집합 S_1,S_2에 대하여 S_1\cap S_2=\varnothing이면 S_1S_2서로소라고 한다. 이는 S_1\ne S_2이며 \{S_1,S_2\}가 서로소 집합족인 것과 동치이다.

두 무한 집합의 교집합이 유한할 때 이 두 집합이 거의 서로소인 집합이라고 한다. 하지만 다르게 정의하는 경우도 있다.[2]

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

[편집]

성질[편집]

  • 임의의 집합과 공집합은 서로소이다.[4]
  • 공집합은 자기 자신과 서로소인 유일한 집합이다.[4]
  • 서로소 집합족이 둘 또는 이상의 원소를 가지면, 그의 교집합은 공집합이다.
  • 하나의 원소만을 가진 집합족은 모두 서로소 집합족이다. 그의 교집합은 공집합일 수도, 아닐 수도 있다.
  • 교집합이 공집합인 집합족이 다 서로소인 것은 아니다.[5] 그 예로 집합 { {1, 2}, {2, 3}, {1, 3} }을 들 수 있다.
  • 공집합은 집합족으로서 서로소 집합족이다.[6]

관련 개념[편집]

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

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

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

같이 보기[편집]

각주[편집]

  1. Halmos, P. R. (1960), 《Naive Set Theory》, Undergraduate Texts in Mathematics (영어), Springer, 15쪽, ISBN 9780387900926 
  2. Halbeisen, Lorenz J. (2011), 《Combinatorial Set Theory: With a Gentle Introduction to Forcing》, Springer monographs in mathematics (영어), Springer, 184쪽, ISBN 9781447121732 
  3. Copson, Edward Thomas (1988), 《Metric Spaces》, Cambridge Tracts in Mathematics (영어) 57, Cambridge University Press, 62쪽, ISBN 9780521357326 
  4. Oberste-Vorth, Ralph W.; Mouzakitis, Aristides; Lawrence, Bonita A. (2012), 《Bridge to Abstract Mathematics》, MAA textbooks (영어), Mathematical Association of America, 59쪽, ISBN 9780883857793 
  5. Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2010), 《A Transition to Advanced Mathematics》 (영어), Cengage Learning, 95쪽, ISBN 9780495562023 
  6. See answers to the question ″Is the empty family of sets pairwise disjoint?″
  7. Halmos (1960, 28쪽)
  8. 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 
  9. Paige, Robert; Tarjan, Robert E. (1987), “Three partition refinement algorithms”, 《SIAM Journal on Computing》 (영어) 16 (6): 973–989, doi:10.1137/0216062, MR 917035 
  10. Ferland, Kevin (2008), 《Discrete Mathematics: An Introduction to Proofs and Combinatorics》 (영어), Cengage Learning, 45쪽, ISBN 9780618415380 
  11. 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 
  12. Monin, Jean François; Hinchey, Michael Gerard (2003), 《Understanding Formal Methods》 (영어), Springer, 21쪽, ISBN 9781852332471 
  13. Lee, John M. (2010), 《Introduction to Topological Manifolds》, Graduate Texts in Mathematics (영어) 202 2판, Springer, 64쪽, ISBN 9781441979407 
  14. Bollobás, Béla (1986), 《Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability》 (영어), Cambridge University Press, 82쪽, ISBN 9780521337038 

바깥 고리[편집]