함수를 두 질문으로 나눈다. 출력이 서로 겹치지 않는가(단사), 도착 쪽을 빠짐없이 덮는가(전사). 둘 다이면 전단사로, 두 집합의 원소를 하나씩 짝지을 수 있어 크기가 같다. 끝없이 큰 집합의 크기도 이 짝짓기로 비교한다. 해시 함수처럼 큰 집합에서 작은 집합으로 가는 함수는 단사일 수 없어서 충돌이 반드시 생긴다.
예시로 보기
강의실 좌석 배정은 함수 “학생 → 좌석”이다.
| 상황 | 겹침 | 빈자리 | 이름 |
|---|---|---|---|
| 학생 30명, 좌석 40개, 한 좌석에 한 명 | 없음 | 있음 | 단사, 전사 아님 |
| 학생 40명, 좌석 30개, 모든 좌석이 참 | 있음 | 없음 | 전사, 단사 아님 |
| 학생 30명, 좌석 30개, 한 좌석에 한 명씩 꽉 참 | 없음 | 없음 | 전단사 |
마지막 경우에는 학생 수를 세지 않고도 좌석 수와 같다는 것을 안다. 짝이 딱 맞기 때문이다. 이 생각이 “크기가 같다”의 정의가 된다.
flowchart LR
subgraph U1["단사, 전사 아님"]
a1["학생 1"] --> x1["좌석 1"]
a2["학생 2"] --> x2["좌석 2"]
x3["좌석 3: 빈자리"]
end
subgraph U2["전사, 단사 아님"]
b1["학생 1"] --> y1["좌석 1"]
b2["학생 2"] --> y1
b3["학생 3"] --> y2["좌석 2"]
end
subgraph U3["전단사"]
c1["학생 1"] --> z1["좌석 1"]
c2["학생 2"] --> z2["좌석 2"]
end
첫 묶음에는 화살표가 닿지 않는 좌석이 있다. 둘째 묶음에서는 화살표 둘이 한 좌석에 모인다. 셋째 묶음만 학생과 좌석이 하나씩 짝지어진다1.
정의
함수 \(f: A \to B\)에 대해2
- 단사(injective, 일대일): \(f(a_1) = f(a_2) \Rightarrow a_1 = a_2\). 서로 다른 입력은 서로 다른 출력으로 간다.
- 전사(surjective, 위로의): \(\forall b \in B\ \exists a \in A\ (f(a) = b)\)(\(\forall\)은 “모든”). 치역이 공역 전체다.
- 전단사(bijective): 단사이면서 전사. 이때 역함수 \(f^{-1}: B \to A\)가 있고, 거꾸로 역함수가 있으면 전단사다.
집합의 크기. \(A\)에서 \(B\)로 가는 전단사가 있으면 \(\vert A\vert = \vert B\vert\)라 한다. 단사가 있으면 \(\vert A\vert \le \vert B\vert\)라 한다. 유한 집합에서는 원소 수와 같은 뜻이고, 무한 집합에서는 이것이 크기의 정의다.
\(A\), \(B\)가 유한할 때
- 단사 \(A \to B\)가 있으면 \(\vert A\vert \le \vert B\vert\)이다.
- 전사 \(A \to B\)가 있으면 \(\vert A\vert \ge \vert B\vert\)이다.
- \(A\)에서 \(B\)로 가는 함수는 \(\vert B\vert ^{\vert A\vert }\)개다.
증명
- 단사이면 치역 \(f(A)\)의 원소가 \(A\)의 원소와 하나씩 짝지어지므로 \(\vert f(A)\vert = \vert A\vert\)이고, \(f(A) \subseteq B\)라 \(\vert A\vert \le \vert B\vert\)다.
- 전사이면 \(B\)의 원소마다 그리로 가는 \(A\)의 원소를 하나씩 고를 수 있다. 고른 원소들은 서로 다르므로(출력이 다르니) \(\vert B\vert \le \vert A\vert\)다.
- \(A\)의 원소마다 출력을 \(\vert B\vert\)가지 중 하나씩 독립적으로 고른다. \(\vert A\vert\)번 고르므로 \(\vert B\vert \cdot \vert B\vert \cdots \vert B\vert = \vert B\vert ^{\vert A\vert }\)가지다(이 셈법은 셈의 기본 법칙에서 곱의 법칙으로 정식화한다). ∎
예제
\(\vert \mathcal{P}(A)\vert = 2^n\)을 전단사로 보이기. \(A = \{0, 1, \dots, n - 1\}\)의 부분집합 \(S\)에, \(i \in S\)이면 \(i\)번째 비트가 1인 \(n\)비트 문자열을 대응시킨다.
- 단사: 두 부분집합이 다르면 어떤 원소 \(i\)가 한쪽에만 있어 \(i\)번째 비트가 다르다.
- 전사: 아무 \(n\)비트 문자열이든 1인 자리들을 모으면 그 문자열로 가는 부분집합이 된다.
- 결론: 전단사이므로 부분집합의 수는 \(n\)비트 문자열의 수 \(2^n\)과 같다.
활용
- 해시 충돌. 문자열 전체에서 64비트 해시값으로 가는 함수는 입력이 훨씬 많아 단사일 수 없다(정리 1의 대우). 충돌은 설계 실수가 아니라 필연이다. 좋은 해시는 충돌을 없애는 것이 아니라 고르게 흩는다.
- 암호와 압축. 복호화할 수 있으려면 암호화는 단사여야 한다. 무손실 압축은 어떤 파일은 오히려 커질 수밖에 없다. 짧은 파일의 수가 긴 파일의 수보다 적어서, 모든 파일을 줄이는 단사 함수는 없기 때문이다3.
- 데이터베이스 키. 기본 키는 행에서 키값으로 가는 단사 함수다. 같은 키를 가진 두 행을 허용하지 않는다.
- 알고리즘에서: 예제의 짝짓기를 코드로 옮긴 것이 비트마스크이고, 0부터 \(2^n - 1\)까지의 수 하나가 부분집합 하나다(비트 연산과 비트마스크). 유한 집합에서는 출력 종류 수가 입력 수와 같으면 단사라서, 후보키는 고른 열 값의 종류 수를 행 수와 비교해 유일성을 검사한다. 충돌이 나도 평균 \(O(1)\)을 지키는 방법(다른 빈칸 찾기, 칸 수 늘리기)은 딕셔너리와 집합에 있다.
연결
- 선수: 집합, 역함수(일대일 함수의 뜻)
- 이어지는 개념: 가산 집합과 대각선 논법(무한 집합의 크기), 셈의 기본 법칙과 비둘기집 원리
과목별 관점
데이터베이스 설계 (2-2학기). 표를 설계할 때 쓰는 말 가운데 여럿이 함수의 성질을 다른 이름으로 부른 것이다.
- 키는 단사 함수다. 표의 줄(튜플) \(t\)를 그 줄의 키 값 \(t[K]\)로 보내는 함수를 생각한다. \(K\)가 키라는 것은 서로 다른 두 줄 \(t_1\), \(t_2\)에 대해 늘 \(t_1[K] \ne t_2[K]\)라는 뜻이다. 서로 다른 입력이 서로 다른 출력으로 가므로 단사다. 학생 표에서 학생을 사회보장번호로 보내는 함수는 단사이고, 나이로 보내는 함수는 두 학생이 19로 가서 단사가 아니다. 나이는 키가 아니다: 슈퍼키·후보 키·기본 키
- 일대다 연결은 함수다. “직원은 부서 하나에만 속한다”(부서 1 : 직원 N)는 직원마다 부서가 많아야 하나 정해진다는 말이다. 직원에서 부서로 가는 함수다. 표에서는 직원 줄의 부서 번호 칸이 이 함수의 값을 적는 자리다. 5번 부서로 직원 넷이 가므로 단사는 아니다: 카디널리티 비율
- 참여 제약은 “빠짐없이”를 묻는다. 모든 직원이 부서에 속해야 한다(전체 참여)면 함수가 직원 전체에서 정해진다. 일부만 참여해도 되면(부분 참여) 값이 없는 입력이 있다. 사장은 상사가 없어서 “직원 → 상사”에는 값이 없는 직원이 있다. 자세한 것은 참여 제약에 있다.
| 표를 설계할 때의 말 | 함수의 말 |
|---|---|
| 키 | 줄에서 키 값으로 가는 함수가 단사 |
| 1:N 연결 (N쪽은 상대가 많아야 하나) | N쪽에서 1쪽으로 가는 함수 |
| N쪽의 전체 참여 | 그 함수가 N쪽 전체에서 정해진다 |
| 1:1 연결 | 그 함수가 단사 |
| 1쪽의 전체 참여 | 그 함수가 전사 |
| M:N 연결 | 함수가 아니다. 한 입력에 출력이 여럿이다 |
표의 아래 네 줄은 연결의 비율과 참여 제약의 정의를 함수의 말로 옮긴 것이다. 함수인 연결은 칸 하나로 적을 수 있고, 함수가 아닌 연결은 짝마다 줄 하나를 쓰는 표가 따로 필요하다.
확인 문제
C1 정수에서 정수로 가는 함수 (가) f(x) = 2x (나) g(x) = ⌊x/2⌋ (다) h(x) = x + 1 (라) k(x) = x²을 단사·전사로 분류하라.
답: (가) 단사, 전사 아님(홀수가 안 나옴). (나) 전사, 단사 아님(\(g(0) = g(1) = 0\)). (다) 전단사(역함수 \(x - 1\)). (라) 둘 다 아님(\(k(1) = k(-1)\), 음수와 2가 안 나옴).
C2 유한 집합 A에서 B로 가는 단사 함수가 있으면 왜 |A| ≤ |B|인가? 이 사실에서 해시 충돌에 대해 무엇을 알 수 있나?
답: 단사이면 출력이 모두 달라 치역의 크기가 \(\vert A\vert\)이고, 치역은 \(B\) 안에 있으므로 \(\vert A\vert \le \vert B\vert\)다. 대우를 취하면, \(\vert A\vert > \vert B\vert\)이면 어떤 함수도 단사가 아니다. 입력이 해시값보다 많으면 충돌이 반드시 있다.
C3 원소 3개인 집합에서 원소 2개인 집합으로 가는 함수는 몇 개이고, 그중 전사는 몇 개인가?
답: \(2^3 = 8\)개. 전사가 아닌 것은 모든 원소를 한 값으로 보내는 2개이므로 전사는 6개다.
C4 어느 회사에 직원 8명, 부서 3개, 프로젝트 6개가 있다. (가) 직원 → 일하는 부서: 직원마다 부서가 하나이고 세 부서에 1명, 3명, 4명이 있다. (나) 부서 → 관리자: 부서마다 관리자가 한 명이고 세 관리자는 서로 다른 직원이다. (다) 직원 → 일하는 프로젝트: 한 직원이 프로젝트 넷에서 일하기도 한다. 셋 가운데 함수인 것은? 그중 단사인 것, 전사인 것은?
답: (가)는 함수다. 단사는 아니고(한 부서로 여럿이 간다) 전사다(세 부서 모두 직원이 있다). (나)는 함수이고 단사다(관리자가 겹치지 않는다). 전사는 아니다(직원 8명 가운데 3명에게만 닿는다). (다)는 함수가 아니다(한 입력에 출력이 넷이다).
이유: 데이터베이스의 말로는 (가)가 1:N, (나)가 1:1, (다)가 M:N 연결이다. (가)와 (나)는 칸 하나로 적고 (다)는 표를 따로 만든다.
-
‘예시로 보기’ 표의 세 상황을 학생과 좌석 2~3개로 줄여 그렸다. ↩
-
Lehman·Leighton·Meyer, Mathematics for Computer Science, 4장 “Mathematical Data Types”(함수, 이항 관계, 유한 집합의 크기). Rosen, Discrete Mathematics and Its Applications 7판, 2장(함수, 집합의 크기). ↩
-
무손실 압축의 한계는 “길이 \(n\) 비트 파일은 \(2^n\)개인데 길이 \(n\) 미만 파일은 \(2^n - 1\)개”라는 셈에서 나온다. 비둘기집 원리의 대표 예다. ↩