알고리즘 수학 기본-관계

Jul 10, 2021

1. 관계(Relations)
   • 이항 관계(binary relation)
   • 이항관계의 성질
   • 동치 관계에 관한 기본적인 정리 하나 (A basic theorem of equivalence classes)
   • 반대칭 관계

알고리즘을 위한 수학 - 관계(Relations)

Introduction to Algorithm, 3rd, Cormen을 토대로 정리한 내용입니다.

일부 표기나 개념이 기존의 수학과 다를 수도 있으므로, 여기서 배운 내용은 단순 해당 책(Introduction to Algorithm, 3rd, Cormen)의 부록으로 취급해야한다.

이 장에서는 관계의 표기법, 정의, 속성 같은 기본적인 것만 배운다.

관계(Relations)

이항 관계(binary relation)

두 집합 A와 B에 대한 이항 관계 R은 곱집합(Cartesian product) $A\times B$의 부분집합이며, 만약 순서쌍 $(a, b)\in R$일 경우 이러한 관계를 $a\ R\ b$로 표현한다.

즉 $a\ R\ b$는 “a와 b의 관계가 성립 가능”을 의미한다.

만약 R이 집합 A의 이항 관계라면 R은 $A \times A$의 부분집합, 즉 집합 A의 원소들끼리의 관계가 성립된다라는 의미이다.

이외의 예시로, 자연수에서의 미만 관계(“less than” relations)는 집합 ${(a,b):a,b \in \N\ and\ a<b}$를 의미하며, 집합족 $A_1, A_2,\cdots,A_n$에 대한 n항 관계(n-ary relations)는 $A_1\times A_2\times \cdots \times A_n$의 부분집합을 의미한다.

이항관계의 성질

반사관계(Reflexive relations)

이항관계 $R\subseteq A\times A$는 모든 원소 $a\in A$에 대하여 $a\ R\ a$가 성립될 경우, R은 반사(reflexive) 관계라 한다.

예를 들어 관계 “=”와 “$\leq$”은 자연수 집합 $\N$에 대하여 반사관계이지만 “$<$”은 아니다.(0~무한까지 자기자신보다 같거나 작거나 같은 수들 뿐이지만, 자기자신보다 작은 수는 없으니까.)

대칭관계(Symmetric relations)

어떤 집합 A의 원소 $a,b\in A$인 순서쌍 (a, b)와 (b, a)가 관계 R에 속할때, 즉 $a\ R\ b$성립되면서 동시에 $b\ R\ a$ 성립될 때, R을 대칭관계(Symmetric relations)라고 부른다.

예를 들면 “=”는 대칭관계 이지만 “<”나, “$\leq$”는 아니다.

추이관계(transitive relations)

만약, $a,b,c\in A$일 때, $a\ R\ b$, $b\ R\ c$ 그리고 $a\ R\ c$를 만족할 때, 추이관계(transitive relations)라고 한다.

예를 들면, “<”, “$\leq$”, “=”는 추이 관계이지만, 관계 $R={(a,b):a,b\in \N\ and\ a=b-1}$은 예를 들어 $3\ R\ 4$이며, $4\ R\ 5$이지만 $3\ R\ 5$는 성립되지 않으므로 아니다.

위에 설명한 세 관계를 모두 만족하는 관계를 동치관계(equivalence relation)이라고 부르는데, 대표적으로 “=”는 동치 관계이다.

집합 A에 포함된 원소 a의 동치류(equivalence class)는 $[a]={b\in A: a\ R\ b}$로 표현하며, 동치류 내의 원소들은 모두 a에 대하여 동치관계이다.

해당 동치류는 앞서 언급했듯이 대칭관계를 만족하므로, 동치류는 [a] 뿐만 아니라 같은 동치류 내의 다른 원소들 x들의 동치류 [x] 이기도 하다.

예를 들어, $R={(a,b):a,b \in \N\ and\ a+b는\ 짝수}$에서

a+a는 짝수이면 반사관계

a+b가 짝수이고, b+a가 짝수이면 대칭 관계

a+b가 짝수이고, b+c도 짝수인 뒤, a+c도 짝수이면 추이관계가 성립되고,

