관계와 함수

앞 장에서는 순서쌍과 데카르트 곱을 정의하였다. 이제 데카르트 곱의 부분집합을 사용하여 원소 사이의 관계를 나타내고, 그중 특별한 형태를 갖는 함수의 개념으로 나아간다. 이 장에서는 관계와 함수의 정의와 기본 성질을 살펴본다.

1. 관계의 정의

집합 \(A\)와 \(B\)에 대하여, \(A\)에서 \(B\)로의 관계(relation) \(R\)은 데카르트 곱 \(A\times B\)의 부분집합이다. 즉, \[R\subseteq A\times B\] 일 때 \(R\)을 \(A\)에서 \(B\)로의 관계라고 부른다. \((a,b)\in R\)일 때, “\(a\)와 \(b\) 사이에 \(R\)-관계가 있다” 또는 “\(a\)와 \(b\)가 관계 \(R\)에 있다”라고 말한다. 이것을 \(aRb\)로 나타내기도 한다.

특히 \(A=B\)인 경우, \(R\subseteq A\times A\)를 \(A\) 위의 관계라고 부른다.

예를 들어, \(A=\{1,\,2,\,3\}\)일 때, “작거나 같다” 관계를 원소나열법으로 나타내면 다음과 같다. \[R=\{(1,\,1),\,(1,\,2),\,(1,\,3),\,(2,\,2),\,(2,\,3),\,(3,\,3)\}.\]

관계 \(R\subseteq A\times B\)의 정의역과 치역을 다음과 같이 정의한다.

• 정의역(domain): \(\operatorname{dom}(R)=\{a\in A\mid \exists b\in B,\ (a,b)\in R\}.\)
• 치역(range): \(\operatorname{ran}(R)=\{b\in B\mid \exists a\in A,\ (a,b)\in R\}.\)

2. 합성관계와 역관계

관계 \(R\subseteq A\times B\)와 \(S\subseteq B\times C\)가 주어졌을 때, 합성관계(composite relation) \(S\circ R\)을 다음과 같이 정의한다. \[S\circ R=\{(a,\,c)\in A\times C\mid \exists b\in B,\ (a,\,b)\in R\text{이고 }(b,\,c)\in S\}.\]

관계 \(R\subseteq A\times B\)의 역관계(inverse relation) \(R^{-1}\)를 다음과 같이 정의한다. \[R^{-1}=\{(b,\,a)\in B\times A\mid (a,\,b)\in R\}.\]

3. 관계의 종류

\(R\)이 집합 \(A\) 위의 관계라고 하자. 즉 \(R\subseteq A\times A\)라고 하자. 이때 다음과 같이 정의한다.

• \(R\)이 반사적(reflexive) 관계라 함은, 모든 \(a\in A\)에 대해 \((a,a)\in R\)을 만족시키는 것을 의미한다.
• \(R\)이 대칭적(symmetric) 관계라 함은, \((a,b)\in R\)일 때마다 \((b,a)\in R\)이 성립하는 것을 의미한다.
• \(R\)이 반대칭적(antisymmetric) 관계라 함은, \((a,b)\in R\)이고 \((b,a)\in R\)일 때마다 \(a=b\)가 성립하는 것을 의미한다.
• \(R\)이 추이적(transitive) 관계라 함은, \((a,b)\in R\)이고 \((b,c)\in R\)일 때마다 \((a,c)\in R\)이 성립하는 것을 의미한다.

특히 수학에서 중요한 역할을 하는 관계는 동치관계와 순서관계이다.

• 반사적이고 대칭적이며 추이적인 관계를 동치관계(equivalence relation)라고 부른다.
• 반사적이고 반대칭적이며 추이적인 관계를 순서관계(order relation)라고 부른다. [여기서 순서관계는 흔히 부분순서관계(partial order)라고 부르는 개념이다. 임의의 두 원소가 비교 가능하다는 조건까지 만족시키면 전순서(total order)라고 부른다.]

4. 관계의 예

수학에서 자주 등장하는 관계의 예를 살펴보자.

