Appendix C 집합과 함수에 관한 용어

이 부록에서는 “전단사”, “동치류” 등 집합과 함수에 관한 몇 가지 개념을 다룹니다.

전문가를 위한 참고: 이 장에서는 기초론적 문제를 다루지 않습니다. 그러한 내용에 관심이 있다면 장 89(및 그 이후)를 참조하십시오. 따라서 대부분의 주장은 증명하지 않겠습니다.

C.1 집합

이 책에서 집합은 단지 (무엇이든 간에) 원소들의 모임입니다. 예를 들어 집합 $\mathbb{N}=\{1,2,3,4,\dots\}$ 는 양의 정수 전체이고, $\mathbb{Z}=\{\dots,-2,-1,0,1,2,\dots\}$ 는 모든 정수의 집합입니다. 또 다른 예로, 다음과 같은 사람들의 집합이 있습니다:

H=\left\{x\mid\text{$x$는 깃털 없는 두 발 동물입니다}\right\}.

(여기서 “ $\mid$ ”는 “ 을 만족하는”을 의미합니다.)

원소가 하나도 없는 집합도 있으며, 이를 공집합이라고 부릅니다. 공집합은 $\varnothing$ 으로 나타냅니다.

관례적으로 집합에는 ( $H$ 처럼) 대문자를, 집합의 원소에는 ( $x$ 처럼) 소문자를 사용합니다.

정의 C.1.1.

“ $x$ 가 $S$ 에 속한다”는 뜻으로 $x\in S$ 라고 씁니다. 예를 들어 $3\in\mathbb{N}$ 입니다.

정의 C.1.2.

집합 $A$ 의 모든 원소가 집합 $B$ 에도 속하면, $A$ 를 $B$ 의 부분집합이라고 하고 $A\subseteq B$ 로 나타냅니다. 더 나아가 $A\neq B$ 이면, $A$ 를 진부분집합이라고 하고 $A\subsetneq B$ 라고 씁니다. (이는 $\leq$ 와 $<$ 의 관계와 유사합니다.)

집합 $A$ 가 주어졌을 때, 모든 부분집합의 집합을 $2^{A}$ 또는 $\mathcal{P}(A)$ 로 나타내고 $A$ 의 멱집합이라고 부릅니다.

예제 C.1.3 (부분집합의 예).

(a)

$\{1,2,3\}\subseteq\mathbb{N}\subseteq\mathbb{Z}$ .
(b)

임의의 집합 $A$ 에 대해 $\varnothing\subseteq A$ 입니다. (왜 그렇습니까?)
(c)

임의의 집합 $A$ 에 대해 $A\subseteq A$ 입니다.
(d)

$A=\{1,2\}$ 이면 $2^{A}=\left\{\varnothing,\{1\},\{2\},\{1,2\}\right\}$ 입니다.

정의 C.1.4.

다음과 같이 씁니다.

•

$A\cup B$ 는 $A$ 와 $B$ 중 어느 한쪽에 속하는 (둘 다에 속할 수도 있는) 원소들의 집합을 나타내며, $A$ 와 $B$ 의 합집합이라고 부릅니다.
•

$A\cap B$ 는 $A$ 와 $B$ 모두에 속하는 원소들의 집합을 나타내며, $A$ 와 $B$ 의 교집합이라고 부릅니다.
•

$A\setminus B$ 는 $A$ 에는 속하지만 $B$ 에는 속하지 않는 원소들의 집합을 나타냅니다.

예제 C.1.5 (집합 연산의 예).

$A=\{1,2,3\}$ 이고 $B=\{3,4,5\}$ 라고 합시다. 그러면

	$\displaystyle A\cup B$	$\displaystyle=\{1,2,3,4,5\}$
	$\displaystyle A\cap B$	$\displaystyle=\{3\}$
	$\displaystyle A\setminus B$	$\displaystyle=\{1,2\}.$

연습문제 C.1.6.

스스로 확인해 보십시오: 임의의 집합 $A$ 와 $B$ 에 대해 $A\cap B\subseteq A\subseteq A\cup B$ 가 성립합니다.

다음은 자주 등장하는 집합들입니다:

•

$\mathbb{C}$ 는 $3.2+\sqrt{2}i$ 와 같은 복소수들의 집합입니다.
•

$\mathbb{R}$ 은 $\sqrt{2}$ 나 $\pi$ 와 같은 실수들의 집합입니다.
•

