관계와 함수

by I Seul Bee

수학에서 관계(relation)는 집합의 원소들 사이의 연결 여부를 나타내는 개념이다. 함수는 특별한 종류의 관계로서, 수학의 거의 모든 분야에서 핵심적인 역할을 한다. 이 장에서는 관계와 함수의 정의와 기본 성질을 살펴본다.

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)\}.\]

문제 4.1. 다음 관계를 원소나열법으로 나타내시오.

  1. \(A\)가 \(10\) 이하인 양의 정수의 모임이고, \((n,\,m)\in R\)일 필요충분조건을 "\(n\)이 \(m\)의 약수이다"라고 정의했을 때, 관계 \(R\).
  2. \(A\)가 \(10\) 이하인 양의 정수의 모임이고, \((n,\,m)\in E\)일 필요충분조건을 "\(n\)과 \(m\)의 공약수의 개수가 \(2\)이다"라고 정의했을 때, 관계 \(E\).
  3. \(\mathbb{Z}\)가 정수 전체의 집합이고, \(n\equiv m\)일 필요충분조건을 "\(n\)을 \(4\)로 나눈 나머지와 \(m\)을 \(4\)로 나눈 나머지가 같다"라고 정의했을 때, 관계 \(\equiv\).
  4. \(\mathbb{N}\)이 양의 정수 전체 집합이고, \(x\)와 \(y\)가 \(y=x^2\)을 만족시키는 것을 \(xRy\)로 나타낼 때, 관계 \(R\).

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

  • 정의역(domain): \(\text{dom}(R) = \{a \in A \mid \exists b \in B : (a,\,b) \in R\}.\)
  • 치역(range): \(\text{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{ and }\, (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\}.\]

문제 4.2. 합성관계와 역관계는 언제 정의되는가? 즉, 주어진 관계가 어떤 조건을 만족시킬 때 합성관계와 역관계를 정의할 수 있는가?

관계의 합성에 대하여 결합법칙이 성립한다. 즉, \(R \subseteq A \times B\), \(S \subseteq B \times C\), \(T \subseteq C \times D\)일 때, 다음이 성립한다. \[(T \circ S) \circ R = T \circ (S \circ R)\] 또한 역관계와 관련하여 다음이 성립한다.

  • \((R^{-1})^{-1} = R\)
  • \((S \circ R)^{-1} = R^{-1} \circ S^{-1}\)
  • \(\text{dom}(R^{-1}) = \text{ran}(R)\)
  • \(\text{ran}(R^{-1}) = \text{dom}(R)\)

문제 4.3. 위 등식을 증명하시오.

문제 4.4. 관계의 합성의 결합법칙을 증명하시오.

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)라고 부른다.

4. 관계의 예

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

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

문제 4.5. 위 예에서 살펴본 관계가 각각 동치관계 또는 순서관계의 조건을 만족시킴을 확인하시오.

문제 4.6. \(S\)가 집합들의 모임이라고 하자. (모든 집합의 모임이라는 뜻은 아니다.) 이때 집합의 대등관계(원소의 개수가 같은 관계)는 \(S\) 위의 동치관계임을 증명하시오.

문제 4.7. \(\mathcal{V}\)가 실벡터공간들의 모임이라고 하자. 이때 동형 관계는 \(\mathcal{V}\) 위의 동치관계임을 증명하시오.

문제 4.8. 집합의 '분할'(partition)의 정의를 찾아보고, 분할과 동치관계가 어떠한 관계가 있는지 탐구하시오.

5. 제한된 관계

관계 \(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\)도 반사적이다. 대칭성과 추이성도 마찬가지로 이어받는다.

6. 함수의 정의

함수(function) \(f: A \to 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: A \to B\)에 대하여 다음과 같이 정의한다.

  • \(A\)를 \(f\)의 정의역(domain)이라고 부른다.
  • \(B\)를 \(f\)의 공역(codomain)이라고 부른다.
  • \(\{y\in B \mid y=f(x) \text{ for some } x\in A \} \subseteq B\)를 \(f\)의 치역(range)이라고 부른다.

문제 4.9. 집합 \(A\), \(B\)와 관계 \(R\)이 다음과 같이 정의되어 있을 때, \(R\)이 \(A\)로부터 \(B\)로의 함수가 되는지 판별하시오.

  1. \(A\)와 \(B\)가 실수 전체 집합이고, \((x,\,y)\in R\)일 필요충분조건은 \(x=y^2\)이다.
  2. \(A\)와 \(B\)가 양의 실수 전체의 집합이고, \((x,\,y)\in R\)일 필요충분조건은 \(x=y^2\)이다.
  3. \(A\)와 \(B\)가 양의 정수 전체 집합이고, \((p,\,q)\in R\)일 필요충분조건은 \(p\)가 \(q\)의 약수인 것이다.
  4. \(A\)와 \(B\)가 양의 정수 전체 집합이고, \((p,\,q)\in R\)일 필요충분조건은 \(12\)와 \(p\)의 최소공배수가 \(q\)인 것이다.

