2.3 집합의 연산

2.1 집합과 부분집합

Theorem 1 임의의 집합 A, B, C에 대하여, 다음이 성립한다.

1. A = A

2. A = B =⇒ B = A

3. A = B and B = C =⇒ A = C 4. A ⊆ B and B ⊆ A =⇒ A = B 5. A ⊆ B and B ⊆ C =⇒ A ⊆ C.

Proof.

1. x ∈ A =⇒ x ∈ A and x ∈ A =⇒ x ∈ A는 사실이므로 집합의 상등 정 의에 의하여 A = A 이다.

2. A = B 라 하자. 그러면, 논리규칙의 교환법칙에 의하여 x ∈ A =⇒ x ∈ B ≡ x ∈ B =⇒ x ∈ A 따라서 B = A.

3. A = B 이고 B = C 라 하자. 그러면

x ∈ A =⇒ x ∈ B (1)

x ∈ B =⇒ x ∈ A (2)

x ∈ B =⇒ x ∈ C (3)

x ∈ C =⇒ x ∈ B (4)

위 명제의 (1), (3) 에 의하여

x ∈ A =⇒ x ∈ C

(2), (4) 에 의하여

x ∈ C =⇒ x ∈ A 따라서 A = C.

4,5 는 3과 같은 방식으로 증명할 수 있다. ♠

2.3 집합의 연산

Theorem 2 공집합 ∅은 임의의 집합의 부분집합이다.

Proof. 임의의 집합 A에 대하여 ∅ ⊆ A를 보이려면 x ∈ ∅ =⇒ x ∈ A

를보이면 된다. 이는 참인 명제

x /∈ A =⇒ x /∈ ∅

의 대우이다. 따라서 ∅ ⊆ A ♠

Theorem 4 임의의 두 집합 A, B에 대하여 (1) A ⊆ B ⇐⇒ A ∪ B = B

(2) A ⊆ B ⇐⇒ A ∩ B = A Proof.

(1) B ⊆ A ∪ B 이므로 A ∪ B ⊆ B 임을 보이면 된다.

x ∈ A ∪ B =⇒ x ∈ A and x ∈ B by Definition

=⇒ x ∈ B and x ∈ A

=⇒ x ∈ B and x ∈ B

=⇒ x ∈ B 따라서 A ∪ B ⊆ B 이므로 A ∪ B = B.

(2) A ∩ B ⊆ A 이므로 A ⊆ A ∩ B 임을 보이면 된다.

x ∈ A =⇒ x ∈ A and x ∈ A

=⇒ x ∈ A and x ∈ B

=⇒ A ⊆ A ∩ B

따라서 A ∩ B = A ♠

Theorem 5 임의의 두 집합 A, B에 대하여 (1) A ∪ (A ∩ B) = A

(2) A ∩ (A ∪ B) = A Proof.

(1) Theorem 3에 의하여, A ∩ B ⊆ A 이므로 A ∪ (A ∩ B) = A.

(2) Theorem 3에 의하여, A ⊆ A ∪ B 이므로 A ∩ (A ∪ B) = A. ♠ Theorem 6 임의의 집합 A 에 대하여, (A^c)^c = A.

Proof.

x ∈ (A^c)^c=⇒ x /∈ A^c

=⇒ x ∈ A

=⇒ (A^c)^c ⊆ A

x ∈ A =⇒ x /∈ A^c

=⇒ x ∈ (A^c)^c

=⇒ A ⊆ (A^c)^c

따라서 (A^c)^c= A. ♠

Theorem 7 (DeMorgan의 정리) 임의의 두 집합 A, B에 대하여, (1) (A ∪ B)^c= A^c∩ B^c

(2) (A ∩ B)^c= A^c∪ B^c

Proof.

(1)

x ∈ (A ∪ B)^c=⇒ x /∈ A ∪ B

=⇒ x /∈ A and x /∈ B

=⇒ x ∈ A^c and x ∈ B^c

=⇒ x ∈ A^c∩ B^c

x ∈ A^c∩ B^c =⇒ x ∈ A^c and x ∈ B^c

=⇒ x /∈ A and x /∈ B

=⇒ x /∈ A ∪ B

=⇒ x ∈ (A ∪ B)^c

(2) (1) 과 같은 방법이므로 생략. ♠

Theorem 8 임의의 두 집합 A, B, C 에 대하여

(1) 교환법칙 (i) A ∪ B = B ∪ A (ii) A ∩ B = B ∩ A (2) 멱등법칙 (iii) A ∪ A = A (iv) A ∩ A = A

(3) 결합법칙 (v) A ∪ (B ∪ C) = (A ∪ B) ∪ C (vi) A ∩ (B ∩ C) = (A ∩ B) ∩ C

(4) 배분법칙 (vii) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (viii) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

Proof. 논리규칙의 교환, 항등, 결합, 분배법칙 그대로이므로 증명은 생략.

♠

Theorem 9 모든 집합 A에 대하여, (1) A ∪ ∅ = A

(2) A ∩ ∅ = ∅ (3) A ∩ A^c= ∅

Proof.

(1) ∅ ⊆ A 이므로 A ∪ ∅ = A.

(2) A ∩ ∅ ⊆ ∅ 이므로 A ∩ ∅ = ∅.

(3)

x ∈ A ∩ A^c =⇒ x ∈ A and x /∈ A

=⇒ x ∈ ∅

=⇒ A ∩ A^c⊆ ∅

따라서 A ∩ A^c= ∅. ♠

Example 앞의 정리들을 이용하여 다음을 증명하여라.

A ∩ (A^c∪ B) = A ∩ B.

Proof.

A ∩ (A^c∪ B) = (A ∩ A^c) ∪ (A ∩ B)

= ∅ ∪ (A ∩ B)

= A ∩ B

♠ Example A − B = B^c− A^c임을보여라.

Proof.

A − B = A ∩ B^c

= B^c∩ A

= B^c∩ (A^c)^c

= B^c− A^c

♠