$\mathbb{N}$ 은 $5$ 나 $9$ 와 같은 양의 정수의 집합입니다.
•

$\mathbb{Q}$ 는 $7/3$ 과 같은 유리수의 집합입니다.
•

$\mathbb{Z}$ 는 $-2$ 나 $8$ 과 같은 정수의 집합입니다.

(이들은 예상하시는 대로 “씨”, “알”, “엔”, “큐”, “제드”로 읽습니다.)

C.2 함수

두 집합 $A$ 와 $B$ 가 주어졌을 때, $A$ 에서 $B$ 로 가는 함수 $f$ 는 $A$ 의 모든 원소를 $B$ 의 어떤 원소에 대응시키는 것입니다.

$A$ 를 $f$ 의 정의역, $B$ 를 공역이라고 부릅니다. 이를 $f\colon A\to B$ 또는 $A\xrightarrow{f}B$ 로 씁니다.

표기의 남용 C.2.1.

이름 $f$ 가 중요하지 않을 때에는 흔히 간단히 $A\to B$ 로 씁니다.

$f$ 가 $a$ 를 $b$ 로 보낸다는 것을 나타내기 위해 $f(a)=b$ 또는 $a\mapsto b$ 로 씁니다.

$B$ 가 $0$ 을 원소로 가지고 $f(a)=0$ 이면, 흔히 $a$ 를 $f$ 의 근 또는 영점이라 하고, $f$ 가 $a$ 에서 소멸한다고 말합니다.

C.2.1 단사 / 전사 / 전단사 함수

정의 C.2.2.

함수 $f\colon A\to B$ 가 다음과 같은 의미에서 “일대일”이면 단사라고 합니다: $f(a)=f(a^{\prime})$ 이면 $a=a^{\prime}$ 입니다. 다시 말해, 임의의 $b\in B$ 에 대하여 $f(a)=b$ 를 만족하는 $a\in A$ 가 많아야 하나 존재합니다.

이를 강조하기 위해 흔히 $f\colon A\hookrightarrow B$ 로 씁니다.

정의 C.2.3.

함수 $f\colon A\to B$ 가 다음과 같은 의미에서 “위로의 함수”이면 전사라고 합니다: 임의의 $b\in B$ 에 대하여 $f(a)=b$ 를 만족하는 $a\in A$ 가 적어도 하나 존재합니다.

이를 강조하기 위해 흔히 $f\colon A\twoheadrightarrow B$ 로 씁니다.

정의 C.2.4.

함수 $f\colon A\to B$ 가 단사이면서 동시에 전사이면 전단사라고 합니다. 다시 말해, 각 $b\in B$ 에 대하여 $f(a)=b$ 를 만족하는 $a\in A$ 가 정확히 하나 존재합니다.

예제 C.2.5 (함수의 예).

여기서 “사람”이란 “살아 있는 깃털 없는 두 발 동물”을 뜻합니다.

(a)

모든 사람을 그 사람의 나이(가장 가까운 정수로 반올림한 햇수)로 보내는 함수가 있습니다. 예를 들어 나이가 $20$ 인 사람이 많이 있으므로, 이 함수는 단사가 아닙니다. 또한 이 함수는 전사도 아닙니다: 나이가 $10000$ 인 사람은 없습니다.
(b)

모든 미국 시민을 그 사람의 사회보장번호로 보내는 함수가 있습니다. 이 함수 역시 전사가 아니지만(사회보장번호가 $3$ 인 사람은 없습니다), 적어도 단사이기는 합니다(사회보장번호가 같은 두 사람은 없습니다).

예제 C.2.6 (전단사의 예).

(a)

$A=\{1,2,3,4,5\}$ , $B=\{6,7,8,9,10\}$ 이라 합시다. 그러면 $a\mapsto a+5$ 로 주어지는 함수 $f\colon A\to B$ 는 전단사입니다.
(b)

좌석이 $30$ 개인 교실에서 모든 좌석에 학생이 정확히 한 명씩 앉아 있습니다. 따라서 각 학생을 그 학생이 앉은 좌석으로 보내는 함수는 전단사이며, 특히 학생은 정확히 $30$ 명입니다.

비고 C.2.7.

편의상 $A$ 와 $B$ 가 유한집합이라고 가정합시다. 그러면 다음이 성립합니다:

•

$f\colon A\hookrightarrow B$ 가 단사이면, $A$ 의 크기는 $B$ 의 크기 이하입니다.
•

$f\colon A\twoheadrightarrow B$ 가 전사이면, $A$ 의 크기는 $B$ 의 크기 이상입니다.
•

