이상엽 집합론 정주행 3회차 - 관계와 분할

1. 관계

이 부분부터는 고등학교에서 배운 내용이 아니라서 집합론이라는 학문을 처음 접하는 사람이라면 처음 보는 개념일 것이다. 우선 필수적으로 알아야 하는 용어부터 살펴보자.

 

1) 용어 정리

① 관계: 곱집합 A × B의 부분집합

• R = (A, B, P(x, y))로 표기하며 P(x, y)는 명제함수이다.
• 이를 충족시킨다면 "A가 B에 관계한다, B가 A에 관계된다" 라고 이야기한다.

 

② 관계 R의 해집합 = { (x, y) | x ∈ A, y ∈ B, P(x, y)는 참 }

 

ex) A = { 2, 3 }, B = { 4, 6 }

• A × B = { (2, 4), (2, 6), (3, 4), (3, 6) }
• P(x, y) = "x는 y의 약수이다."
• R = (A, B, P(x, y)) → (2, 4) ∈ R
• 따라서 R = { (2, 4), (2, 6), (3, 6) }을 R의 해집합이라고 한다.

 

③ 정의역: 적당한 y ∈ B에 대하여 xRy인 모든 x ∈ A의 집합. Dom(R)로 표기

 

ex) ②의 예시처럼 R = { (2, 4), (2, 6), (3, 6) }이 있다면

• R의 순서쌍 중에 x성분은 각각 2, 2, 3이다.
• 따라서 Dom(R) = { 2, 3 }

 

④ 상: 적당한 x ∈ A에 대하여 xRy인 모든 y ∈ B의 집합. Im(R)로 표기

 

ex) ②의 예시처럼 R = { (2, 4), (2, 6), (3, 6) }이 있다면

• R의 순서쌍 중에 y성분은 각각 4, 6, 6이다.
• 따라서 Im(R) = { 4, 6 }

 

2) 관계의 성질

집합 X = { 1, 2, 3 }에서의 관계 R에 대하여

 

① 반사성: ∀x ∈ X, xRx

• R1 = { (1, 1), (2, 2) }이 있다면 반사성이 충족되지 않는다. (3, 3)이 없기 때문이다.
• R1 = { (1, 1), (2, 2), (3, 3), (1, 3) }이 있다면 반사성이 충족된다. x가 x에 관계하는 경우가 모두 존재하기 때문이다. (1, 3)은 반사성에 영향을 미치지 않는다.
• 여기서 { (1, 1), (2, 2), (3, 3) }처럼 반사성을 만족하는 최소한의 원소만 있다면 이 원소들을 △x로 표기하며 대각관계 혹은 항등관라고 한다.

 

② 대칭성: xRy => yRx

• R2 = { (1, 1), (1, 2), (2, 1) }이 있다면 대칭성이 충족된다. 모든 원소에 대해 xRy => yRx인 원소가 존재하기 때문이다.
• R2 = { (1, 1), (1, 2) }가 있다면 대칭성이 충족되지 않는다. (1, 2)에 대해 xRy => yRx인 원소가 없기 때문이다.

 

③ 반대칭성: xRy ∧ yRx => x = y

• 대칭의 반대로 서로 대칭되는 관계가 존재하면 그 둘은 반드시 같은 값이어야 한다는 뜻이다.
• R3 = { (1, 1), (1, 2), (2, 1) }은 반대칭이 아니다. (1, 2), (2, 1)은 x, y가 서로 다르지만 xRy ∧ yRx가 충족되기 때문이다.
• R3 = { (1, 1), (1, 2) }은 반대칭이다. xRy ∧ yRx를 충족하는 모든 원소들 중 x = y인 원소밖에 존재하지 않기 때문이다.

 

④ 추이성: xRy ∧ yRz => xRz

• R4 = { (1, 1), (1, 2), (2, 3) }이 있다면 추이성이 만족하지 않는다. 1R2, 2R3이 있다면 1R3도 있어야 한다.
• R4 = { (1, 1), (1, 2), (2, 3), (1, 3) }은 추이성을 만족한다.

 

3) 여러가지 관계

① 역관계 R^(-1)

xRy이면 오직 그 때에만 yR^(-1)x 즉, R^(-1) = { (y, x) | (x, y) ∈ R }

ex) R = { (1, 1), (1, 2) } → R^(-1) = { (1, 1), (2, 1) }

 

② 합성관계

집합 X에서의 관계 G와 H에 대하여 합성관 H · G = { (x, y) | ∃z, (x, z) ∈ G ∧ (z, y) ∈ H }

ex) ((1, 2) ∈ G ∧ (2, 3) ∈ H) → (1, 3) ∈ H · G

 

③ 역관계와 합성관계에 관한 정리

집합 X에서의 관계 F, G, H에 대해 다음이 모두 성립한다.

• (F^(-1))^(-1) = F
• (H · G) · F = H · (G · F)
• (G · F)^(-1) = F^(-1) · G^(-1)

 

④ 동치관계: 반사적, 대칭적, 추이적인 관계

사실 우리가 흔히 "같다"라고 표현하는 것들은 전부 위의 3가지를 만족한다. 아래의 링크에서 다뤘던 "같다"의 정의에서 동치관계를 언급한 적이 있는데 그것이 바로 지금 나오는 내용이다.

https://dafher-diary.tistory.com/35

이상엽 기초수학 정주행 1회차 - 수란 무엇인가?