• 실수 집합에서의 등호 관계: \(R=\{(x,x)\mid x\in\mathbb{R}\}\)는 동치관계이다.
• 실수 집합에서의 부등호 관계: \(R=\{(x,y)\in\mathbb{R}\times\mathbb{R}\mid x\leq y\}\)는 순서관계이다.
• 집합족에서의 부분집합 관계: 집합족 \(\mathcal{F}\)에 대하여 \(R=\{(A,B)\in\mathcal{F}\times\mathcal{F}\mid A\subseteq B\}\)는 순서관계이다.
• 정수 집합에서의 합동 관계: 양의 정수 \(n\)에 대하여 \(R=\{(a,b)\in\mathbb{Z}\times\mathbb{Z}\mid a\equiv b\pmod{n}\}\)은 동치관계이다.
• 양의 정수 집합에서의 약수 관계: \(R=\{(a,b)\in\mathbb{Z}_+\times\mathbb{Z}_+\mid a\text{는 }b\text{의 약수}\}\)는 순서관계이다. 여기서 \(\mathbb{Z}_+\)는 양의 정수 전체의 집합이다.

5. 동치류와 분할

\(R\)이 집합 \(A\) 위의 동치관계이고 \(a\in A\)라고 하자. \(a\)의 동치류(equivalence class)를 \[[a]_R=\{x\in A\mid xRa\}\] 로 정의한다. 문맥에서 관계 \(R\)이 분명하면 \([a]\)라고 간단히 쓰기도 한다. 모든 동치류의 집합 \[A/R=\{[a]_R\mid a\in A\}\] 을 \(R\)에 의한 몫집합(quotient set)이라고 부른다.

집합 \(A\)의 분할(partition)은 다음 두 조건을 만족시키는 \(A\)의 부분집합들의 집합족 \(\mathcal{P}\)이다.

1. 모든 \(P\in\mathcal{P}\)에 대하여 \(P\ne\varnothing\)이고, \(\displaystyle\bigcup_{P\in\mathcal{P}}P=A\)이다.
2. 서로 다른 \(P,Q\in\mathcal{P}\)에 대하여 \(P\cap Q=\varnothing\)이다.

6. 제한된 관계

관계 \(R\subseteq A\times A\)와 부분집합 \(B\subseteq A\)가 주어졌을 때, \(R\)을 \(B\) 위로 제한하여 얻은 제한된 관계(restriction) \(R|_B\)를 다음과 같이 정의한다. \[R|_B=R\cap(B\times B)=\{(x,y)\in R\mid x,y\in B\}.\]

예를 들어, 실수에서의 순서관계 \(\leq\)를 유리수 집합 \(\mathbb{Q}\)로 제한하면 유리수에서의 순서관계를 얻는다. 제한된 관계는 원래 관계의 성질을 이어받는다. 즉, \(R\)이 반사적, 대칭적, 반대칭적, 추이적 관계이면 \(R|_B\)도 각각 같은 성질을 갖는다. 따라서 동치관계의 제한은 동치관계이고 순서관계의 제한은 순서관계이다.

7. 함수의 정의

이 책에서는 함수(function) \(f\colon A\to B\)를 정의역 \(A\), 공역 \(B\), 그리고 다음 두 조건을 만족시키는 관계 \(f\subseteq A\times B\)를 함께 지정한 것으로 이해한다. [이렇게 정의역과 공역도 함수의 자료에 포함시키면, 같은 대응 규칙을 사용하더라도 정의역이나 공역이 다르면 서로 다른 함수가 된다.]

1. 함숫값의 존재성: 모든 \(a\in A\)에 대하여 \((a,b)\in f\)인 \(b\in B\)가 존재한다.
2. 함숫값의 유일성: \((a,b)\in f\)이고 \((a,c)\in f\)이면 \(b=c\)이다.

다시 말해, 함수는 정의역의 모든 원소에 공역의 원소를 정확히 하나씩 대응시키는 관계이다.

\((a,b)\in f\)일 때, \(b\)를 \(a\)의 상(image) 또는 \(f\)에 의한 \(a\)의 함숫값이라고 부르고 \(f(a)=b\)로 나타낸다.

