관계 (등치관계의 분할, 부분순서 관계)
정의 5-11. 관계 R에서 반사관계, 대칭관계, 추이관계가 모두 성립할 때 이를 동치관계라고 한다. 동치관계 R의 중요한 성질로는 R이 서로 공통부분이 없으면서 공집합이 아닌 클래스들로 S를 분할한다는 점이다.
예제 5-27. 집합 A = {1,2,3,4} 이고 A에 대한 관계가 다음과 같을 때, R이 동치관계임을 보아라.
R = {(1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4)}
1) 반사? -> O
2) 대칭? -> O
3) 추이? -> O
-> R은 동치관계가 맞다.
정의 5-13. 공집합이 아닌 집합 A와 분할이란 다음 조건을 만족시키는 A의 부분집합의 모임 {A₁, A₂,... An}을 말한다.
(1) Ai != ∅, 1<=i<=n (공집합인 부분은 없다)
(2) A = A₁∪ A₂∪... An (모든 부분을 다 더하면 전체가 된다)
(3) Ai ∩ Aj = ∅, i != j (서로 교집합이 없다)
예제 5-28. A = {1,2,3,4,5}이고 A의 부분집합이 A₁= {1}, A₂ = {2,3,5}, A₃ = {4}일때 이들이 집합 A의 분할이 되는지를 밝혀보라
1) 공집합이 없을 것 - T
2) 교집합이 없을 것 - T
3) 합집합이 전체일 것 - T
-> 그러므로 분할이 맞다
예제 5-29. S = {1,2,3,4,5,6}의 부분집합이 다음과 같을 때 집합 S를 분할하는지를 판단해보자.
(1) {(1,2,3), (3,4,5), (6)}
-> 분할이 아니다. 교집합이 존재하므로
(2) {(1,2), (3,4,6), (5)}
-> 교집합이 없고, 공집합인 부분이 없고, 합집합이 전체이다 (분할이 맞다)
예제 5-31. 양의 정수m에 대해 mod항등의 관계(m으로 나눴을 때 나머지가 같은(항등) 경우), 즉 a∈b(mod m)인 경우를 살펴보자. 만약 m이 3인 경우에 동치관계가 되는지를 밝히고, 동치류를 만들어보자.
[0] = {0,3,6,...,3n}
[1] = {1,4,7,...3n+1}
[2] = {2,5,8,...3n+2}
정의 5-14. 집합 A에 대한 관계 R이 반사관계, 반대칭관계, 추이관계이면 관계 R을 부분순서관계라 한다. 또한 R이 A에 대한 부분순서 관계이면 순서쌍 (A, R)을 부분순서집합이라고 한다.
- 부분이라는 용어를 쓰는 이유는 집합 A의 원소의 모든 쌍이 관계를 가지는 것은 아니기 때문임
- 부분순서집합을 나타낼 때 (A, ~<) 라는 기호를 사용함
- 집합 A에 대한 관계 R이 부분순서 관계이면, A의 두 원소 x,y에 대하여 {x,y}∈R을 x<=y로 표기함
- x<=y의 관계인 경우 'x가 y를 선행한다'라고 읽음
정리 5-2. 집합 A에서의 관계 R ⊂= A * A는 다음과 같은 성질을 가질 수 있다.
(1) 반사관계 : 모든 x∈A에 대해 xRx이다.
(2) 반대칭관계 : 모든 x,y∈A에 대해 xRy이고 yRx이면 x=y이다.
(3) 추이관계 : 모든 x,y ∈ A에 대해 xRy이고 yRz이면 xRz이다.
위의 세가지 관계를 모두 만족시키는 관계를 부분순서 관계라 한다.
예제 5-32. 자연수의 집합(N)에 대한 관계 <=이 부분순서 관계임을 보이자.
1) = 있으니 반사 O
2) 반대칭 O (같을땐 대칭, 다를땐 대칭 X)
3) 추이 O (3<=5, 5<=7, 3<=7)
∴ 부분순서관계에 해당한다.
예제 5-33. 집합 S의 부분집합 간의 포함관계 ⊂=이 부분순서관계임을 보이자.
예) 1 ⊂= {1,2} ⊂= {1,2,3}
1) A ⊂= A (반사 O)
2) A ⊂= B이고 B ⊂= A이면 A = B이므로 반대칭관계 O
3) A ⊂= B, B ⊂= C, A ⊂= C (추이관계 성립 O)
∴ 부분순서관계에 해당한다.
