2.1. 집합
“집합”(Set)은 공통적인 성질을 가진 “객체”(Object)들의 “모임”(Collection)입니다.
집합을 구성하는 객체를 “원소”(Element 또는 Member)라고 표현합니다.
“\(x\)가 집합 \(S\)의 원소이다.” 는 “\(x ∈ S\)” 로 표현하고, 반대로 “\(x\)는 집합 \(S\)의 원소가 아니다.” 는 “\(x ∉ S\)” 로 표현합니다.
집합을 표현하는 방법으로는 두 가지 방법으로 표현 할 수 있습니다.
1). 원소나열법 : \(S\)의 원소들이 \(1\)부터 \(10\)까지라고 한다면, \(S = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\) 이라고 표현 할 수 있습니다.
main = do
--원소나열법
let s1 = [3, 4, 5, 6, 7]
print $ s12). 조건제시법 : \(S\)의 원소들이 \(1\) 보다 크고 \(10\)보다 작은 자연수라면,
\(S = \{a | a ∈ ℕ, a > 1 , a < 10\}\) 라고 표현 할 수 있습니다.
main = do
--조건제시법
let s2 = [a | a <- [1..10], a > 2, a < 8]
print $ s2“집합의 크기”(Cardinality)는 집합의 원소의 개수를 집합의 크기라고 정의합니다.
집합의 크기표현은 “\(| S |\)“로 표현 하고, 값은 “기수”(Cardinal Number)라고 표현합니다.
기수는 보통 자연수와 \(0\)으로 표기합니다.
집합의 종류는 “가산”, “비가산”의 여부와 “유한”, “무한”의 여부 두 가지를 보고 결정합니다.
“가산”(Countable)은 집합이 이산적으로 정의 할 수 있다는 것이고, 자연수와 일대일 대응을 할 수 있습니다.
수열이나, 자연수집합 자신도 물론 가산의 범주에 포함됩니다.
“비가산”(Uncountable)은 집합이 이산적으로 정의되지 않는다는 것이며,
자연수와 일대일 대응되지 않는 값들이 반드시 존재합니다.
실수나 무리수집합의 경우 자연수집합으로 대응을 시키려고 해도
대각선논법등에 의해 대응되지 않는 값들이 반드시 존재하므로 비가산의 범주에 포함됩니다.
“유한”(Finite)은 집합의 원소가 유한하다는 의미이고, 유한한 집합의 원소를 나열법으로 작성 가능하다는 의미입니다.
“무한”(Infinite)은 집합의 원소가 무한하다는 의미이고, 엄밀하게는 원소 나열법으로 작성이 불가하고,
조건제시법으로만 정의됩니다.
두 집합의 각 원소가 같은 값끼리 하나씩 일대일 대응하여 두 집합의 모든 원소들의 페어를 찾아내면,
두 집합은 “같다”(Equal)고 할 수 있고, 두 집합 \(A, B\) 가 같으면, \(A = B\)라고 표현 할 수 있습니다.
집합 \(A\)의 모든 원소 \(a\)가 집합 \(B\)에 존재한다면, ” \(A ⊆ B\) ” 로 표현 가능하고
\(A\)는 \(B\)의 “부분집합”(Subset)이라고 표현합니다.
( 해석학 1.1절에서도 그렇고 부분집합을 “\(⊆\)” 대신 “\(⊂\)” 을 사용하는데,
\(⊂\)는 원래 “진부분집합”(Proper Subset) 기호이지만, 편의상 부분집합 기호로 구별없이 사용하겠습니다. )
다루는 대상을 모두 포함하는 집합을 “전체집합”(Universal Set)이라고 표현하고 보통 “\(U\)“를 사용합니다.
( 전체집합은 집합론의 가능한 모든 범위들의 상위집합으로 표현하려는 의도로 사용되었지만,
“러셀의 역설”등의 논리적 모순을 피하지 못해서 현재는 일반적으로 허용되지 않는 개념입니다. )
반대로, 원소가 하나도 없는 집합을 “공집합”(Empty Set)이라고 표현하고 “\(∅\)“로 표현합니다.
전체집합과 공집합은 여 관계라고 볼 수 있습니다. ( 즉, \(U = ∅^c\) 또는 \(∅ = U^c\) )
“멱집합”(Power Set)은 어떤 집합의 모든 부분집합을 원소로 가지는 집합을 의미합니다.
어떤 집합 \(A\)가 존재할 때, \(A\)의 멱집합은 “\(P(A)\)” 로 표현 할 수 있습니다.
2.2. 집합의 연산
\(\{x | x ∈ A ∨ x ∈ B\}\) , (조건 제시법 \(A\)의 원소 조건 또는 \(B\)의 원소 조건에 충족되는 원소\(x\)로 이루어진 집합) 을
“ \(A ∪ B\) ”, “\(A\)와 \(B\)의 합집합”라고 표현 합니다.
\(∪\) 기호에서 윗첨자와 아랫첨자가 붙은 기호는 아랫첨자 부터 윗첨자까지의 값들을 전부 합 연산 한다는 의미입니다.
예를들어 \(∪_{i=1}^{3}{A_i}\) 는 \(A_1 ∪ A_2 ∪ A_3\) 를 의미합니다.
\(\{x | x ∈ A ∧ x ∈ B\}\) , (조건 제시법 \(A\)의 원소 조건 과 \(B\)의 원소 조건에 충족되는 원소\(x\)로 이루어진 집합) 을
“ \(A ∩ B\) ”, “\(A\)와 \(B\)의 교집합”라고 표현 합니다.
\(∩\) 기호에서 윗첨자와 아랫첨자가 붙은 기호는 아랫첨자 부터 윗첨자까지의 값들을 전부 교 연산 한다는 의미입니다.
예를들어 \(∩_{i=2}^{4} {A_i}\) 는 \(A_2 ∩ A_3 ∩ A_4\) 를 의미합니다.
두 집합 \(A, B\) 가 \(A ∩ B = ∅\) 이면, \(A\)와 \(B\)는 “서로소”,(Disjoint)라 표현 합니다.
또한, 여러 집합 \(A_1, \ldots, A_i\) 가 \(A_j ∩ A_k = ∅ : ∀ j, k ⊂ {1, \ldots, i} , j ≠ K\) 이면,
여러집합들을 “상호서로소”(Mutually Disjoint)라고 표현합니다.
어떤집합 \(S\)가 상호서로소인 여러 집합 \(A_1, \ldots, A_i\) 의 합( \(∪\) )으로 표현될 수 있다면,
이를 집합 \(S\)의 “분할”(Partition)이라고 표현합니다. (이때, 분할 가능한 \(S\)를 “가족집합”(Family Set)이라고 표현합니다.)
\(\{x | x ∈ A ∧ x ∉ B\}\) , (조건 제시법 \(A\)의 원소 조건 과 \(B\)의 원소가 아닌 조건에 충족되는 원소\(x\)로 이루어진 집합) 을
“ \(A – B\) ”, “\(A\)와 \(B\)의 차집합”라고 표현 합니다.
“여집합”(Complement)은 전체집합에는 포함되지만, 특정집합에는 포함되지 않는 경우,
특정집합의 여집합이라고 표현 할 수 있습니다. 집합 \(A\)의 여집합은 \(A^c\)로 표현 할 수 있습니다.
“대칭 차집합”(Symmetric Difference)은 어떤 두집합이 있을 때,
두 집합의 합집합에 교집합을 차집합 한 집합을 표현합니다.
어떤 두 집합 \(A, B\)가 존재할 때, 대칭차집합을 ” \(A △ B\) ” \(= ( A ∪ B ) – ( A ∩ B )\) 라고 표현 할 수 있습니다.
2.3. 집합의 성질과 증명법
여러집합 \(A_1, \ldots, A_i\) 의 합집합의 원소들의 개수를 셀 때, 서로가 상호 서로소이고 분할된 형태로 값을 구한다면,
단순 덧셈으로 합집합의 원소들의 개수를 구할 수 있지만, 상호서로소가 아닌 경우는 조금 더 복잡합니다.
“포함배제의 원리”(Inclusion-Exclusion Principle)는 위의 문제를 해결하는 방법입니다.
포함배제 원리는 각집합의 원소들을 일단 단순 덧셈을 하고 이후 둘 사이의 교집합을 빼고
다시 셋사이의 교집합을 더하고 \(\ldots\) 를 반복하여 값을 구하는 방법입니다.
두 집합 \(A, B\) 가 상호서로소가 아닐 때, \(| A ∪ B | = | A | + | B | – | A ∩ B |\) 으로 정의 할 수 있습니다.
세 집합 \(A, B, C\) 가 상호서로소가 아닐 때,
\(| A ∪ B ∪ C | = | A | + | B | + | C | – | A ∩ B | – | B ∩ C | – | A ∩ C | + | A ∩ B ∩ C |\) 으로 정의 할 수 있습니다.
집합에 관한 명제에서 합집합”\(∪\)” 와 교집합”\(∩\)” , 전체집합 “\(U\)” 와 공집합 “\(∅\)” 을
서로 바꾸어 정의한 명제를 원래 명제의 “쌍대”(Duality)라고 표현합니다.
쌍대명제에 해당하는 법칙은 7가지가 있습니다.
1). 교환법칙 : \(A ∪ B = B ∪ A => A ∩ B = B ∩ A\)
2). 결합법칙 : \(A ∪ ( B ∪ C ) = ( A ∪ B ) ∪ C => A ∩ ( B ∩ C ) = ( A ∩ B ) ∩ C\)
3). 분배법칙 : \(A ∩ ( B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C ) => A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C )\)
4). 멱등법칙 : \(A ∪ A = A => A ∩ A = A\)
5). 여법칙 : \(A ∪ A^c = U , ∅^c = U => A ∩ A^c = ∅ , U^c = ∅\)
6). 드 모르간 법칙 : \(( A ∩ B )^c = A^c ∪ B^c => ( A ∪ B )^c = A^c ∩ B^c\)
7). 항등법칙 : \(A ∪ U = U , A ∪ ∅ = A => A ∩ U = A , A ∩ ∅ = ∅\)
어떤 집합명제를 증명하는 방법은 다음 세 가지 방법으로 증명 할 수 있습니다.
1). 밴 다이어그램을 이용한 방법 : 밴다이어그램을 그려서 증명하는 방법입니다.
2). 각 집합간의 부분집합 관계를 사용하여 증명하는 방법 :
각 집합의 원소가 모두 속하거나 존재하는지를 따져 부분집합 관계로 증명하는 방법입니다.
3). 각 집합을 포함한 결과 진리표를 구하여 증명하는 방법 : 주어진 집합을 입력으로 \(T, F\)를 테이블로 작성한 뒤
가능한 모든 경우의 수에 대해 진리표를 작성하여 증명하는 방법입니다.