5강. 함수와 관계

함수는 입력마다 출력을 하나씩 정하고, 관계는 두 대상이 '이어져 있는지'만 말합니다. '같다', '작거나 같다', '나누어떨어진다', '같은 반이다'가 모두 관계입니다. 이 강에서는 함수의 세 가지 성질(단사·전사·전단사)과, 관계 가운데 특히 중요한 동치관계(같은 것끼리 묶기)와 순서를 다룹니다.

함수는 각 입력에 출력을 하나씩 정하는 규칙이고, 관계는 두 원소가 “이어져 있는지”만 말하는 더 일반적인 개념입니다. 둘 다 4강의 곱집합의 부분집합으로 정의할 수 있습니다.

5.1 함수

정의 5.1 (함수). 집합 $A$ 의 각 원소에 집합 $B$ 의 원소를 정확히 하나씩 대응시키는 규칙 $f$ 를 $A$ 에서 $B$ 로의 함수(function)라 하고 $f : A \to B$ 로 씁니다. $A$ 를 정의역(domain), $B$ 를 공역(codomain), $f(A) = \{f(a) \mid a \in A\}$ 를 치역(range)이라 합니다.

“정확히 하나”에는 두 조건이 들어 있습니다: 모든 $a$ 에 출력이 있고(빠짐없음), 출력이 둘 이상이 아닙니다(하나뿐). 치역은 공역의 부분집합이지만 같을 필요는 없습니다.

정리 5.2. $|A| = m$ , $|B| = n$ 이면 $A$ 에서 $B$ 로의 함수는 $n^m$ 개입니다.

증명. $A$ 의 원소마다 출력을 $n$ 가지 중 하나로 독립적으로 고르므로 $n \cdot n \cdots n = n^m$ 입니다. □

5.2 단사, 전사, 전단사

정의 5.3. 함수 $f : A \to B$ 가

단사(일대일): $f(a_1) = f(a_2)$ 이면 $a_1 = a_2$ .
전사(위로): 모든 $b \in B$ 에 대해 $f(a) = b$ 인 $a$ 가 있다. 곧 치역 = 공역.
전단사(bijective): 단사이면서 전사.

함수	단사	전사
$f : \mathbb{Z} \to \mathbb{Z}$ , $f(n) = 2n$	예	아니오 (홀수가 안 나옴)
$f : \mathbb{Z} \to \mathbb{Z}$ , $f(n) = n + 3$	예	예
$f : \mathbb{R} \to \mathbb{R}$ , $f(x) = x^2$	아니오 ( $f(1) = f(-1)$ )	아니오 (음수가 안 나옴)
$f : \mathbb{R} \to [0, \infty)$ , $f(x) = x^2$	아니오	예

마지막 두 줄처럼 같은 식이라도 공역을 바꾸면 성질이 바뀝니다.

정리 5.4. 유한집합 $A$ , $B$ 에 대해 단사 $f : A \to B$ 가 있으면 $|A| \le |B|$ , 전사가 있으면 $|A| \ge |B|$ , 전단사가 있으면 $|A| = |B|$ 입니다.

전단사는 두 집합의 원소를 남김없이 짝짓는 것이므로 “크기가 같다”의 정의로 씁니다.

5.3 합성과 역함수

정의 5.5. $f : A \to B$ , $g : B \to C$ 의 합성(composition) $g \circ f : A \to C$ 는 $(g \circ f)(a) = g(f(a))$ 입니다.

정리 5.6. $f : A \to B$ 가 전단사이면 $f^{-1} \circ f = \mathrm{id}_A$ , $f \circ f^{-1} = \mathrm{id}_B$ 인 역함수(inverse function) $f^{-1} : B \to A$ 가 하나 있습니다. 거꾸로 역함수가 있으면 $f$ 는 전단사입니다.

증명 개요. 전사이므로 각 $b$ 에 $f(a) = b$ 인 $a$ 가 있고, 단사이므로 그런 $a$ 는 하나뿐입니다. 그 $a$ 를 $f^{-1}(b)$ 로 정합니다. □

5.4 관계

정의 5.7 (관계). 집합 $A$ 위의 관계(relation) $R$ 은 $A \times A$ 의 부분집합입니다. $(a, b) \in R$ 이면 $a\, R\, b$ 로 씁니다.

정의 5.8 (관계의 성질). $A$ 위의 관계 $R$ 이

반사적(reflexive): 모든 $a$ 에 대해 $a\, R\, a$ .
대칭적(symmetric): $a\, R\, b$ 이면 $b\, R\, a$ .
반대칭적(antisymmetric): $a\, R\, b$ 이고 $b\, R\, a$ 이면 $a = b$ .
추이적(transitive): $a\, R\, b$ 이고 $b\, R\, c$ 이면 $a\, R\, c$ .

관계 (정수 위)	반사	대칭	반대칭	추이
$=$	예	예	예	예
$\le$	예	아니오	예	예
$<$	아니오	아니오	예	예
$a \mid b$ (양의 정수 위)	예	아니오	예	예
$a - b$ 가 짝수	예	예	아니오	예

5.5 동치관계와 분할

정의 5.9 (동치관계). 반사적·대칭적·추이적인 관계를 동치관계(equivalence relation)라 합니다. $a$ 와 동치인 원소의 집합 $[a] = \{x \mid x\, R\, a\}$ 를 $a$ 의 동치류(equivalence class)라 합니다.

