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)

모든 미국 시민을 그들의 사회보장번호로 보내는 함수가 있습니다. 이 함수 역시 SSN이 $3$ 인 사람이 없으므로 전사가 아니지만, 적어도 동일한 SSN을 가진 두 사람이 없으므로 단사이기는 합니다.

예제 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”이라고 읽습니다).