4.1 
–

4.1 기본개념 및 정의

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.

Proof. (1) R이 대칭적이라하자. 그러면

(x, y) ∈ R ⇐⇒ (y, x) ∈ R ⇐⇒ (x, y) ∈ R⁻¹ 따라서 R = R⁻¹. 역으로, R = R⁻¹ ,이라하자. 그러면

(x, y) ∈ R ⇐⇒ (x, y) ∈ R⁻¹ ⇐⇒ (y, x) ∈ R

(2) R이 반대칭적이라하자. 그러면

(x, y) ∈ R ∩ R⁻¹ =⇒ (x, y) ∈ R and (x, y) ∈ R⁻¹

=⇒ (x, y) ∈ R and (y, x) ∈ R

=⇒ x = y

=⇒ (x, y) = (x, x) ∈ I_A 역으로, R ∩ R⁻¹ ⊆ I_A라 하자. 그러면

(x, y) ∈ R and (y, x) ∈ R =⇒ (x, y) ∈ R and (x, y) ∈ R⁻¹

=⇒ (x, y) ∈ R ∩ R⁻¹ ⊆ I_A

=⇒ x = y

(3) R 이 추이적이라하자. 그러면

(x, y) ∈ R ◦ R =⇒ for some z, (x, z) ∈ R and (z, y) ∈ R

=⇒ (x, y) ∈ R

따라서 R ◦ R ⊆ R. 역으로, R ◦ R ⊆ R라 하자. 그러면

(x, y) ∈ R and (y, z) ∈ R =⇒ (x, z) ∈ R ◦ R ⊆ R

Example m이 주어진 양의 정수일 때, 정수집합 Z 위에서의 법 m에 관 한 합동관계(또는 합동 ≡)이란 것은 적당한 k ∈ Z에 대하여

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

로 정의된것을 말한다. 이 합동은 정수집합 Z 위에서의 동치관계이다.

Proof. (1) x ∈ Z에 대하여 x − x = 0 · m이므로 x ≡ x (mod m).

(2) x ≡ y (mod m) 이면 적당한 k ∈ Z에 대하여

x − y = km =⇒ y − x = (−k)m, −k ∈ Z 따라서 y ≡ x (mod m)

(3) x ≡ y (mod m), y ≡ z (mod m) 이면 적당한 k₁, k₂ ∈ Z에 대하여 x − y = k m, y − z = k m

Exercise 다음 정수집합 Z 위에서의 관계에 대하여 반사율, 대칭율, 반 대칭율, 추이율을 말하여라. 또한 동치관계, 순서관계인지 아닌지 를 결정하 여라.

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

Solution. 반사율, 2. R = {(x, y) | x | y}

Solution. 반사율, 반대칭율, 추이율 3. R = {(x, y) | x, y 서로소}

Solution. 대칭율,

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

Solution. 반사율, 대칭율, 추이율 5. R = {(x, y) | x = y ∨ x = −y}

Solution. 반사율, 대칭율, 추이율

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

Solution. 반사율, 반대칭율, 7. R = {(x, y) | y = x + 1} Solution.

4.2 동치관계와 분할

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

Proof. 정의에 의하여 각 집합 R_x는 A의 부분집합이다. x ∼ x이므로 x ∈ Rx, 즉 Rx는공집합이 아니다. 분할의 두 조건을 체크하자.

z ∈ R_x∩ R_y =⇒ z ∈ R_x and z ∈ R_y

=⇒ z ∼ x and z ∼ y

=⇒ x ∼ z and z ∼ y

=⇒ R_x = R_y

따라서 P1*를 만족한다. 만일 x ∈ A이면, 반사율에 의하여 x ∼ x이 고 x ∈ R_x이므로 P2*도 만족한다. 따라서 {R_x}_x∈A는 집합 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 = {A_i}_i∈I.

Proof. 동치관계의 세 조건을 확인하자.

(3) R is transitive:

(x, y) ∈ R and (y, z) ∈ R =⇒ x ∈ A_i and y ∈ A_i and y ∈ A_j and z ∈ A_j

=⇒ y ∈ A_i∩ A_j =⇒ A_i = A_j

=⇒ x ∈ A_i and z ∈ A_i

=⇒ (x, z) ∈ R

이제각 A_i는 동치관계 R에 의한 분할임을 보이자. x ∈ A_i라 하면 y ∈ A_i ⇐⇒ (y, x) ∈ R ⇐⇒ y ∈ R_x

따라서 A_i = R_x.