집합의 연산

집합은 일반적인 연산인 사칙연산같은 연산을 사용하지는 않지만, 부분집합, 삽입, 결합 등의 방법으로 연산을 할 수 있습니다.

부분집합 (Subset)

그림과 같이 A집합과 B집합이 있습니다. 이러한 상황에서 A의 요소는 A의 요소이기도 하지만 동시에 B의 요소이기도 합니다. 그러니까, if x ∈ B, then x ∈ A 라는 말이죠. 이것은 B ⊆ A로 표현합니다. 또한, A ⊆ A and ∅ ⊆ A가 가능하다는 것에 유의합시다.

합집합/교집합 (Union/Intersection)

A와 B의 합집합은 A혹은 B에 있는 모든 요소를 포함하게 됩니다. 합집합은 A ∪ B 로 표현하고, {xlx is an element of A OR x is an element of B} 라고 작성합니다.

A와 B의 교집합은 A와 B 모두의 요소에 해당하는 요소만을 의미합니다. 교집합은 A ∩ B 로 표현하고, {xlx is an element of A AND x is an element of B} 라고 작성합니다.

여집합 (Complement)

A의 여집합은 A가 아닌 요소들을 선택하게 됩니다. 여집합은 Ac(지수형 꼴을 표현하기 어려움)로 표현하고, {xlx ∈/ A}라고 작성합니다.

그런데 이때, x ∈/ A인 요소들은 어디서 오는 걸까요? 보통은 전체 집합을 기준으로 생각합니다.

전체 집합 (Universal set) Ω로 표현하고, U로 쓰기도 합니다.

관심있는 모든 데이터를 포함하고 있는 집합입니다. 따라서 A ⊆ U, Ac ⊆ U, ∅ ⊆ U 이러한 식이 성립합니다.

차집합 (Set subtraction)

그림의 경우를 보면, A에서 A이면서 B인 요소를 제거했습니다. 또한 이것은 A이면서 B의 여집합의 교집합이라고 생각할 수 있습니다. 차집합은 A − B 혹은 A ∩ Bc로 표현할 수 있습니다. 차집합은 특이한 케이스가 있는데, 생각해보면 어렵지 않는 항목들입니다.

특이한 케이스

• Ω − A = Ac
• A − ∅ = A
• A − A = ∅
• A − B = A − (A ∩ B)

다중 집합 연산

앞에서는 단순히 한개 혹은 두 개의 집합에서의 집합 연산을 알아보았는데, 이번에는 한번에 여러 개의(혹은 무한개가 될 수도) 집합을 연산하는 방법을 알아봅시다.

만약 A1, A2, A3 … Ak라는 세트가 있다고 해봅시다. 이는 Ai라고 표현할 수 있습니다. (i = 1,2,3 … k라고 정의했을 때) 이 개념을 기반으로 다중 연산을 해봅시다.

다중 교집합 (Multiple intersection)

우리가 위에서 배웠듯이, x ∈ A1 ∩ A2 이면 x ∈ Ai, for all i ∈ {1,2} 와 같은 의미를 가진다는 것을 배웠습니다. 이를 응용해서, i가 n개로 늘어나면 어떨까요? x ∈ A1 ∩ A2 ∩ · · · An 이고, 또 한 이것은 x ∈ Ai, for all i ∈ {1, 2, · · · , n} 이겠죠. 이것을 축약하여 마치 고등학교에서 배운 시그마처럼 작성할 수 있습니다.

이렇게 수식을 정리할 수 있습니다. (무한대가 아니라 n까지 입니다. 수식에 오류가 있습니다.)

다중 합집합 (Multiple union)

다중 교집합과 비슷한 방식으로, x ∈ A1 ∪ A2 이면 there exists i ∈ {1, 2} such that x ∈ Ai 이죠. 똑같이 i가 n개로 늘어나면, x ∈ A1 ∪ A2 ∪ · · · An이고, 이것은 there exists i ∈ {1, 2, · · · , n} such that x ∈ Ai 와 같습니다.

이렇게 수식을 정리할 수 있습니다. (마찬가지로 무한대가 아니라 n까지 입니다.)

분할 (Partition)

집합의 요소는 집합이 될 수 있다. 고 한 것을 다시 떠올려보세요. 집합을 원소로 하여 구성된 집합을 집합족 (class of sets, family of sets)이라고 합니다. 한국어로는 잘 쓰이지 않습니다. 분할 또한 class of sets중 하나입니다. 예를들어 이러한 조건을 충족하는 A1, · · · , An n-집합이 있다고 생각해보죠.

그러면, {Aiㅣi = 1, · · · , n} (그러니까, Ai의 모든 집합을 의미합니다.) 는 Ω의 분할입니다. 분할은 고등학교 과정에 없으므로 꽤 생소한 단어일 텐데, 정의를 내리자면

집합의 분할은 집합의 원소들을 비공(non-empty, 非空) 부분집합들에게 나눠주어, 모든 원소가 각자 정확히 하나의 부분집합에 속하게끔 하는 것이다.

예를 들면, Ω = {1, 2, 3, 4, 5} 라고 합시다.

• A1 = {1,2}, A2 = {3,4,5} 면 {A1,A2}는 Ω의 분할입니다.
• Ai = {i} for i = 1, … 5 면, {A1,A2,A3,A4,A5}는 Ω의 분할입니다.
• 이때 Ω의 모든 분할을 찾아보세요.