$f\colon A\to B$ 가 전단사이면, $A$ 의 크기는 $B$ 의 크기와 같습니다.

이제 $f\colon A\to B$ 가 전단사이면 “ $f$ 를 거꾸로 적용”할 수 있다는 점에 주목하십시오. (예를 들어, 각 학생을 그 학생이 앉아 있는 자리로 사상하는 대신, 각 자리를 그 자리에 앉아 있는 학생으로 사상합니다.) 이를 역함수라고 하며, $f^{-1}\colon B\to A$ 로 표기합니다.

C.2.2 상과 역상

$X\xrightarrow{f}Y$ 를 함수라고 합시다.

정의 C.2.8.

$T\subseteq Y$ 라고 합시다. 역상 $f^{\text{pre}}(T)$ 는 $f(x)\in T$ 를 만족하는 모든 $x\in X$ 의 집합입니다. 따라서 $f^{\text{pre}}(T)$ 는 $X$ 의 부분집합입니다.

예제 C.2.9 (역상의 예).

$f\colon H\to\mathbb{Z}$ 를 앞에서 본 나이 함수라고 합시다. 그러면

(a)

$f^{\text{pre}}(\{13,14,15,16,17,18,19\})$ 는 십대들의 집합입니다.
(b)

$f^{\text{pre}}(\{0\})$ 은 신생아들의 집합입니다.
(c)

그렇게 나이가 많은 사람은 없을 것이므로 $f^{\text{pre}}(\{1000,1001,1002,\dots\})=\varnothing$ 입니다.

표기의 남용 C.2.10.

표기 남용으로 $f^{\text{pre}}(\{y\})$ 를 $f^{\text{pre}}(y)$ 로 줄여 쓸 수 있습니다. 예를 들어 위의 $f^{\text{pre}}(\{0\})$ 은 $f^{\text{pre}}(0)$ 으로 줄여 씁니다.

쌍대 개념은 다음과 같습니다:

정의 C.2.11.

$S\subseteq X$ 라고 합시다. 상 $f^{\text{img}}(S)$ 는 $f(s)$ 꼴인 모든 것의 집합입니다.

예제 C.2.12 (상의 예).

$A=\{1,2,3,4,5\}$ , $B=\mathbb{Z}$ 라고 합시다. 다음과 같이 주어진 함수 $f\colon A\to B$ 를 생각합시다.

f(1)=17\quad f(2)=17\quad f(3)=19\quad f(4)=30\quad f(5)=234.

(a)

상 $f^{\text{img}}(\{1,2,3\})$ 은 집합 $\{17,19\}$ 입니다.
(b)

상 $f^{\text{img}}(A)$ 는 집합 $\{17,19,30,234\}$ 입니다.

질문 C.2.13.

$f\colon A\twoheadrightarrow B$ 가 전사라고 합시다. $f^{\text{img}}(A)$ 는 무엇입니까?

C.3 동치 관계

이제 $X$ 를 고정된 집합이라고 합시다. $X$ 위의 이항 관계 $\sim$ 는 각 $x$ 와 $y$ 에 대해 $x\sim y$ 에 “참” 또는 “거짓”이라는 진릿값을 부여합니다. 이제 $X$ 위의 동치 관계 $\sim$ 란 다음 공리들을 만족하는 이항 관계입니다:

•

반사성: $x\sim x$ 가 성립합니다.
•

대칭성: $x\sim y$ 이면 $y\sim x$ 입니다.
•

추이성: $x\sim y$ 이고 $y\sim z$ 이면 $x\sim z$ 입니다.

그러면 동치류는 서로 동치인 모든 것들의 집합입니다. $X$ 가 이 동치류들에 의해 분할됨을 보일 수 있습니다:

예제 C.3.1 (동치 관계의 예).

$\mathbb{N}$ 을 양의 정수의 집합이라고 합시다. 그리고 $a$ 와 $b$ 의 마지막 자릿수가 같으면 $a\sim b$ 라고 정한다고 합시다. 예를 들어 $131\sim 211$ , $45\sim 125$ 등이 성립합니다.

그러면 $\sim$ 는 동치 관계입니다. 이 관계는 $\mathbb{N}$ 을 끝자리 숫자마다 하나씩, 열 개의 동치류로 분할합니다.

흔히 동치류들의 집합은 $X/{\sim}$ 로 표기합니다(“ $X$ mod sim”이라고 읽습니다).