예제 5.10. 정수 위에서 “ $a - b$ 가 3의 배수”는 동치관계이고, 동치류는 3으로 나눈 나머지에 따라 $[0], [1], [2]$ 의 셋입니다. 이것이 10강에서 다룰 합동입니다.

정리 5.11. 동치관계의 동치류들은 서로소이고 합하면 전체가 됩니다. 곧 집합의 분할(partition)을 이룹니다. 거꾸로 분할이 주어지면 “같은 조각에 있다”는 동치관계가 됩니다.

증명 (서로소). $[a] \cap [b]$ 에 $c$ 가 있으면 $c\, R\, a$ , $c\, R\, b$ 입니다. 대칭과 추이로 $a\, R\, b$ 이고, 그러면 $x\, R\, a \iff x\, R\, b$ 이므로 $[a] = [b]$ 입니다. 그러므로 두 동치류는 같거나 서로소입니다. 반사성으로 $a \in [a]$ 이므로 모든 원소가 어떤 동치류에 들어갑니다. □

5.6 부분순서

정의 5.12 (부분순서). 반사적·반대칭적·추이적인 관계를 부분순서(partial order)라 합니다. 임의의 두 원소가 비교 가능하면( $a\, R\, b$ 또는 $b\, R\, a$ ) 전순서(total order)입니다.

$\le$ 는 전순서이고, 양의 정수 위의 $\mid$ 와 집합의 $\subseteq$ 는 전순서가 아닌 부분순서입니다. 예를 들어 $2 \nmid 3$ 이고 $3 \nmid 2$ 입니다.

쓰이는 곳. 해시 함수(단사에 가까워야 함), 데이터베이스의 관계, 클러스터링(동치관계로 묶기), 작업 순서(부분순서와 위상 정렬)가 이 강의 개념입니다.

5.7 이 장의 요약

함수의 수 $n^m$ . 전단사 ⟺ 역함수가 있음.
동치관계 = 반사·대칭·추이, 그 동치류가 분할을 이룹니다.
부분순서 = 반사·반대칭·추이.

문제

5.1 [계산] · 확인 문제

$|A| = 3$ , $|B| = 4$ 일 때 함수의 개수를 씁니다.

종류	개수
$A \to B$ 함수	[?]
$A \to B$ 단사	[?]
$B \to A$ 함수	[?]
$A \to A$ 전단사	[?]

힌트 1

단사는 첫 원소부터 아직 쓰지 않은 출력만 고릅니다.

정답

풀이

$4^3 = 64$ , 단사는 $4 \cdot 3 \cdot 2 = 24$ , $B \to A$ 는 $3^4 = 81$ , $A \to A$ 전단사는 $3! = 6$ 입니다.

5.2 [개념] · 확인 문제

전단사인 것은?

$f : \mathbb{Z} \to \mathbb{Z}$ , $f(n) = n^2$
$f : \mathbb{R} \to \mathbb{R}$ , $f(x) = 3x - 7$
$f : \mathbb{N} \to \mathbb{N}$ , $f(n) = n + 1$
$f : \mathbb{R} \to \mathbb{R}$ , $f(x) = e^x$

정답

풀이

2번의 역함수는 $f^{-1}(y) = (y + 7)/3$ 입니다. 1번은 단사가 아니고, 3번은 $0$ 이 치역에 없고, 4번은 음수가 치역에 없어 전사가 아닙니다.

5.3 [계산] · 확인 문제

집합 $\{1, 2, 3\}$ 위의 관계 $R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$ 의 각 성질을 “예” 또는 “아니오”로 씁니다.

성질	답
반사적	[?]
대칭적	[?]
반대칭적	[?]
추이적	[?]

정답

예
예
아니오
예

풀이

$(1,1), (2,2), (3,3)$ 이 모두 있으므로 반사적입니다. $(1,2)$ 와 $(2,1)$ 이 함께 있으므로 대칭적이고, $1 \ne 2$ 이므로 반대칭적이 아닙니다. 추이성은 $(1,2), (2,1) \Rightarrow (1,1)$ 같은 모든 경우가 $R$ 에 있으므로 성립합니다. 이 관계는 분할 $\{\{1, 2\}, \{3\}\}$ 에 대응하는 동치관계입니다.

5.4 [계산]

집합 $\{1, 2, 3\}$ 위의 동치관계는 모두 몇 개일까요?

힌트 1

정리 5.11에 따라 동치관계와 분할은 일대일로 대응합니다.

정답

풀이

$\{1,2,3\}$ 의 분할: 한 조각 1개, 두 조각 3개( $\{1\}\{2,3\}$ 등), 세 조각 1개로 모두 5개입니다. 동치관계도 5개입니다.

5.5 [증명]

$f : A \to B$ , $g : B \to C$ 가 모두 단사이면 $g \circ f$ 도 단사임을 보입니다.

풀이

$(g \circ f)(a_1) = (g \circ f)(a_2)$ 라 합시다. 곧 $g(f(a_1)) = g(f(a_2))$ 입니다. $g$ 가 단사이므로 $f(a_1) = f(a_2)$ 이고, $f$ 가 단사이므로 $a_1 = a_2$ 입니다.