개념
- 순진한 정의
- 집합: 구별 가능한 것들의 모임
- 원소: 집합에 들어 있는 대상들
- 공집합: a ∉ ∅
- 원소 나열법
- A = { a, b, c }
- 조건 제시법
- a ∈ { p(x) | q(x) }
- 상등
- A = B ⇔ ∀z, z ∈ A ⇔ z ∈ B
- { a, a, b } = { a, b }
- 부분집합
- A ⊆ B ⇔ ∀z, z ∈ A ⇒ z ∈ B
- 집합의 크기
- | A | : A의 원소의 개수 (A는 유한집합)
- 멱집합(power set)
- P(A) : A의 부분집합들을 모은 집합
- { x | x ∈ A }
- | A | = 2 ⇒ | P(A) | = 2n
- 합집합
- A ∪ B = { x | x ∈ A ∨ x ∈ B }
- 교집합
- A ∩ B = { x | x ∈ A ∧ x ∈ B }
- 차집합
- A ∖ B = { x | x ∈ A ∧ x ∉ B }
- 여집합
- AC = U ∖ A
- 공집합은 모든 집합의 부분집합
- 공집합은 unique 하다
집합식
- A ⊆ B ∧ B ⊆ A ⇔ A = B
- A ⊆ B ∧ B ⊆ C ⇒ A ⊆ C
- A ∪ A = A
- A ∩ A = A
- A ∪ B = B ∪ A
- A ∩ B = B ∩ A
- A ∪ (B ∪ C) = (A ∪ B) ∪ C
- A ∩ (B ∩ C) = (A ∩ B) ∩ C
- A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
- (AC)C = A
- ∅C = U, UC = ∅
- (A ∪ B)C = AC ∩ BC
- (A ∩ B)C = AC ∪ BC
- A ⊆ B ⇔ A ∪ B = B
- A ⊆ B ⇔ A ∩ B = A
- A ⊆ B ⇔ A ∖ B = ∅
- A ⊆ B ⇔ BC ⊆ AC
- A ∪ U = U
- A ∩ U = A
- A ∪ ∅ = A
- A ∩ ∅ = ∅