20180926 집합 (Set)

집합과 부분집합 : Set & Subset

수학에서 집합은 명확한 기준에 의해서 서로 다른 대상들이 모여 이루는 새로운 대상이다. 그리고 그 집합에 속하는 대상 하나하나들을 원소라고 칭한다.

만약 a 가 집합 A 의 원소라고 한다면, 아래와 나타낼 수 있다.

a ∈ A

" 원소 a 는 집합 A 에 속한다. "

만약 a 가 집합 A 의 원소가 아니라면, 아래와 같이 나타낼 수 있다.

a ∉ A

" 원소 a 는 집합 A 에 속하지 않는다. "

• ∈ 는 원소를 뜻하는 Element 의 첫 글자를 기호화 하였다.
• 일반적으로 원소는 소문자, 집합은 대문자로 표현한다.
• n(A) : 집합 A 의 원소의 개수

두 집합 A, B 에서 집합 A의 모든 원소가 집합 B에 포함되는 경우. A 를 집합 B의 부분집합이라고 말한다. 

A ⊂ B

" 집합 A 는 집합 B에 포함된다. "

진부분집합은 부분집합 중에서 자기자신을 제외한 부분집합을 의미한다. 

A ⊂ B 이고 A ≠ B

" A는 B의 진부분집합이다. "

부분집합의 개수

n(A) = n 일 때,

• 집합 A 의 부분집합의 개수 = 2^n

• 집합 A 의 진부분집합의 개수 = 2^n - 1

• 특정원소 k 개를 포함하지 않는 부분집합의 개수 = 2^(n-k)

• 특정원소 k 개를 포함하는 부분집합의 개수 = 2^(n-k)

• 특정원소 k 개 중 적어도 한 개를 포함하는 부분집합의 개수 = 2^n - 2^(n-k)

위의 공식에서 집합 A의 부분집합의 개수가 2^n 이 되는 경우의 해당 내용에 대한 증명을 하기 위해서는 원소의 개수가 1인 경우, 2인 경우, 3인 경우, n 인 경우를 통해 귀납적 증명이 가능하다. 

집합 내의 원소들을 소유하고 있는지 / 소유하고 있지 않은지에 따라서 두 가지 경우의 수로 생각해볼 수 있다. 더불어서 기본적으로 부분집합에는 공집합이 포함되기에 2^n 이 된다. 진부분집합의 경우에는 자기 자신을 제외하였기 때문에 마지막에 -1 을 붙여준다.

참고자료

https://mathbang.net/286