Chapter 4.

Chapter 4. 관계(Relations)

4.1 기본개념 및 정의

두 가정 A, B에는 아들이 각각 4명, 3명씩 있다. 즉, A = {a1, a2, a3, a4}, B = {b1, b2, b3} 두 집합의 구성원 사이에 의형제를 맺다보니

“a2는 b1의 형이다.” “a3는 b3의 형이다.”

일 때, 이것을 순서쌍의 집합 R = {(a2, b1), (a3, b3)}로 나타낼 수 있다. 이 와같이 두 집합의 원소 사이의 일종의 관계를 순서쌍으로 표시할 수있다는 것 에 착안하여 다음과 같은 정의를 얻는다.

Definition 4.1.1 집합 A에서 집합 B로의 관계(relation) R은 A × B의 하나의 부분집합을 의미한다. 여기서 (a, b) ∈ R을 aRb로 나타내기도 하고, a는 R에 따라 b와 관계된다 라고 읽는다.

Definition 4.1.2 집합 A에서의 관계(relation) R은 A × A의 임의의 부 분집합이다.

Definition 4.1.2 R은 집합 A에서의 관계라 하자.

1. 반사율: 모든 x ∈ A에 대하여, (x, x) ∈ R일 때, 관계 R은 반사 적(reflexive) 이다 라고한다.

2. 대칭율: (x, y) ∈ R =⇒ (y, x) ∈ R을 만족하면, 관계 R은 대칭 적(symmetric) 이다 라고한다.

3. 반대칭율: (x, y) ∈ R ∧ (y, x) ∈ R =⇒ x = y을 만족하면, 관계 R은 반대칭적(antisymmetric) 이다 라고한다.

4. 추이율: (x, y) ∈ R ∧ (y, z) ∈ R =⇒ (x, z) ∈ R을 만족하면, 관계 R은 추이적(transitive) 이다 라고한다.

Example X = {1, 2, 3, 4}에서의 관계

R = {(1, 1), (1, 4), (2, 2), (2, 4), (4, 1), (4, 2), (4, 4)}

에 대하여 반사율, 대칭율, 반대칭율, 추이율을 말하여라.

Examples:

1. A = {1, 2, 3, 4}에서

R = {(1, 1), (2, 4), (3, 3), (4, 1), (4, 4)}

이라하면 R은 반사율을 만족하지 않는다.

2. 집합 A는 유클리드 평면에서의 삼각형들의 집합이라하자. 집합 A에서 의 두 원소간의 관계는 “닮음”이라고 할 때, 이 관계는 반사율, 대칭율, 반대칭율, 추이율을 만족하는가?

3. 실수집합

R

R

R

R

4. A를 집합족이라하자. R의 두 집합의 관계는 다음과 같이 주어진다.

(A, B) ∈ A × A 이면, A ⊆ B이다. 그러면 R은 어떤관계의 정의를 만족하는가?

Definition 4.1.3 집합 I_A := {(x, x) | x ∈ A}를 대각 그래프 또는 대각관 계라고 한다.

Remark 관계 R이 반사적 ⇐⇒ I_A ⊆ R.

Theorem 1 R이 집합 A에서의 관계일 때,

(1) R이 대칭적 ⇐⇒ R = R⁻¹, 이 때, R⁻¹ = {(y, x) | (x, y) ∈ R}.

(2) R이 반대칭적 ⇐⇒ R ∩ R⁻¹ ⊆ I_A.

(3) R 이 추이적 ⇐⇒ R ◦ R ⊆ R.

Definition 4.1.4 1. 관계 R이 반사적, 대칭적, 추이적일 때, R을 동치관 계(equivalence relation)이라 한다.

2. 관계 R이 반사적, 반대칭적, 추이적일 때, R을 순서관계(order rela- tion)이라 한다.

Example m이 주어진 양의 정수일 때, 정수집합

Z

Z

x − y = km ⇐⇒ x ≡ y(mod m)

로 정의된 것을 말한다. 이 합동은 정수집합

Z

Exercise 다음 정수집합

Z

1. R = {(x, y) | x + y < 3}

2. R = {(x, y) | x | y}

3. R = {(x, y) | x, y 서로소}

4. R = {(x, y) | x + y = 짝수}