함수 \(f\colon A\to B\)에서 \(A\)를 \(f\)의 정의역(domain), \(B\)를 \(f\)의 공역(codomain)이라고 부른다. 또한 \[\{f(x)\mid x\in A\}\subseteq B\] 를 \(f\)의 치역(range)이라고 부른다. 함수로서의 정의역은 관계로 보았을 때의 \(\operatorname{dom}(f)\)와 같고, 치역은 \(\operatorname{ran}(f)\)와 같다.

8. 함수의 종류

함수 \(f\colon A\to B\)를 원소의 대응 양상에 따라 다음과 같이 분류한다.

• 일대일함수(one-to-one): \(f\)가 “\(f(a_1)=f(a_2)\)이면 \(a_1=a_2\)이다”를 만족시킨다.
• 위로의 함수(onto): \(f\)가 “모든 \(b\in B\)에 대해, \(f(a)=b\)인 \(a\in A\)가 존재한다”를 만족시킨다.
• 일대일대응(one-to-one correspondence): \(f\)가 일대일함수이면서 위로의 함수이다. [일대일함수, 위로의 함수, 일대일대응을 각각 단사함수(injective function), 전사함수(surjective function), 전단사함수(bijective function)라고 부르기도 한다.]

예를 들어 다음과 같은 함수를 살펴보자.

• \(f\colon\mathbb{R}\to\mathbb{R}\), \(f(x)=x^2\)은 일대일함수도 아니고 위로의 함수도 아니다.
• \(f\colon[0,\infty)\to\mathbb{R}\), \(f(x)=x^2\)은 일대일함수이지만 위로의 함수는 아니다.
• \(f\colon\mathbb{R}\to[0,\infty)\), \(f(x)=x^2\)은 위로의 함수이지만 일대일함수는 아니다.
• \(f\colon\mathbb{R}\to\mathbb{R}\), \(f(x)=2x+1\)은 일대일대응이다.

위 예에서 보다시피, 같은 식을 사용하여 정의된 함수일지라도 정의역이나 공역이 다르면 다른 함수이다.

두 집합 \(A\), \(B\) 사이에 일대일대응이 존재하면 \(A\)와 \(B\)가 대등(equinumerous)하다고 한다. 대등은 집합의 크기를 비교하는 기본 개념이다.

함수 \(f\colon A\to B\)와 부분집합 \(C\subseteq A\)에 대하여 제한함수(restriction) \(f|_C\colon C\to B\)를 \[f|_C(x)=f(x)\quad(x\in C)\] 로 정의한다. 한편 \(A\subseteq D\)이고 함수 \(g\colon D\to B\)가 \(g|_A=f\)를 만족시키면 \(g\)를 \(f\)의 확장함수(extension)라고 부른다.

9. 함수의 합성과 역함수

함수 \(f\colon A\to B\)와 \(g\colon B\to C\)가 주어졌을 때, 합성관계 \(g\circ f\)는 함수가 되기 위한 두 조건을 모두 만족시킨다. 이때 \(g\circ f\colon A\to C\)를 \(f\)와 \(g\)의 합성함수(composite function)라고 부른다. 모든 \(a\in A\)에 대하여 \[(g\circ f)(a)=g(f(a))\] 가 성립한다. 관계의 합성에 대한 결합법칙에서 함수의 합성에 대한 결합법칙 \[(h\circ g)\circ f=h\circ(g\circ f)\] 도 바로 얻어진다.

집합 \(A\)의 항등함수(identity function) \(\operatorname{id}_A\colon A\to A\)를 \(\operatorname{id}_A(a)=a\)로 정의한다.

10. 함수와 관련된 정리들

함수 \(f\colon A\to B\)와 집합 \(C\subseteq A\), \(D\subseteq B\)에 대하여 다음과 같이 정의한다.

• \(f\)에 의한 \(C\)의 상(image): \(f(C)=\{f(x)\mid x\in C\}\)
• \(f\)에 의한 \(D\)의 역상(inverse image): \(f^{-1}(D)=\{x\in A\mid f(x)\in D\}\)

역상 \(f^{-1}(D)\)는 \(f\)가 일대일대응이 아니어도 항상 정의된다. 따라서 이 표기에서 \(f^{-1}\)는 역함수를 뜻하는 것이 아니라 역상을 나타내는 표기의 일부이다.