집합

집합

수학적 성질을 가지는 객체들의 모임
집합은 정확하게 정의되어야 하며, 어떤 객체가 그 집합에 속하는지 아닌지를 분명히 구분할 수 있어야 한다.
중복되는 원소가 없어야 한다.

원소 나열법
집합의 원소들을 { } 사이에 하나씩 나열하는 방법
의미가 명확한 경우 모든 원소를 나열하는 대신에 ...이용
조건 제시법
집합의 원소들이 가지고 있는 특정한 성질을 기술하여 나타내는 방법

S={x|x는 자연수이고 1≤x≤5}

---

Cardinality: 집합S 내에 있는 서로 다른 원소들의 개수, 원소 수, |S|

유한 집합
무한 집합

가산적 집합(Countable Set): 정수의 집합과 일대일 대응 관계에 있는 집합들. Countably infinite Set 이라고도 한다.
유리수들과 알파벳 $\sum$로 부터 만들어지는 유한한 길이의 스트링들의 집합 $\sum^*$는 모두 가산적 집합이다.

전체 집합(Universal Set): 집합론에서 관심을 두는 모든 원소의 집합(U)

공집합(Empty Set): 어떤 원소도 가지지 않는 집합({ }, ∮)

부분 집합(Subset): 집합 A의 모든 원소가 집합 B에 속하면 '집합 A는 B에 포함된다.'고 한다. (A⊆B) 이 때 A는 B의 부분 집합.
진부분 집합(Proper Subset): A⊆B 이고 , A≠B 경우에 A를 B의 진 부분 집합이라 한다.(A⊂B)

여집합(Complement Set): 전체집합 U와 그것의 부분집합 A에서 U에 속하나 A가 아닌 원소들의 집합을 A의 여집합 이라고 한다. ($A^C$, $A'$)

합집합 A∪B
교집합 A∩B
차집합 A-B

서로소: $A∩B≠∮$ 인 경우, A와 B가 공통된 원소를 하나도 가지지 않은 경우

대칭 차집합(symmetric Difference):(A⊕B), A∪B의 원소 중 A∩B에 속하지 않는 모든 원소들의 집합

순서쌍(odered pair): 순서로 구분되는 원소들의 쌍, (a,b)와 같이 나타낸다. a≠b 이면 (a,b)≠(b,a), (a,b)=(c,d)이면 a=c b=d

곱집합, 카디시안 곱(Cartesian Product): x∈A 이고 y∈B인 모든 순서쌍 (x,y)의 집합, AxB, (n개의 집합으로 확장 가능)

집합 연산의 카디날리티

집합의 대수법칙

멱등 법칙(idempotent law): A∪A=A, A∩A=A
항등 법칙(identity law):A∪∮=A, A∩∮=∮, A∪U=U, A∩U=A
교환 법칙(commutative law): A∪B=B∪A, A∩B=B∩A
결합 법칙(associative law): A∪(B∪C)=(A∪B)∪C, A∩(B∩C)=(A∩B)∩C
분배 법칙:(distributive law): A∪(B∩C)=(A∪B)∩(B∪C), A∩(B∪C)=(A∩B)∪(B∩C)
흡수 법칙(absorption law): (A∩B)∪A=A, (A∪B)∩A=A
보 법칙(compliment law):$(A^c)^c$=A
역 법칙(inverse law): $A∪A^c=U, A∩A^c=∮, U^c=∮, ∮^c=U$
드 모르간의 법칙(De morgan's law):$(A∪B)^c=A^c∩B^c, (A∩B)^c=A^c∪B^c$
기타: $A-B=A∩A^c ,\ A-A=∮,\ A-∮=A$

---

쌍대(duality): 집합에 관한 명제에서 그 명제 안에 있는 교집합과 합집합을 전체 집합에 대한 여집합으로 바꾸어서 만든 새로운 명제

'집합에 관한 명제에서 합집합, 교집합, 그리고 공집합과 전체집합을 서로 바꾼 명제'

집합류(class): 어떤 집합 A에 대해 A의 원소의 개수가 n개일 때 A의 부분 집합의 개수는 $2^n$ 이러한 부분 집합의 모임을 집합류라고 한다. (집합의 집합)

멱집합(Power set)

임의의 집합 S에 대하여, 모든 부분 집합을 원소로 가지는 집합을 집합S의 멱집합이라 한다.(P(s)), $2^s$
개수: $|P(s)|=2^{|s|}$

• 멱집합은 집합류
• 멱집합을 구할 때 개수가 $2^{|A|}$가 되는지 확인한다.
• 멱집합의 원소는 모두 집합이다. ∮을 제외하고 모두 중괄호
• 원래 집합A의 원소 중 집합인 원소가 있을 때에는 추가적인 집합 표시가 필요하다. {a}⊂A, {{a}}⊂P(A)

집합의 분할(partition)

S를 공집합이 아닌 임의의 집합이라고 할 때 집합 S의 분할$\pi$는 다음의 3 조건을 만족해야 한다. $\pi$={$A_1,A_2,...,A_k$}
1. i=1, ..., k에 대하여 $A_i$는 공집합이 아닌 집합 S의 부분 집합이다.
2. S=$A_1∪A_2∪...∪A_k$
3. $A_i$ 들 사이는 서로소이다. i≠j 이면$A_i∩A_j=∮$이다.
분할의 원소인 $A_i$를 분할의 블록이라고 한다.