[이산수학] 집합

집합이란?

---

집합이란 공통적인 성질을 가진 객체들의 모임이다. 집합의 개념은 수학의 모든 분야에 있어서 기초가 될 뿐만 아니라 일상생활에서도 많이 사용하는 개념으로 현대 수학의 가장 중요한 개념이라고 할 수 있다. 먼저 집합에서 쓰이는 용어들의 정의에 대해서 알아보자.

• 집합(set): 명확한 기준에 따라 동통 성질을 가지며 중복되지 않는 원소(element 또는 member)의 모임이다. 대문자 A, B, C등으로 표시한다.
• 유한집합(finite set): 집합을 구성하는 원소의 개수가 유한개인 집합이다.
• 무한집합(infinite set): 집합을 구성하는 원소의 개수가 무한히 많은 집합이다.
• 원소(element 또는 member): 집합을 구성하는 객체이다. 소문자 a,b,c,...등으로 표시한다.
• 기수(cardinality: |A|): 집합 A에 포함되는 원소의 개수이다.
• “a가 집합 A의 원소이다.”는 a∈A라고 표시, “a가 집합 A의 원소가 아니다.“는 a∉A라 표시한다.

 

집합의 표기방식

---

집합의 표기방식에는 3가지가 있다.

• 원소나열법: 집합에 포함되는 원소들을 일일이 나열하는 방법이다.

예) A = {1, 2, 3, 4, 5}

• 조건제시법: 집합에 포함되는 원소들의 공통 성질을 조건식으로 제시하는 방법이다.

예) A = { x | 0 < x <=6, x∈R }

• 벤 다이어그램: 집합과 원소 또는 집합과 집합의 포함관계를 그림으로 보여주는 방법이다.

예)

벤 다이어그램

 

집합의 종류

---

집합의 종류에는 셀 수 있는/없는 무한/유한 집합이 있다. 셀 수 있다는 것은 무엇일까?

• 셀 수 있다는 것: 자연수와 1:1 대응이 되어야 한다.예를 들어 짝수(2, 4, 6, 8, ...)는 자연수(1, 2, 3, 4, ...)와 1:1 대응이 되므로(1x2=2, 2x2=4, 3x2=6, 4x2=8, ...) 셀 수 있다. 반면에 0과 1 사이에 있는 실수는 자연수와 1:1 대응이 되지 않으므로 셀 수 없다.

유한과 무한은 어떻게 구분할까?

• 무한집합: 집합 A의 적당한 진부분 집합 S가 존재해서, A와 S 사이에 1:1 대응이 존재하는 집합이다. 자연수 집합 N은 N의 진부분 집합인 짝수의 집합과 1:1 대응이 존재한다. 따라서 자연수 집합은 셀 수 있는 무한집합이다.

 

집합에 대한 다른 개념들은 다음과 같다.

