서로소 집합

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

집합 A, B에 공통의 원소가 없으면, 즉 A와 B의 교집합공집합이면 A와 B가 서로소(서로素, 영어: disjoint)라고 하고 이러한 두 집합 A와 B를 서로소 집합(서로素 集合, 영어: 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), p. 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 .

바깥 고리[편집]