[DiscreteMath]집합론

📚기본사항

집합론에서 집합과 원소는 무정의 용어입니다. 무정의 용어란 직관적으로 이해할 수 있는 정의 없이 사용하는 용어를 가리킵니다.

집합을 서술하기 위해 일반적으로 원소나열법과 조건제시법을 사용합니다.

• 원소나열법
  {a, b, c}와 같이 원소를 직접 나열하는 방식입니다.

• 조건제시법
  {x|x는 0이 아닌 정수}와 같이 원소들의 논리적 관계를 기술하는 방식입니다.

📄부분집합

집합들 사이에 포함관계가 있을 때 부분집합으로 나타냅니다. 집합 A의 모든 원소가 집합 B에 포함될 경우 A ⊂ B 또는 A ⊆ B로 나타냅니다. 또한 A는 B의 부분집합이라고 합니다.

• 진부분집합
  A가 B의 부분집합이고 A와 B가 같지 않다면 A는 B의 진부분집합이라고 합니다.

• 상동
  집합 A와 B에 대하여 A의 모든 원소가 B에 포함되고 B의 모든 원소가 A에 포함되면 A와 B는 상동입니다.

• 공집합
  원소가 하나도 없는 집합을 공집합이라고 합니다. 기호로 { }나 ø를 사용합니다. 공집합은 모든 집합의 부분집합으로 약속합니다. { ø }은 공집합을 원소로 가지고 있는 집합이므로 공집합 ø와는 다릅니다.

📄분할

• 서로소
  집합 A와 B가 공통된 원소를 가지고 있지 않은 경우 서로소라고 합니다.
  

\[A ∩ B = ø\]

• 쌍으로 서로소
  n개의 집합 A₁, A₂, …, A_n이 있을 때 서로 다른 임의의 두 집합 A_i와 A_j가 공통된 원소를 가지고 있지 않을 경우 쌍으로 서로소라고 합니다.

\[i ≠ j일\,때,\;A_i ∩ A_j = ø\]

• 분할
  집합 A를 ø이 아닌 부분집합으로 나눴을 때 A의 모든 원소들이 나누어진 부분집합들 중 하나에만 포함되어 있을 경우, 이 부분집합들을 원소로 하는 집합을 A의 분할이라고 합니다.
  
  분할의 조건
  
  1. i = 1, …, n에 대하여 A_i는 ø이 아니면서 A의 부분집합이다.
  2. A = A₁ ∪ A₂ ∪ A₃ … ∪ A_n
  3. A₁, A₂, A₃ …, A_n은 쌍으로 서로소이다.
     
     📍집합 {1, 2, 3}의 모든 분할을 구하시오.
     {{1}, {2}, {3}}
     {{1, 2}, {3}}
     {{1, 3}, {2}}
     {{1}, {2 ,3}}
     {{1, 2, 3}}

📄멱집합

집합 A에 대하여 A의 모든 부분집합들의 집합을 A의 멱집합이라고 합니다. P(A)로 나타냅니다.

📍집합 A = {1, 2, 3}, A의 멱집합을 구하시오.
P(A) = { ø, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

📚집합연산

📄합집합

전체집합 U가 있고 집합 A와 B가 U의 부분집합일 때, A에 속하거나 B에 속하는 원소의 집합을 A와 B의 합집합이라고 합니다.

\[A ∪ B = \{x∈U\,|\,x∈A\,∨\,x∈B\}\]

📄교집합

전체집합 U가 있고 집합 A와 B가 U의 부분집합일 때, A에 속하고 B에도 속하는 원소의 집합을 A와 B의 교집합이라고 합니다.

\[A ∩ B = \{x∈U\,|\,x∈A\,∧\,x∈B\}\]

📄차집합

전체집합 U가 있고 집합 A와 B가 U의 부분집합일 때, A에는 속하지만 B에는 속하지 않는 원소의 집합을 A에서 B를 뺀 차집합이라고 합니다.

\[A – B = \{x∈U\,|\,x∈A\,∧\,x∉B\}\]

📄여집합

전체집합 U가 있고 집합 A와 B가 U의 부분집합일 때, 전체집합 U에 속하면서 A에는 속하지 않는 원소의 집합을 A의 여집합이라고 합니다.

\[A^c = \{x∈U\,|\,x∉A\}\]

📄대칭차집합

전체집합 U가 있고 집합 A와 B가 U의 부분집합일 때, A ∪ B에 속하지만 A ∩ B에 속하지 않는 원소의 집합을 A와 B의 대칭차집합이라고 합니다.

\[A ⊕ B = \{x∈U\,|\,x∈(A∪B) ∧ x∉(A ∩ B)\}\]

📄곱집합

전체집합 U가 있고 집합 A와 B가 U의 부분집합일 때, A에 속하는 원소 a와 B에 속하는 원소 b에 대하여 모든 순서쌍 (a, b)의 집합을 A와 B의 곱집합이라고 합니다.

\[A × B = \{(a,b)\,|\,a∈A\,∧\,b∈B\}\]

📚집합의 대수법칙

📄합집합의 크기

집합 A, B가 유한집합이면 다음 식이 성립합니다.
|A ∪ B| = |A| + |B| - |A ∩ B|

📄서로소인 합집합의 크기

집합 A, B가 유한집합이면서 서로소이면 |A ∪ B| = |A| + |B|입니다.

📄교집합, 합집합, 포함관계의 이행성

모든 집합 A, B, C에 대해 다음을 만족합니다.

교집합
(A ∩ B) ⊆ A
(A ∩ B) ⊆ B

합집합
A ⊆ (A ∪ B)
B ⊆ (A ∪ B)

이행성
만약 A ⊆ B이고 B ⊆ C이면, A ⊆ C입니다.

• 원소논증
  집합의 대수법칙을 증명하는 가장 기본적인 방법입니다. 하나의 집합이 다른 집합의 부분집합임을 증명하기 위해 원소의 포함관계를 이용하는 증명방식입니다.
  
  

\[집합\,X와\,Y가\,주어지고\,X\,⊆\,Y임을\,증명하고자\,한다면, \\ X의\,임의의\,원소\,x에\,대해서\,항상x\,∈\,Y가\,만족함을\,보인다.\]

📄집합의 대수법칙

U를 전체집합이라고 할 때 모든 집합 A, B, C에 대해 다음을 만족합니다.

• 교환법칙
  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)
  A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

• 항등법칙
  A ∪ ∅ = A
  A ∩ U = A

• 보수법칙
  A ∪ A^c = U
  A ∩ A^c = ∅

• 이중보수법칙
  (A^c)^c = A

• 멱등법칙
  A ∪ A = A
  A ∩ A = A

• 전체한계법칙
  A ∪ U = U
  A ∩ ∅ = ∅

• 드모르간법칙
  (A ∪ B)^c = A^c ∩ B^c
  (A ∩ B)^c = A^c ∪ B^c

• 흡수법칙
  A ∪ (A ∩ B) = A
  A ∩ (A ∪ B) = A

• U와 ∅의 여집합
  U^c = ∅
  ∅^c = U

• 차집합법칙
  A - B = A ∩ B^c

📄포함관계에 대한 동치

전체집합 U가 있고 집합 A와 B가 있을 때, 다음 조건 중 하나가 참일 때 나머지 다른 조건도 모두 참이 되고, 다음 조건 중 하나가 거짓이라면 나머지 다른 조건도 모두 거짓이 됩니다. 다음 조건들 모두 동치입니다.

• A ⊆ B
• B^c ⊆ A^c
• A ∪ B = B
• A ∩ B = A
• A^c ∪ B = U
• A ∩ B^c = ∅
• A - B = ∅