A) 답을 나열하기에는 너무 많아서, 분할의 개수를 알아보도록 합시다. 이 상황은 원소의 개수가 5개인 집합을 분할하는 상황이죠. 그러니까 S(5,1)+S(5,2)+S(5,3)+S(5,4)+S(5,5)를 하겠다는 소리입니다.

S(5,1) 은 A1 = {1,2,3,4,5}로 1개죠.

S(5,2) 는 2개를 먼저 선택하면 나머지가 선택되므로 5C2 입니다. 10개죠.

S(5,3) 부터는 생각이 좀 필요한데요. 5를 3개로 나누는 방법에는 3, 1, 1 과 2, 2, 1 이 있겠죠? 그러니까 이 두 경우의 수를 구해 더해야 합니다. (5C3 * 2C1 * 1C1) / 2! + (5C3 * 3C2 * 1C1) / 2! = 25개죠.

S(5,4) 도 마찬가지에요. 5를 4개로 나누려면 2, 1, 1, 1로 나누어야 하죠? (5C2 * 3C1 * 2C1 * 1C1) / 3! 에 의해 10개 입니다. S(5,5) 는 Ai = {i} for i = 1, … 5 면, {A1,A2,A3,A4,A5}로 한개죠.

그러니까 총 47개 입니다.

집합 연산의 법칙

벤 다이어그램을 생각해보면서 이 법칙을 보면 이해가 쉽게 갈겁니다.
이러한 법칙은 차집합에도 적용되나요? : 아니요. Commutative Law만 보더라도, A-B는 B-A와 다르기 때문에 성립하지 않습니다.

일단은 이러한 연산들이 좀 익숙한가요? commutative law와 associative law가 사용되는 다른 연산도 있어요.
Addition과 Multiplication 입니다.

이렇게 되는 경우가 있다면 안되는 경우도 있겠죠.
상술했듯 Subtractions 가 그렇습니다.

추가적으로, 이 식 또한 성립합니다.

이러한 연산 법칙은 어디에 사용될까요? 병렬 컴퓨팅(Parallel computing)하는데 용이합니다.
예를 들어서 1부터 100까지의 합을 구한다고 합시다.
그리고 하나의 연산은 1 나노 초가 걸리는데, 그러면 1에서 100까지 더하는데는 99 나노 초가 걸립니다.
그럼 이제 우리가 10개의 컴퓨터를 가지고 있다고 해봅시다. 그러면 (1~10)+(11~20) … + (91~100)이 가능합니다. 그리고 이는 9 나노 초 밖에 걸리지 않습니다.

이번엔 관측치에 대한 예인데요, n개의 관측치가 있다고 해봅시다. xi를 각 시행의 관측치라고 하면, µ는 당연히

입니다.

만약 {A1, A2, · · · , Ak }를 {1, 2, · · · , n}의 분할이라고 생각하면,

가 가능하겠죠?
그러니까 이러한 작업을 k개의 프로세서로 나눌 수 있습니다.

데이터와 집합

데이터 하면 조정계산론과 데이터베이스에서 자주 다뤘는데요, 여기서의 데이터도 마찬가지입니다. 우리가 모은 데이터(관측 등으로)가 잘 정의되어있다면, 그것을 집합이라고 하지요.
예를 들어서 우리가 2019년 한국인들의 스마트폰 사용 시간을 얻었다고 해보죠. 여러 가지 방법으로요.
그러면 데이터의 정보는 (age, gender, usage time)이 있을 것입니다. 이것을 엑셀 파일로 정리하면

와 같습니다.

Age를 x, Gender를 y, Time을 z라고 둔다면 i번째 사람의 나이는 (i, x)라고 표현할 수 있겠죠? 편하게 xi라고 하기도 합니다. 아무튼 중요한 것은 이 데이터들은 전부 자연수라는 것입니다. 그러므로 xi ∈ N 이죠. 마찬가지로, yi ∈ {M, F}, zi ∈ R 겠죠? 그러면 우리는 이러한 데이터를

와 같이 표현할 수 있습니다. (왜 이렇게 표현되는지는, 곱집합에 대해 알게되면 더 확실해집니다.)

함수

함수(函數, 영어: function) 또는 사상(寫像, 영어: map 또는 mapping)은 첫 번째 집합의 임의의 한 원소를 두 번째 집합의 오직 한 원소에 대응시키는 이항관계다.

여러 분야에서 함수는 사용되지만, 집합론에 있어서는 집합 X와 Y가 있을 때 X의 요소 x와 Y의 요소 y의 관계로 해석합니다.
앞에 있는 집합 X는 정의역(domain)이라고 하고, 뒤에 있는 집합 Y는 치역(range, 정의역의 상)이라고 합니다.

f : X → Y 이라는 함수가 주어졌을때, 모든 x의 원소들은 Y의 원소에 연결되어야 합니다.

(함수의 정의역 X, 공역 Y, 치역 f(X). 이 상황에서는 공역과 치역이 다릅니다.)

질문 1 : 함수 f와 함수의 값 f(x)는 동일한가요 ? : 아니겠죠? (수업때 확인) 질문 2 : f : X → Y함수가 주어졌을 때 Y의 모든 요소들은 X의 요소와 연결되어 있어야 하나요? 역시 아닙니다. 위에 그림을 보면 이해할 수 있습니다.

+뒤에 퀴즈