• 전체집합(universal set: U): 논의 대상이 되는 원소 전체를 포함하는 집합을 말한다.
• 공집합(empty set: Φ 또는 { }): 원소를 하나도 포함하지 않는 집합으로 기수가 0인 집합이다.(|Φ| = 0)
• 상등(equal: A = B): 두 집합 A, B 각각에 속하는 원소들이 모두 종일할 때, '두 집합 A와 B가 서로 같다' 또는 '두 집합 A와 B는 서로 상등이다'라고 한다.(A = B ↔ ∀a(a∈A  ↔ a∈B)
• 부분집합(subset: A⊆B): 집합 A의 모든 원소가 집합 B에 포함될 때, 집합 A는 집합 B의 부분집합을 말한다.(|A| <= |B|)
• 진부분집합(proper subset: A⊂B): 집합 A의 모든 원소가 집합 B에 포함되지만 집합 A와 집합 B가 상등이 아닐 때, 집합 A는 집합 B의 진부분집합이라고 한다.(|A| < |B|)
• 멱집합(power set): 집합 A에 대하여, A의 모든 부분집합을 모은 집합을 A의 멱집합이라 하고, P(A)로 표시한다.

A={1,2} 라고 하자. A의 부분집합은 ∅,{1},{2},{1,2}이다. 그러므로 P(A)={∅,{1},{2},{1,2}}이다. 멱집합의 원소의 개수는 2^(|A|)개이다.

 

집합의 연산

---

• 합집합(union: A∪B): 집합 A와 B에 모두 속하거나 둘 중 한 집합에만 속하는 원소들로 이루어진 집합이다. A∪B = {x | x∈A ∨ x∈B}
• 교집합(intersection: A∩B): 집합 A와 B 모두에 속하는 원소들로 이루어진 집합이다.               A∩B = {x | x∈A ∧ x∈B}
• 서로소(disjoint): 집합 A와 B에 공통으로 포함되는 원소가 하나도 없는 경우이다. A∩B = ∅
• 차집합(difference: A-B): 집합 A에는 포함되지만 집합 B에는 포함되지 않는 원소들의 집합이다. A-B = {x | x∈A ∧ x ∉B}
• 대칭차집합(symmetric difference: A⊖B or A△B): 집합 A에만 포함되거나 집합 B에만 포함되는 원소들의 집합이다. A⊖B = {x | x∈(A-B) ∨ x ∈(B-A)}
• 여집합 또는 보집합(complement set: A' 또는 AC): 전체집합 U에는 포함되지만 집합 A에는 포함되지 않는 원소들로 구성된 집합이다. A' = {x | x∈U ∧ x∉A} = U-A,   | A'| = |U|-|A|
• 곱집합(product set: AXB): 집합 A, B에 대하여 a∈A, b∈B일 때, 순서쌍 (a,b)의 집합이다.     AXB = {(a,b) | a∈A ∧ b∈B},   |AXB| = |A|x|B|
• 멱집합(power set: P(A)): 원소가 n개인 집합 A에 대하여, 가능한 모든 부분집합을 원소로 갖는 집합이다. P(A) = {B | B ⊆ A},   |P(A)| = 2^n

 

집합의 대수법칙

---

기본적인 집합의 대수법칙은 다음과 같다.

집합 연산		법칙
A∪∅=A	A∩U=A	항등법칙 (identity law)
A∪U=U	A∩∅=∅	지배법칙 (domination law)
A∪A=A	A∩A=A	멱등법칙 (idempotent law)
A∪B=B∪A	A∩B=B∩A	교환법칙 (commutative law)
A∪(B∪C)=(A∪B)∪C A∩(B∩C)=(A∩B)∩C		결합법칙 (associative law)
A∪(B∩C)=(A∪B)∩(A∪C) A∩(B∪C)=(A∩B)∪(A∩C) A×(B∩C)=(A×B)∩(A×C) A×(B∪C)=(A×B)∪(A×C) A×(B−C)=(A×B)−(A×C)		분배법칙 (distributive law)
(A')'=A		이중 보법칙 (double complement law)
A∪A'=U ∅'=U	A∩A'=∅ U'=∅	보법칙 (complement law)
(A∪B)'=A'∩B'	(A∩B)'=A'∪B'	드모르간의 법칙 (De Morgan's law)
A∪(A∩B)=A	A∩(A∪B)=A	흡수법칙 (absorption law)

 

집합의 분할

---

• 분할(partion: A = {A1, A2, ..., An}): 공집합이 아닌 임의의 집합 A를 서로소이면서 공집합이 아닌 하나 이상의 부분집합(A1, A2, ..., An)으로 나누는 것이다.
• 분할의 조건(i = 1, 2, ..., n)

1. Ai ≠ ∅
2. i ≠ j이면, Ai∩Aj = ∅
3. Ai ⊆ A
4. A = A1∪A2∪...∪An

• 집합류(set class: Ai): 집합 A에 대하여 분할된 부분집합을 말한다.

집합의 분할과 집합류

 

궁금한 것이나 잘못된 것이 있다면 댓글에 남겨주세요!