집합은 대상을 순서 없이 모은 것이고, 함수는 한 집합의 원소를 다른 집합의 원소에 대응시키는 규칙이다. 이 두 개념은 이산수학의 거의 모든 분야에서 공통 언어로 사용된다.
집합과 원소
집합 에 원소 가 포함되면 , 포함되지 않으면 라고 쓴다. 집합은 원소를 직접 나열하거나 조건으로 표현할 수 있다.
집합의 원소 수를 cardinality라고 하며 로 나타낸다. 위 집합에서는 이다.
Subset과 Proper Subset
의 모든 원소가 에도 포함되면 라고 한다. 모든 집합에 대해
가 성립한다.
이고 이면 이며 이를 proper subset이라고 한다. 두 집합의 동일성은 다음과 같이 양방향 포함으로 확인할 수 있다.
기본 집합 연산
전체집합을 라고 하자.
이면 두 집합은 disjoint이다. 유한집합에서는 합집합의 원소 수를
로 계산한다.
집합 연산도 논리 연산과 비슷한 법칙을 만족한다.
이는 원소 가 각 집합에 속하는지를 명제로 바꾸면 논리의 De Morgan 법칙과 분배법칙에 대응한다.
Partition
집합 의 partition은 공집합이 아닌 부분집합들의 모음 으로 다음을 만족한다.
즉 모든 원소는 정확히 하나의 block에 속한다. 정수를 짝수와 홀수로 나누는 것은 의 partition이다.
Power Set
의 모든 부분집합을 모은 집합을 Power Set이라고 한다.
이면
이다. 유한집합 의 원소가 개이면 각 원소를 부분집합에 넣거나 넣지 않는 두 선택이 있으므로
이다.
Cartesian Product
두 집합의 Cartesian Product는 ordered pair들의 집합이다.
순서쌍이므로 일반적으로 이다. 유한집합에서는
이다.
Function
함수 는 Domain 의 각 원소에 Codomain 의 원소를 정확히 하나 대응시킨다. 에 대응하는 값을 라고 하고, 실제로 출력되는 값들의 집합을 Range라고 한다.
Codomain과 Range는 다를 수 있다. 함수의 성질을 판단할 때는 식뿐 아니라 Domain과 Codomain도 함께 보아야 한다.
Injection, Surjection, Bijection
함수 가 injection이면 서로 다른 입력이 같은 출력을 만들지 않는다.
유한집합에서는 injection이 존재하면 이다.
Surjection은 Codomain의 모든 원소가 실제로 출력되는 함수이다.
유한집합에서는 surjection이 존재하면 이다.
Injection이면서 Surjection인 함수를 Bijection이라고 한다. Bijection은 두 집합의 원소를 빠짐없이 일대일로 짝지으므로 집합의 크기가 같다는 의미를 갖는다.
Inverse와 Composition
Bijection 에는 inverse function 가 존재한다.
함수 와 의 composition은
이다. 실제로는 의 Range가 의 Domain 안에 들어가면 composition을 정의할 수 있다.
정리
집합은 포함 관계와 합집합·교집합 등의 연산으로 구조를 만들고, 함수는 집합 사이의 대응을 표현한다. Injection은 출력의 중복이 없고, Surjection은 Codomain에 빠진 값이 없으며, Bijection은 두 조건을 모두 만족한다. Bijection은 다음 글에서 무한집합의 크기를 비교하는 핵심 도구가 된다.
연습 문제
- 의 Power Set을 구한다.
- , 이 injection과 surjection 중 무엇인지 판단한다.
- 을 에서 로 가는 함수로 볼 때 inverse를 구한다.
풀이
1번
이며 원소 수는 이다.
2번
이면 이므로 이다. 따라서 injection이다. 그러나 홀수는 출력되지 않으므로 전체로의 surjection은 아니다.
3번
을 에 대해 풀면
이다. 따라서
이다.