집합과 함수
집합 연산, 함수, 단사·전사·역함수
개요 — 동기·문제의식
집합은 이산수학 전체가 쓰는 공용어다. 관계, 그래프, 순열, 확률공간 — 이후의 모든 장이 다루는 대상은 결국 "어떤 집합 위의 구조"로 정의되고, 그 정의를 다루는 기본기가 이 장의 내용이다. 증명 기법에서 익힌 직접증명·귀납법은 여기서 처음으로 본격적인 적용 대상을 만난다: 두 집합이 같음을 보이는 표준 전략(이중 포함), 멱집합의 크기를 세는 귀납 논증이 그것이다.
함수는 두 집합을 비교하는 장치다. 단사·전사·전단사라는 세 가지 성질은 "정보를 잃지 않는가", "목표를 모두 덮는가", "완벽하게 짝지어지는가"를 각각 묻고, 이 물음들이 이후 장의 핵심 도구가 된다 — 집합의 크기에서는 전단사의 존재 여부가 곧 "크기가 같다"의 정의이고, 셈의 기본 원리 이후의 조합론에서는 "두 집합 사이의 전단사를 만들면 세는 문제가 끝난다"는 전단사 논법이 반복적으로 등장한다. 이 장은 그 도구들을 정확한 정의와 증명으로 준비하는 단계다.
직관
집합은 순서도 중복도 없는 자루다. $\{1,2,3\}$과 $\{3,1,2,2\}$는 같은 집합이다 — 무엇이 들어 있는가만이 집합의 정체이며, 이것이 외연성 원리다. 합집합·교집합·차집합은 두 자루를 벤 다이어그램 위에서 합치고 겹치고 깎아내는 조작이고, 드모르간 법칙은 "합치고 나서 뒤집기"와 "각각 뒤집고 나서 겹치기"가 같다는, 명제논리의 $\lnot(p\lor q)\equiv\lnot p\land\lnot q$를 그대로 집합 언어로 옮긴 대칭성이다.
함수 $f:A\to B$는 $A$의 각 원소에서 $B$의 원소로 화살표를 정확히 하나씩 쏘는 기계다. 단사는 "두 화살표가 같은 곳에 꽂히지 않음"(충돌 없음), 전사는 "$B$의 모든 점에 적어도 하나의 화살표가 꽂힘"(빠짐 없음), 전단사는 둘 다 — 즉 $A$와 $B$의 완벽한 일대일 짝짓기다. 역함수는 모든 화살표의 방향을 거꾸로 뒤집는 조작인데, 뒤집은 결과가 다시 함수가 되려면 각 점에 꽂힌 화살표가 정확히 하나여야 하므로 전단사가 정확히 필요조건이자 충분조건이 된다. 이 그림 하나가 이 장의 마지막 정리다.
정의
집합과 부분집합
정의. 집합(set)은 서로 구별되는 대상들의 모임이며, 대상 $x$가 집합 $A$에 속하면 $x\in A$로 쓴다. 두 집합이 같음은 원소가 같음이다(외연성): $A=B\iff\forall x\,(x\in A\leftrightarrow x\in B)$. $A$가 $B$의 부분집합 $A\subseteq B\iff\forall x\,(x\in A\to x\in B)$이고, $A\subseteq B$이면서 $A\ne B$이면 진부분집합 $A\subsetneq B$이다. 원소가 하나도 없는 집합이 공집합 $\varnothing$이며, 임의의 집합 $A$에 대해 $\varnothing\subseteq A$이다(전제가 항상 거짓인 함의는 참 — 공허한 참).
집합 연산
정의. 전체집합 $U$ 안에서 $A,B\subseteq U$에 대해:
| 연산 | 표기 | 정의 |
|---|---|---|
| 합집합 | $A\cup B$ | $\{x \mid x\in A \lor x\in B\}$ |
| 교집합 | $A\cap B$ | $\{x \mid x\in A \land x\in B\}$ |
| 차집합 | $A\setminus B$ | $\{x \mid x\in A \land x\notin B\}$ |
| 여집합 | $A^c$ | $U\setminus A$ |
| 대칭차 | $A\triangle B$ | $(A\setminus B)\cup(B\setminus A)$ |
$A\cap B=\varnothing$이면 $A$와 $B$는 서로소(disjoint)다.
멱집합과 곱집합
정의. $A$의 멱집합(power set)은 $A$의 모든 부분집합의 집합 $\mathcal{P}(A)=\{S\mid S\subseteq A\}$이다. 순서쌍 $(a,b)$는 $(a,b)=(c,d)\iff a=c\land b=d$를 만족하는 대상이며, 곱집합(Cartesian product)은 $A\times B=\{(a,b)\mid a\in A,\ b\in B\}$이다. 일반화하여 $A_1\times\cdots\times A_n$은 $n$-순서쌍들의 집합이다.
함수
정의. 함수 $f:A\to B$는 $A$의 각 원소 $a$에 $B$의 원소를 정확히 하나 대응시키는 규칙이다(형식적으로는 $\Gamma\subseteq A\times B$ 중 각 $a\in A$에 대해 $(a,b)\in\Gamma$인 $b$가 유일하게 존재하는 부분집합 — 함수는 특별한 관계다, 관계와 동치관계). $A$를 정의역, $B$를 공역, $f(A)=\{f(a)\mid a\in A\}\subseteq B$를 치역(상)이라 한다. 두 함수가 같음은 정의역·공역이 같고 모든 입력에서 값이 같음이다.
단사·전사·전단사
정의. $f:A\to B$에 대해(술어와 한정기호의 한정기호로 정확히 쓰면):
- 단사(injective, 일대일) $\iff\forall a_1,a_2\in A\,\big(f(a_1)=f(a_2)\to a_1=a_2\big)$.
- 전사(surjective, onto) $\iff\forall b\in B\ \exists a\in A\ f(a)=b$, 즉 $f(A)=B$.
- 전단사(bijective) $\iff$ 단사이면서 전사.
합성·항등함수·역함수
정의. $f:A\to B$, $g:B\to C$의 합성은 $(g\circ f)(a)=g(f(a))$로 정의되는 $g\circ f:A\to C$이다. 항등함수 $\mathrm{id}_A:A\to A$는 $\mathrm{id}_A(a)=a$. $g:B\to A$가 $g\circ f=\mathrm{id}_A$와 $f\circ g=\mathrm{id}_B$를 모두 만족하면 $g$를 $f$의 역함수라 하고 $f^{-1}$로 쓴다.
상과 역상
정의. $f:A\to B$, $S\subseteq A$, $T\subseteq B$에 대해 $S$의 상(image)은 $f(S)=\{f(x)\mid x\in S\}$, $T$의 역상(preimage)은 $f^{-1}(T)=\{x\in A\mid f(x)\in T\}$이다. 역상 $f^{-1}(T)$는 역함수의 존재와 무관하게 모든 함수에 대해 정의된다 — $f^{-1}$이라는 기호가 겹치지만 다른 개념이다.
주요 정리
정리 1 (드모르간 법칙, 집합판). $A,B\subseteq U$에 대해 $(A\cup B)^c=A^c\cap B^c$이고 $(A\cap B)^c=A^c\cup B^c$이다.
증명 보기
증명. 첫 식을 원소 논법으로 보인다. 임의의 $x\in U$에 대해 $x\in(A\cup B)^c\iff\lnot(x\in A\lor x\in B)\iff(x\notin A)\land(x\notin B)$ (명제논리의 드모르간 동치) $\iff x\in A^c\land x\in B^c\iff x\in A^c\cap B^c$. 모든 원소에 대한 동치이므로 외연성에 의해 두 집합이 같다. 둘째 식은 첫 식에서 $A,B$ 대신 $A^c,B^c$를 대입하고 양변의 여집합을 취하면 $(A^c\cup B^c)^c=A\cap B$에서 따라 나온다. $\blacksquare$
정리 2 (멱집합의 크기). $\lvert A\rvert=n$이면 $\lvert\mathcal{P}(A)\rvert=2^n$이다.
증명 보기
증명. $n$에 대한 귀납법(증명 기법). $n=0$이면 $A=\varnothing$이고 $\mathcal{P}(\varnothing)=\{\varnothing\}$이므로 $\lvert\mathcal{P}(A)\rvert=1=2^0$. $n$짜리 집합에서 성립한다고 가정하고 $\lvert A\rvert=n+1$이라 하자. 원소 $a\in A$를 하나 고정하고 $A'=A\setminus\{a\}$로 두면 $\lvert A'\rvert=n$. $A$의 부분집합은 $a$를 포함하지 않는 것($A'$의 부분집합과 정확히 일치, 귀납 가정으로 $2^n$개)과 $a$를 포함하는 것($S\mapsto S\cup\{a\}$가 $\mathcal{P}(A')$에서 후자로 가는 전단사이므로 역시 $2^n$개)으로 서로소 분할된다. 따라서 $\lvert\mathcal{P}(A)\rvert=2^n+2^n=2^{n+1}$. $\blacksquare$
정리 3 (합성은 단사·전사를 보존). $f:A\to B$, $g:B\to C$에 대해 (i) $f,g$가 단사이면 $g\circ f$ 단사, (ii) $f,g$가 전사이면 $g\circ f$ 전사. 따라서 전단사의 합성은 전단사다.
증명 보기
증명. (i) $(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$. (ii) $c\in C$를 잡자. $g$ 전사이므로 $g(b)=c$인 $b\in B$가 존재하고, $f$ 전사이므로 $f(a)=b$인 $a\in A$가 존재한다. 그러면 $(g\circ f)(a)=g(b)=c$. $\blacksquare$
정리 4 (합성에서 얻는 부분 정보). $f:A\to B$, $g:B\to C$에 대해 (i) $g\circ f$가 단사이면 $f$ 단사, (ii) $g\circ f$가 전사이면 $g$ 전사. (역방향 주장 — $g$가 단사라거나 $f$가 전사라는 결론 — 은 일반적으로 거짓이다.)
증명 보기
증명. (i) $f(a_1)=f(a_2)$이면 $g$를 적용해 $(g\circ f)(a_1)=(g\circ f)(a_2)$이고, $g\circ f$ 단사이므로 $a_1=a_2$. (ii) $c\in C$에 대해 $g\circ f$ 전사이므로 $(g\circ f)(a)=c$인 $a$가 존재하며, $b=f(a)$로 두면 $g(b)=c$. 반례는 예제 5에서 구성한다. $\blacksquare$
정리 5 (역함수 존재 $\iff$ 전단사). $f:A\to B$가 역함수를 가질 필요충분조건은 $f$가 전단사인 것이며, 역함수는 존재하면 유일하다.
증명 보기
증명. ($\Leftarrow$) $f$가 전단사라 하자. 각 $b\in B$에 대해 전사성으로 $f(a)=b$인 $a$가 존재하고 단사성으로 그런 $a$는 유일하다. $g(b)$를 그 유일한 $a$로 정의하면 $g:B\to A$는 함수이고, 구성에 의해 $f(g(b))=b$ (모든 $b$)와 $g(f(a))=a$ (모든 $a$; $f(a)$의 유일한 원상이 $a$ 자신이므로)가 성립한다. ($\Rightarrow$) $g\circ f=\mathrm{id}_A$, $f\circ g=\mathrm{id}_B$인 $g$가 있다고 하자. $\mathrm{id}_A$가 단사이므로 정리 4(i)에 의해 $f$ 단사이고, $\mathrm{id}_B$가 전사이므로 정리 4(ii)에 의해 $f$ 전사다. 유일성: $g,g'$이 모두 역함수이면 $g=g\circ\mathrm{id}_B=g\circ(f\circ g')=(g\circ f)\circ g'=\mathrm{id}_A\circ g'=g'$ (합성의 결합법칙). $\blacksquare$
정리 6 (상·역상과 집합 연산의 호환). $f:A\to B$, $S,S'\subseteq A$, $T,T'\subseteq B$에 대해: (i) $f^{-1}(T\cup T')=f^{-1}(T)\cup f^{-1}(T')$, $f^{-1}(T\cap T')=f^{-1}(T)\cap f^{-1}(T')$, $f^{-1}(B\setminus T)=A\setminus f^{-1}(T)$ — 역상은 모든 집합 연산과 완전히 호환된다. (ii) $f(S\cup S')=f(S)\cup f(S')$이지만 교집합은 $f(S\cap S')\subseteq f(S)\cap f(S')$ 한쪽 포함만 성립하며, 모든 $S,S'$에 대해 등호가 성립할 필요충분조건은 $f$가 단사인 것이다.
증명 보기
증명 스케치. (i) 전부 원소 논법 한 줄이다: $x\in f^{-1}(T\cap T')\iff f(x)\in T\cap T'\iff f(x)\in T\land f(x)\in T'\iff x\in f^{-1}(T)\cap f^{-1}(T')$; 합집합·여집합도 각각 $\lor$·$\lnot$으로 같은 방식. (ii) 포함: $y\in f(S\cap S')$이면 $y=f(x)$, $x\in S\cap S'$인 $x$가 있어 $y\in f(S)$이고 $y\in f(S')$. $f$ 단사일 때 역포함: $y\in f(S)\cap f(S')$이면 $y=f(x_1)=f(x_2)$, $x_1\in S$, $x_2\in S'$인데 단사성으로 $x_1=x_2\in S\cap S'$이므로 $y\in f(S\cap S')$. $f$가 단사가 아니면 $f(a)=f(a')$, $a\ne a'$인 쌍을 잡아 $S=\{a\}$, $S'=\{a'\}$로 두면 $f(S\cap S')=f(\varnothing)=\varnothing$이지만 $f(S)\cap f(S')=\{f(a)\}\ne\varnothing$ — 등호가 깨진다. $\blacksquare$
예제
예제 1 (집합 연산 계산). $U=\{1,\dots,8\}$, $A=\{1,2,3,4\}$, $B=\{3,4,5,6\}$이면 $A\cup B=\{1,\dots,6\}$, $A\cap B=\{3,4\}$, $A\setminus B=\{1,2\}$, $B\setminus A=\{5,6\}$, $A\triangle B=\{1,2,5,6\}$, $A^c=\{5,6,7,8\}$. 드모르간 검증: $(A\cup B)^c=\{7,8\}$이고 $A^c\cap B^c=\{5,6,7,8\}\cap\{1,2,7,8\}=\{7,8\}$로 일치한다.
예제 2 (멱집합). $\mathcal{P}(\{a,b,c\})=\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$ — 정리 2대로 $2^3=8$개다. $\varnothing\in\mathcal{P}(A)$이고 $A\in\mathcal{P}(A)$임에 주의: 멱집합의 원소는 "부분집합"이므로 $\{a\}\in\mathcal{P}(A)$이지만 $a\notin\mathcal{P}(A)$이다.
예제 3 (곱집합). $A=\{1,2\}$, $B=\{x,y,z\}$이면 $A\times B=\{(1,x),(1,y),(1,z),(2,x),(2,y),(2,z)\}$로 $\lvert A\times B\rvert=2\cdot3=6$ — 일반적으로 유한집합에서 $\lvert A\times B\rvert=\lvert A\rvert\,\lvert B\rvert$이며 이것이 셈의 기본 원리의 곱의 법칙이다. 한편 $B\times A$는 $(x,1)$ 같은 쌍들의 집합이므로 $A\times B\ne B\times A$: 순서쌍은 순서가 정체성의 일부다.
예제 4 (단사·전사 판정). $f_1:\mathbb{Z}\to\mathbb{Z}$, $f_1(n)=2n$은 단사($2n_1=2n_2\Rightarrow n_1=n_2$)이지만 전사가 아니다(홀수는 상에 없음). $f_2:\mathbb{Z}\to\mathbb{Z}$, $f_2(n)=\lfloor n/2\rfloor$는 전사($m$의 원상으로 $2m$이 있음)이지만 단사가 아니다($f_2(0)=f_2(1)=0$). $f_3:\mathbb{R}\to\mathbb{R}$, $f_3(x)=x^3$은 전단사다. 반면 $x\mapsto x^2$은 $\mathbb{R}\to\mathbb{R}$로는 단사도 전사도 아니지만, 정의역·공역을 $[0,\infty)\to[0,\infty)$로 바꾸면 전단사가 된다 — 단사·전사는 식이 아니라 (정의역, 공역, 규칙) 삼중항의 성질이다.
예제 5 (정리 4의 역방향 반례). $A=C=\{1\}$, $B=\{1,2\}$, $f(1)=1$, $g(1)=g(2)=1$로 두면 $g\circ f=\mathrm{id}_{\{1\}}$은 전단사다. 그러나 $g$는 단사가 아니고($g(1)=g(2)$) $f$는 전사가 아니다($2$가 상에 없음). 즉 $g\circ f$ 단사에서 $g$ 단사는, $g\circ f$ 전사에서 $f$ 전사는 따라 나오지 않는다.
예제 6 (상·역상 계산). $f:\mathbb{R}\to\mathbb{R}$, $f(x)=x^2$에 대해 $f([-2,1])=[0,4]$, $f^{-1}([1,4])=[-2,-1]\cup[1,2]$, $f^{-1}(\{-1\})=\varnothing$(역상은 공집합일 수 있다). $S=[-1,0]$, $S'=[0,1]$로 두면 $f(S\cap S')=f(\{0\})=\{0\}$이지만 $f(S)\cap f(S')=[0,1]\cap[0,1]=[0,1]$ — 정리 6(ii)의 포함이 진포함이 되는 사례이며, 원인은 $f(-1)=f(1)$이라는 단사성 실패다.
흔한 오해와 함정
- "$\varnothing$과 $\{\varnothing\}$은 같다" — 다르다. $\varnothing$은 원소가 0개, $\{\varnothing\}$은 공집합이라는 원소를 정확히 1개 가진 집합이다. $\mathcal{P}(\varnothing)=\{\varnothing\}$이 두 개념의 차이를 정확히 보여준다.
- "$\in$과 $\subseteq$는 비슷한 것" — 전혀 다르다. $a\in\{a,b\}$이지만 $a\subseteq\{a,b\}$는 (일반적으로) 무의미하거나 거짓이고, $\{a\}\subseteq\{a,b\}$이지만 $\{a\}\in\{a,b\}$는 거짓이다. 멱집합에서는 $S\subseteq A\iff S\in\mathcal{P}(A)$로 두 기호가 정확히 한 층 차이로 연결된다.
- "$f^{-1}(T)$라고 쓰려면 역함수가 있어야 한다" — 아니다. 역상은 임의의 함수에 대해 정의되는 집합 연산이고, 역함수는 전단사에만 존재하는 함수다(정리 5). 기호가 겹칠 뿐이다.
- "$f(S\cap S')=f(S)\cap f(S')$" — 일반적으로 거짓. 성립을 보장하는 것은 단사성이다(정리 6, 예제 6). 반면 역상은 교집합·합집합·여집합 모두와 무조건 호환된다.
- "몇 개의 입력에서 값이 다르면 단사" — 단사는 모든 쌍에 대한 전칭 명제다. 사례 확인으로는 증명이 되지 않고, $f(a_1)=f(a_2)\Rightarrow a_1=a_2$를 임의의 $a_1,a_2$에 대해 보여야 한다. 반대로 단사가 아님은 충돌하는 쌍 하나로 충분하다.
- "전사 여부는 식만 보면 안다" — 전사는 공역 선택에 의존한다. $x\mapsto x^2$은 공역이 $\mathbb{R}$이면 전사가 아니고 $[0,\infty)$이면 전사다(예제 4). 공역을 명시하지 않으면 전사라는 말 자체가 무의미하다.
큰 그림 / 연결
이 장의 개념들은 이후 모든 장의 문법이 된다. 함수를 "$A\times B$의 특별한 부분집합"으로 본 관점은 관계와 동치관계에서 일반 관계로 확장되고, 전단사는 집합의 크기에서 무한집합의 크기를 비교하는 유일한 잣대가 된다 — $\mathbb{N}$과 $\mathbb{Q}$ 사이의 전단사, $\mathbb{N}$과 $\mathbb{R}$ 사이 전단사의 부재가 그 장의 주제다. 조합론 쪽으로는 정리 2의 증명에 쓴 "서로소 분할로 나눠 세기"와 예제 3의 곱의 법칙이 셈의 기본 원리의 출발점이고, 부분집합을 0/1 벡터로 보는 관점($S\subseteq A$에 특성벡터를 대응시키는 전단사가 $\lvert\mathcal{P}(A)\rvert=2^n$의 다른 증명을 준다)은 순열과 조합의 전단사 논법으로 이어진다. 드모르간 법칙이 명제논리의 동치를 그대로 옮긴 것이라는 사실은 우연이 아니다 — 집합 연산의 대수는 논리 연산의 대수와 같은 구조를 공유하며, 원소 논법이란 결국 집합 명제를 논리 명제로 번역해 처리하는 절차다.
연습문제
- $A\subseteq B$, $A\cup B=B$, $A\cap B=A$ 세 조건이 서로 동치임을 증명하라.
- 드모르간 둘째 법칙 $(A\cap B)^c=A^c\cup B^c$를 원소 논법으로 직접 증명하라.
- $A\triangle B=(A\cup B)\setminus(A\cap B)$임을 보여라.
- $\mathcal{P}(\varnothing)$, $\mathcal{P}(\mathcal{P}(\varnothing))$, $\mathcal{P}(\mathcal{P}(\mathcal{P}(\varnothing)))$를 모두 원소 나열로 쓰고 크기를 구하라.
- $f:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$, $f(m,n)=m+n$과 $g:\mathbb{Z}\to\mathbb{Z}\times\mathbb{Z}$, $g(n)=(n,n+1)$ 각각의 단사·전사 여부를 판정하고 증명하라.
- $A\ne\varnothing$일 때, $f:A\to B$가 단사 $\iff$ $g\circ f=\mathrm{id}_A$인 $g:B\to A$(왼쪽 역함수)가 존재함을 증명하라.
- 임의의 $f:A\to B$와 $S\subseteq A$에 대해 $S\subseteq f^{-1}(f(S))$임을 보이고, 모든 $S$에 대해 등호가 성립할 필요충분조건이 $f$의 단사성임을 증명하라.
- 대칭차가 결합적임을 증명하라: $(A\triangle B)\triangle C=A\triangle(B\triangle C)$.
힌트 / 정답
- 순환 함의로 처리한다. $A\subseteq B\Rightarrow A\cup B=B$: $A\cup B\supseteq B$는 항상 참이고, $x\in A\cup B$이면 $x\in A\subseteq B$이거나 $x\in B$. $A\cup B=B\Rightarrow A\cap B=A$: $x\in A$이면 $x\in A\cup B=B$이므로 $x\in A\cap B$; 역포함은 자명. $A\cap B=A\Rightarrow A\subseteq B$: $x\in A=A\cap B$이면 $x\in B$.
- $x\in(A\cap B)^c\iff\lnot(x\in A\land x\in B)\iff x\notin A\lor x\notin B\iff x\in A^c\cup B^c$. 명제논리 드모르간 $\lnot(p\land q)\equiv\lnot p\lor\lnot q$를 사용.
- 양쪽 다 "정확히 한 집합에만 속하는 $x$들"임을 보인다: $x\in A\triangle B\iff(x\in A)\oplus(x\in B)$ (배타적 또는), 그리고 $x\in(A\cup B)\setminus(A\cap B)$도 같은 조건.
- $\mathcal{P}(\varnothing)=\{\varnothing\}$ (1개), $\mathcal{P}(\{\varnothing\})=\{\varnothing,\{\varnothing\}\}$ (2개), $\mathcal{P}(\{\varnothing,\{\varnothing\}\})=\{\varnothing,\{\varnothing\},\{\{\varnothing\}\},\{\varnothing,\{\varnothing\}\}\}$ (4개). 크기는 $2^0,2^1,2^2$로 정리 2와 일치.
- $f$: 전사($m\in\mathbb{Z}$의 원상으로 $(m,0)$)이지만 단사 아님($f(1,0)=f(0,1)=1$). $g$: 단사($(n,n+1)=(m,m+1)\Rightarrow n=m$)이지만 전사 아님($(0,0)$은 상에 없음 — 둘째 좌표가 첫째보다 1 커야 함).
- ($\Rightarrow$) $a_0\in A$를 고정. $b\in f(A)$이면 단사성으로 유일한 원상 $a_b$가 있어 $g(b)=a_b$, $b\notin f(A)$이면 $g(b)=a_0$으로 정의하면 $g(f(a))=a$. ($\Leftarrow$) $g\circ f=\mathrm{id}_A$가 단사이므로 정리 4(i)에 의해 $f$ 단사.
- 포함: $x\in S$이면 $f(x)\in f(S)$이므로 $x\in f^{-1}(f(S))$. 단사이면 등호: $x\in f^{-1}(f(S))$이면 $f(x)=f(s)$인 $s\in S$가 있고 단사성으로 $x=s\in S$. 단사가 아니면 $f(a)=f(a')$, $a\ne a'$에 대해 $S=\{a\}$로 두면 $a'\in f^{-1}(f(S))\setminus S$로 등호 실패.
- 특성함수 논법이 깔끔하다: $x$에 대해 $x\in A\triangle B\iff\chi_A(x)+\chi_B(x)\equiv1\pmod 2$. 따라서 양변 모두 "$x$가 $A,B,C$ 중 홀수 개에 속함"과 동치가 되어($\chi_A+\chi_B+\chi_C\bmod 2$는 덧셈의 결합법칙으로 묶는 순서와 무관) 두 집합이 같다.