5. R = {(x, y) | x = y ∨ x = −y}

6. R = {(x, y) | x + y = 짝수 ∧ x 는 y의 배수}

7. R = {(x, y) | y = x + 1}

4.2 동치관계와 분할

이 절에서는 동치관계에 관하여 공부하고 동치관계로부터 정의되는 집합의 분 할에 관하여 알아본다.

Definition 4.2.1 집합 X(X 6=

∅

P1. 모든 i, j ∈ I에 대하여, A_i ∩ A_j =

∅

P2. X = ∪

i∈I

A_i.

직관적으로 분할이란 집합 X를 서로 소인 부분집합들로 나누어 놓은 것으로 생각할 수 있다. 위의 정의에서 P1 조건은 두 집합 Ai와 Aj가 서로 소이거 나 같음을 나타낸다. 즉, 교집합이 공집합 이거나 교집합이 공집합이 아니라 면 두 집합은 같음을 나타낸다. 또한 Ai들은 X의 부분집합들 이므로 그 들 의 합집합도 부분집합이다. 이로부터 분할의 두 조건은 다음과 같이 다시 쓸 수 있다.

P1*. 만일 x ∈ Ai ∩ Aj 이면 Ai = Aj이다.

P2*. X ⊆ ∪

i∈I

A_i. 즉, x ∈ X =⇒ x ∈ Ai for some i ∈ I.

Example:

1. 임의의 정수 n에 대하여,

Bn = {m ∈

Z

Z

Z

2. 실수 집합

R

R

R

(1) 모든 실수 r에 대하여, Br = {(x, y) | y = x + r}

(2) 모든 실수 r에 대하여, B_r = {(x, y) | x² + y² = r}

이제 수학의 여러분야에서 매우 중요하게 사용되는 동치관계와 분할사이의 관 계를 알아본다.

R이 집합 A에서의 관계라고 하자. 즉, R ⊆ A × A이다. 특히 R이 동치관 계(반사, 대칭, 추이)일 때, (x, y) ∈ R라고 쓰는 대신 x ∼_R y 또는 간단히 x ∼ y라고 쓰기로 하고, “x와 y는 관계 R에 대하여 동치이다 라고 읽는다.

관계 R이 집합 A에서 동치관계 이므로 다음을 만족한다.

(1) 모든 x ∈ A에 대하여 x ∼ x (2) x ∼ y =⇒ y ∼ x

(3) x ∼ y 이고 y ∼ z 이면 x ∼ z이다.

Definition 4.2.2 관계 R이 집합 A에서의 동치관계라 하자. 집합 A의 원 소 x에 대하여 x의 동치류 Rx 는 다음과 같이 정의되는 집합이다.

Rx = {y ∈ A | (y, x) ∈ R} = {y ∈ A | y ∼ x}

즉, Rx는 x와 동치인 A의 모든 원소의 집합이다. Rx는 [x]로 쓰기도 한다.

Lemma 2 관계 R이 집합 A에서의 동치관계라 하자. 그러면 x ∼ y ⇐⇒ R_x = R_y

Proof. x ∼ y라 가정하자. 그러면

z ∈ Rx =⇒ z ∼ x =⇒ z ∼ y 가정 x ∼ y

=⇒ z ∈ Ry

따라서 Rx ⊆ Ry. 같은 방법으로 Ry ⊆ Rx이므로 Rx = Ry.

역으로 R_x = R_y라 하자. 그러면 반사율에 의하여 x ∼ x이다. 즉, x ∈ R_x. 그런데 Rx = Ry이므로 x ∈ Ry, 즉 x ∼ y이다.



Theorem 3 관계 R이 집합 A에서의 동치관계라 하자. {R_x}_x∈A는 A의 모든 원소에 대한 동치류의 모임이라고 할 때, {Rx}_x∈A는 집합 A의 분할이 된다.

위의 정리에서 집합 A의 분할 {Rx}_x∈A을 동치관계 R에 의한 분할이라 하고 A/R = {R_x}_x∈A로 나타내기도 한다.

Theorem 4 {A_i}_i∈I를 집합 A의 분할이라하자. 집합 A에서의 관계 R을 다음과 같이 정의하자.

R = {(x, y) | x ∈ A_i ∧ y ∈ A_i for some i ∈ I}

그러면 관계 R은 A에서 동치관계이다. 또한 분할 {A_i}_i∈I은 동치관계 R에 의한 분할이다. 즉, A/R = {Ai}_i∈I

Exercise 실수 집합

R

R

R

(1) 모든 실수 r에 대하여, Br = {(x, y) | y = x + y}

(2) 모든 실수 r에 대하여, B_r = {(x, y) | x² + y² = r}

4.3 동치관계와 함수

이 절에서는 하나의 함수로부터 정의되는 동치관계와 주어진 동치관계로부터 정의되는 함수에 관하여 공부한다.

f : X −→ Y 가 함수라 할 때, 집합 X위에서의 관계 R을 다음과 같이 정의 하자.

R = {(a, b) | f (a) = f (b)}

그러면 R은 집합 X위에서 동치관계이다. 이러한 관계를 함수 f 에 의하여 정의되는 동치관계라 한다.

Exercise 위의 관계 R이 동치관계임을 보여라.

역으로, 집합 X위에서 관계 R이 동치관계라 하면, 함수 f : X −→ X/R은 다음과 같이 정의된다. 모든 x ∈ X에 대하여,

f (x) = R_x

여기서 X/R = {R_x | x ∈ X} 이고 R_x = {y ∈ X | y ∼ x}이다. 이러한 함 수를 정준함수(canonical function)이라 한다.

Exercise f : X −→ X/R 가 함수의 조건을 만족함을 보여라. 즉, 함수 f : X −→ X/R는 잘 정의된다.

Theorem 5 관계 R이 집합 X 위에서의 동치관계라 하자. 만일 함수 f : X −→ X/R이 정준함수라하면, 관계 R은 함수 f 에 의하여 정의되는 동치관 계이다.

Proof. 함수 f : X −→ X/R이 정준함수라하고 G는 함수 f 에 의하여 정 의되는 동치관계라하자. 그러면 R = G임을 보이자.

(x, y) ∈ R ⇐⇒ R_x = R_y ⇐⇒ f (x) = f (y) ⇐⇒ (x, y) ∈ G



임의의 함수 f : X −→ Y 에 대하여, 관계 R을 함수 f 에 의하여 정의되는 동 치관계라하자. 함수 f 에 의하여 결정되는 3가지의 함수를 다음과 같이 정의 한다.

1. r : X −→ X/R은 정준함수이다.

2. s : X/R −→ f (A)는 모든 x ∈ X에 대하여, s(R_x) = f (x)로 정의 되 는 함수이다.

3. t : f (A) −→ B는 모든 y ∈ f (A)에 대하여 t(y) = y로 정의한다.

이 때, f (A) = {y ∈ Y | y = f (x)for some x ∈ X} 이고 t는 포함함수이 다.

Theorem 6 함수 f : X −→ Y 에 대하여, 관계 R을 함수 f 에 의하여 정의 되는 동치관계라하자. 함수 r, s, t는 위와 같이 정의 된다고 하자. 그러면, r은 전사함수, s는 전단사함수, t는 단사함수이고, f = t ◦ s ◦ r이 성립한다.

Proof.

1. Rx ∈ X/R이면, x ∈ X 이고 r(x) = Rx이므로 r은 전사함수이다.

2. f (x) ∈ f (A)이면, x ∈ X, R_x ∈ X/R이고 f (x) = s(R_x) 따라서 s는 전사함수이다.

3.

s(Rx) = s(Ry) =⇒ f (x) = f (y) =⇒ (x, y) ∈ R =⇒ Rx = Ry

이므로 s는 단사함수이다. 즉, s는 전단사함수이다.

4. t(y1) = t(y2) =⇒ y1 = y2이므로 t는 단사함수이다.

5. 모든 x ∈ X에 대하여

t(s(r(x))) = t(s(R_x)) = f (f (x)) = f (x) 이므로

[t ◦ s ◦ r](x) = f (x) =⇒ t ◦ s ◦ r = f



위의 정리에서 t ◦ s ◦ r을 f 의 정준합성이라고 부른다. 또한

Exercise f : X −→ Y 가 전사함수이면 X/R과 Y 는 일대일 대응관계가 있 다.