관계 R에 대한 4의 동치류는 $[4]={0,2,4,6,\cdots}$, 3의 동치류는 $[3]={1,3,5,7,\cdots}$이다.

동치 관계에 관한 기본적인 정리 하나 (A basic theorem of equivalence classes)

동치 관계에 관한 정리 하나는 다음과 같다.

Theorem B1. “동치관계는 우리가 Set에서 배웠던 분할(partition)과 동일하다.”

즉, 모든 동치 관계 R에 대한 집합 A의 원소들의 동치류들의 집합들은 A의 분할(partition)이며, A의 모든 분할들은 어떤 동치 관계에 대한 동치류들의 집합이다.

사실 직관적으로 예시를 들어보자면, 어떤 회사에서 사원들 집합 A를 부서별로 나눈 표를 분할로 볼 수 있고, 동치관계 R은 “사원 a는 사원 b와 같은 부서 소속이다.”로 집합 A를 나눈 표로 볼 수 있으므로, 동일하다는 것을 알 수 있지만 아래에 수학적 증명이 나와있다.

증명

R의 동치류 집합은 공집합이 아니며 합집합은 집합 A이며, 서로소 집합이다.

먼저 첫번째로, R에 대한 동치류 집합은 비어있지 않고, 모두의 합집합은 집합 A가 되며, 서로간에 서로소인 집합들이다. 왜냐하면

1. R은 반사관계의 특성을 가지고 있으므로, $a \in [a]$이며, 따라서 최소한 하나의 원소(자기 자신)을 가지고 있으며 (동치류는 비어있지 않음)

2. 따라서 A의 모든 원소들은 최소한 자기 자신이 포함된 동치류를 가지므로 이 동치류들을 모두 합하면 집합 A가 되며, (합집합이 집합 A)

3. 만약 서로 다른 두 원소 a, b의 동치류 [a], [b]가 공통된 원소 c를 가진다면, 아래에 설명할 증명에 의해 [a] = [b]라는 것이 되는데, 이는 앞선 가정인 동치류 집합이라는 것에 위배된다.(집합은 중복된 원소를 가지지 않는다.)

   즉, a와 b는 공통된 원소 c를 가지지 않는다.(동치류들은 모두 서로 서로소)

3번을 좀더 자세하게 알아보자면, 만약 동치류 [a]와 [b]가 공통된 원소 c를 가진다면, $a\ R\ c$이면서, $b\ R\ c$라는 의미인데, 대칭관계에 의해 $b\ R\ c$는 곧 $c\ R\ b$이며, 추이관계에 의해 $a\ R\ b$가 성립되며, 반대로 $b\ R\ a$가 성립된다.

여기서 c를 동치류 [a]의 모든 원소들 중 하나 x를 대입을 하여도 $a\ R\ x$는 곧 $x\ R\ a$이고, 위에서 설명했던 것 처럼 $a\ R\ b$이므로 추이관계에 의해 $x\ R\ b$가 성립된다.

이는, 반대로 동치류 [b]의 원소 중 하나 y로 하여도 마찬가지이다. 즉 [a]와 [b]는 모든 원소를 서로간에 공유하게 되고 $[a] \subseteq [b]$이자 $[b] \subseteq [a]$가 되며 이는 곧 $[a]=[b]$이므로, a와 b는 공통된 원소 c를 가지지 않는 서로소라는 점이 증명된다.

동치관계 정의

그다음 두번째로, 집합 A의 분할을 $P_A$로 놓고, 분할들의 원소, 즉 서로소인 A의 부분집합들을 $A_i$라 놓자.

집합 A에 대한 관계 R을 $R={(a,b):a와\ b가\ 전부\ 포함된\ 집합인\ A_i가\ 존재함}$로 정의하자.

• 앞서 설명한 “a와 b는 같은 부서 소속이다.”의 수학적인 표현과 다를 바 없다.

우리가 정의한 R은 A에 대해 동치관계인데,

먼저, a와 b가 전부 포함된 집합 $A_i$에는 당연히 a가 들어가 있으므로 $a\ R\ a$가 성립되어 반사관계가 성립되며