예를 들어 X = { 1, 2, 3 }에 대해 R = { (1, 1), (2, 2), (3, 3) }이 있다면 동치관계이다. 아까 전에 언급한 대각관계 혹은 항등관계가 동치관계라는 것이다. 또한 X^2인 { (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3) }도 동치관계이다.

 

⑤ 순서관계: 반사적, 반대칭적, 추이적인 관계

ex) R = { (1, 1), (1, 2), (1, 3), (2, 2), (2, 1), (3, 1) }이 있을 때, 이것을 순서관계로 만들면 다음과 같다.

• 우선 반사성을 위해 (3, 3)을 투입한다.
• 이제 반대칭성을 위해 (1, 2), (2, 1) 중 하나를 지우고 (1, 3), (3, 1) 중 하나를 지운다.
• 여기서는 (2, 1)과 (3, 1)을 지우겠다.

 

결과적으로 R = { (1, 1), (1, 2), (1, 3), (2, 2), (3, 3) }이 된다. 순서관계는 다음에 더 자세히 다룰 것이라고 하며 이번 강의는 동치관계에 더 집중할 것이라고 한다.

 

 

2. 동치관계와 분할

분할이라는 처음 보는 개념이 등장했다. 아까 동치관계에 대해서 살펴볼 때, 3개의 원소를 가진 집합을 다뤘었다. 근데 만약 아주 많은 갯수의 원소를 가지는 집합으로 동치관계를 만들고 싶다면 어떻게 해야할까? 일일히 주먹구구식으로 원소 하나하나를 넣고 빼기에는 그 작업이 너무 번거롭다. 분할은 이 문제를 해결하는데 아주 유용한 개념일 뿐 아니라 그 자체로도 의미가 있다.

 

1) 용어 정리

① 분할: 집합 X에 대하여 다음 세 조건을 만족하는 집합족 → P = { A | A ⊂ X }

• 공집합을 원소로 하지 않는다. → ∀A ∈ P, A ≠ ∅
• X를 덮는다. → ∪P = X
• 서로소 집합족이다. → (∀A1, A2 ∈ P, A1 ∩ A2 = ∅) ∨ (A1 = A2)

 

어렵게 쓰기는 했는데 결국 아래의 예시와 같이 겹치는 부분없이 잘 자른 것을 분할이라고 하면 된다.

ex) X = { 1, 2, 3, 4, 5 } → P = { {1, 2}, {3, 4}, {5} }

 

② 동치류: 집합 X상의 하나의 동치관계를 E라고 할 때, Ex = { y ∈ X | xEy }

ex) X = { 1, 2, 3, 4, 5 }, E = { (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 3), (3, 1), (2, 4), (4, 2) }

여기서 E는 동치관계이다. 여기서 1~5까지에 대해 각 수가 왼쪽에 있을 때, 그것에 대응하는 오른쪽에 오는 수들을 집합으로 쓰면 그것이 동치류가 된다.

E1 = { 1, 3 } = E3 → 왼쪽에 1, 3이 오는 순서쌍들의 오른쪽에 있는 수

E2 = { 2, 4 } = E4 → 왼쪽에 2, 4가 오는 순서쌍들의 오른쪽에 있는 수

E5 = { 5 } → 왼쪽에 5가 오는 순서쌍들의 오른쪽에 있는 수

 

③ 상집합: 집합 X의 모든 동치류의 집합. 즉, X/E = { Ex | x ∈ X }

ex) 위의 X, E를 그대로 가져왔을 때, { 1, 3 }, { 2, 4 }, { 5 }로 나뉘는 것을 볼 수 있었다.

따라서 X/E = { {1, 3}, {2, 4}, {5} }가 될 수 있는 것이다.

 

여기서 주목할 점은 집합 X가 모두 분할되었다는 것이다. 즉, 동치관계를 알면 분할을 알 수 있다는 것이다. 이는 반대로 적용해서 분할을 알면 동치관계를 알 수 있다는 뜻이 된다.

 

④ Rp (= X/P) = { (x, y) | ∃A ∈ P, (x, y ∈ A) } → P는 분할을 의미한다. 즉, 분할 P의 의한 관계인 것이다.

 

ex) X = { 1, 2, 3, 4, 5 }, P = { {1, 2}, {3, 4}, {5} }, A1 = { 1, 2 }, A2 = { 3, 4 }, A3 = { 5 }

 

A1으로 만들 수 있는 순서쌍 (x, y) = { (1, 1), (1, 2), (2, 1), (2, 2) }

A2로 만들 수 있는 순서쌍 (x, y) = { (3, 3), (3, 4), (4, 3), (4, 4) }

A3로 만들 수 있는 순서쌍 (x, y) = { (5, 5) }

 

이를 모두 합하면 동치관계인 Rp가 나오게 된다. 이로써 분할을 이용해서 동치관계를 이끌어냈다.

 

2) 여러가지 정리

① 공집합이 아닌 집합 X위의 동치관계 E에 대하여 다음이 모두 성립한다.

• Ex ≠ ∅
• Ex = Ey ↔ xEy
• Ex ∩ Ey ≠ ∅ ↔ xEy
• X/E는 X의 분할이다.

 

② 공집합이 아닌 집합 X위의 분할 P에 대하여 다음이 모두 성립한다.

• Rp는 X상의 동치관계다.
• X/Rp = P