7. 함수의 종류

함수 \(f: 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: \mathbb{R} \to \mathbb{R}\), \(f(x) = x^2\)은 일대일함수도 아니고 위로의 함수도 아니다.
  • \(f: [0,\, \infty) \to \mathbb{R}\), \(f(x) = x^2\)은 일대일함수이지만 위로의 함수는 아니다.
  • \(f: \mathbb{R} \to [0,\, \infty)\), \(f(x) = x^2\)은 위로의 함수이지만 일대일함수는 아니다.
  • \(f: \mathbb{R} \to \mathbb{R}\), \(f(x) = 2x + 1\)은 일대일대응이다.

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

문제 4.10. 제한함수(restriction)와 확장함수(extension)의 개념을 조사해 보자.

8. 함수의 합성과 역함수

함수 \(f: A \to B\)와 \(g: B \to C\)가 주어졌을 때, 합성관계 \(g\circ f\)는 함수가 되기 위한 두 조건을 모두 만족시킨다. 이때 \(g\circ f : A \rightarrow C\)를 \(f\)와 \(g\)의 합성함수(composite function)라고 부른다. 합성함수는 다음과 같은 식으로 정의할 수도 있다. \[(g \circ f)(a) = g(f(a)) \quad \text{for all }\, a \in A .\] 함수의 합성에 대하여 결합법칙이 성립한다. 즉 다음 등식이 성립한다. \[(h \circ g) \circ f = h \circ (g \circ f).\] 함수 \(f: A \to B\)가 일대일대응일 때, 역관계 \(f^{-1}\)는 함수가 되기 위한 두 조 건을 모두 만족시킨다. 이때 \(f^{-1}\)를 \(f\)의 역함수(inverse function)라고 부른다. 어떤 함수의 역함수가 존재할 필요충분조건은 그 함수가 일대일대응인 것이다.

어떤 함수의 역함수가 존재할 때, 함수와 그 역함수의 합성은 다음과 같다.

  • \(f^{-1} \circ f = \text{id}_A\) (여기서 \(\text{id}_A\)는 \(A\)의 항등함수)
  • \(f \circ f^{-1} = \text{id}_B\)

9. 함수와 관련된 정리들

함수의 합성과 관련하여 다음이 성립한다.

  • \(f: A \to B\), \(g: B \to C\)가 모두 일대일함수이면 \(g \circ f\)도 일대일함수이다.
  • \(f: A \to B\), \(g: B \to C\)가 모두 위로의 함수이면 \(g \circ f\)도 위로의 함수이다.
  • \(g \circ f\)가 일대일함수이면 \(f\)는 일대일함수이다.
  • \(g \circ f\)가 위로의 함수이면 \(g\)는 위로의 함수이다.

문제 4.11. 함수의 합성 및 대응과 관련된 위 성질을 증명하시오.

함수 \(f:A \rightarrow B\)와 집합 \(C\subseteq A\) 그리고 \(D\subseteq B\)에 대하여 다음과 같이 정의한다.

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

문제 4.12. \(A\)와 \(B\)가 집합이고 \(\left\{ A_i \right\}_{i\in I}\)가 집합족이며, 임의의 \(i\in I\)에 대하여 \(A_i \subseteq A\)를 만족시킨다고 하자. 그리고 \(f:A \rightarrow B\)가 함수라고 하자. 다음을 증명하시오.

  1. \(f\left( \bigcup_{i\in I} A_i \right) = \bigcup_{i\in I} f\left( A_i \right) \)
  2. \(f\left( \bigcap_{i\in I} A_i \right) \subseteq \bigcap_{i\in I} f\left( A_i \right) \)

특히 (2)에서 등식이 성립하지 않는 예를 제시하시오. 또한 \(f\)가 일대일함수일 때는 (2)에서 등식이 성립함을 증명하시오.

문제 4.13. \(A\)와 \(B\)가 집합이고 \(\left\{ B_j \right\}_{j\in J}\)가 집합족이며, 임의의 \(j\in J\)에 대하여 \(B_j \subseteq B\)를 만족시킨다고 하자. 그리고 \(f:A \rightarrow B\)가 함수라고 하자. 다음을 증명하시오.

  1. \(f^{-1} \left( \bigcup_{j\in J} B_j \right) = \bigcup_{j\in J} f^{-1}\left( B_j \right) \)
  2. \(f^{-1} \left( \bigcap_{j\in J} B_j \right) = \bigcap_{j\in J} f^{-1}\left( B_j \right) \)

집합과 수리논리 첫걸음 목차 보기

명제와 논리 집합의 개념 다양한 집합의 연산 관계와 함수 유한집합과 무한집합 자연수 집합의 기수 집합의 서수 집합론의 공리 선택 공리 형식논리 명제논리의 개념 명제논리의 건전성과 완전성 일계논리의 구문론 일계논리의 의미론 일계논리의 추론규칙 일계논리의 콤팩트성 페아노 산술 불완전성 정리