Subset   부분 집합

1. 부분 집합 이란?

  ㅇ 부분 집합 (subset)  A ⊆ W
     - 집합 A의 모든 원소가 집합 W에 포함되는 집합
        . 그 자신 A(A = W) 및 ∅(공 집합)도 포함
     - 표기 (⊆) :  A ⊆ W
        . `집합 A가 집합 W의 부분 집합이다` 라고 말함
     - 例) {1,2}의 부분 집합은, ∅, {1}, {2}, {1,2}
 
  ㅇ 진 부분 집합 (proper subset)  A ⊂ W
     - 부분 집합 중 자기 자신을 제외한 집합
        . 즉, A ⊆ W 이지만, W ≠ A일 때
     - 표기 (⊂) :  A ⊂ W
        . `집합 A가 집합 W의 진부분 집합이다` 라고 말함
     - 例) {1,2}의 진 부분 집합은,  ∅, {1}, {2}

  ㅇ 가 부분 집합 (improper subset)
     - 어떤 집합의 부분 집합 중 그 집합 자기 자신인 부분 집합
        . 즉, A ⊆ A에서 A 자체를 가 부분 집합이라고 함

  ㅇ 초 집합 (superset)  W ⊇ A
     - 집합 A의 모든 원소를 포함하는 집합
        . 즉, A ⊆ W일 때 W를 A의 초집합이라고 함
     - A 자체도 A의 초집합에 포함됨


2. 부분 집합의 개수

  ㅇ 유한 집합 S = {a1,a2,...,an}일 때,

     - S의 부분 집합의 개수는, 2n 개

     - S의 진 부분 집합의 개수는, 2n - 1 개
        . 전체 부분 집합에서, 자기 자신 S 하나를 제외

     - 특정 원소 p개를 포함하나, q개는 포함하지 않는 S의 부분 집합의 개수는, 2n-p-q 개
        . 나머지 n-p-q개의 원소는 각각 포함 또는 제외를 자유롭게 선택할 수 있기 때문