a와 b가 전부 포함된 집합 $A_i$($a\ R\ b$)는 b와 a가 전부 포함된 집합과 마찬가지이므로 $b\ R\ a$ 또한 성립하므로 대칭관계이며,

마지막으로, 집합 A의 분할의 원소들은 각각 집합 A의 원소들을 중복해서 포함하지 않으므로, $a\ R\ b$를 증명하는 $A_i$는 $b\ R\ c$인 $A_i$와 같은 원소가 같지 않으면 원소 b가 중복됬다는 의미이므로, a, b, c는 같은 집합 내에 존재한다는 의미이며, 따라서 추이관계 또한 만족한다.

1. $A_i$에 속한 원소 a의 동치류 [a]에 $x \in [a]$를 만족하는 원소 x들은 모두 $A_i$에 속한다.

동치류는 위의 관계 R에 a와 동치관계를 형성해야하는데, 동치류 [a]의 어떤 원소 x가 a와 같은 분할내 집합원소 $A_i$에 속하지 않다면, $a\ R\ x$가 성립하지 않으므로, 동치류에 속할 수 없기 때문이다.

1. 반대로 $A_i$의 모든 원소 y가 [a]에 속한다.

$A_i$의 모든 원소는 관계 R을 만족시므로 $a\ R\ y$가 성립되며, 동치관계이므로 [a]에 속할 수 있다.

$A_i$의 모든 원소와 [a]의 모든 원소가 서로 속하므로 ($A_i \subseteq [a], [a] \subseteq A_i$) A의 분할은 곧 R의 동치류들의 집합이다.

반대칭 관계

이항 관계 R에서 $a\ R\ b$와 $b\ R\ a$일 때, a=b인 관계를 반대칭(antisymmetric) 관계라고 하는데,

이는 $a\ R\ b$일 때, $b\ R\ a$는 성립하지 않는 비대칭 관계(asymmetric) 관계와는 다른 의미이며, 비대칭 관계는 대칭관계의 정반대의 의미이지만, 반대칭 관계는 서로 양립 가능하다.

예를 들어 R이 두 원소는 같다 (“=”)일 경우, 반대칭 관계이면서, 대칭관계일 수 있다.

하지만 R이 두 원소는 작거나 같다 (“$\leq$”)일 경우, 반대칭 관계이지만 대칭관계는 아닌데, $a=b$인 경우에만 $ a\ R\ b$, $b\ R\ a$이기 때문이다.

이때, 반사관계, 반대칭관계, 추이관계를 만족하는 관계를 부분순서 (Partial Order) 관계라고 하며, 부분순서 관계가 정의된 집합을 부분 순서 집합(partially ordered set)이라고 한다. 대표적으로 위에서 예시를 들었던 “$\leq$”가 있다.

부분 순서 집합에서는 집합 A의 모든 원소 b에 대해 $b\ R\ a$를 모두 만족하는 최대값 원소 a가 존재하지 않지만, 집합 A의 모든 원소 b에 대해 $a\ R\ b$를 만족하는 경우가 존재하지 않는 원소 a는 여럿 존재할 수 있다.

예시를 들자면, 박스들의 집합에서 다른 모든 박스들을 수용할 수 있는 가장 큰 박스는 존재하지 않지만, 다른 모든 박스에 들어가지 않는 박스는 존재할 수 있다.

집합 A의 모든 원소 쌍들이 관계 R을 만족할 때, 이를 완전관계(total)라고하며, 완전관계인 부분 순서 집합을 완전 순서(total order) 또는 선형 순서(linear order)라고 한다.

예를 들어 자연수 집합의 $\leq$ 관계는 완전 순서이지만, 모든 인간에 대한 가계도의 경우는 완전 순서가 아니다. 생판 모르는 남끼리는 후손도, 자식으로도 인정받지 못하기 때문에 아무런 관계가 아니기 때문이다.(물론 엄밀히 이상적인 유전검사와 고고학, 인류학적 이상을 고려하면 모든 인간은 한 핏줄이겠지만, 현실적인 이야기를 가정한다.)

이중에, 완전 관계이면서, 추이관계를 만족하지만, 반사관계와 반대칭 관계는 만족하지 않는 완전관계를 완전 전위순서(total preorder)라고 한다.