[CM201] 05. 관계(Relation)

관계 (Relation)

 이전 절에서 셀 수 있는 집합을 설명하기 위해 간단하게 함수에 대해 설명했습니다. 사실 설명은 그 정도로도 충분해요. 이번에는 함수 이야기가 나온 김에 함수와 비슷하지만, 조금 더 일반적인 개념에 대해 다뤄보려고 합니다.

 관계(Relation)는 두 집합 $A$, $B$에 대하여 $A$의 원소와 $B$의 원소가 짝지어진 순서가 있는 쌍들의 집합입니다. 정의가 함수와 비슷하죠? 함수가 바로 관계의 특별한 경우이기 때문입니다. 때문에 관계 또한 함수와 마찬가지로 두 집합의 카르티시안 곱의 부분집합으로 볼 수 있습니다. 원소 a와 b의 관계는 $a \; R \; b$라고 표기하며, ‘$a$는 $b$와 관계되어 있다’라고 합니다.
 만약 두 집합 $A$, $B$의 원소들을 모두 점으로 표현한다면 $A$와 $B$의 관계들을 그래프로 나타낼 수도 있습니다.

특별한 관계들

  관계의 특징을 나타내는 몇 가지 요소들도 있습니다.

• 반사적(Reflexive) : 자기 자신과 관계를 가집니다.
• 대칭적(Symmetric) : 관계에 속하는 순서쌍에서 두 요소의 위치를 바꾸어도 그 관계에 포함됩니다.
• 반대칭적(Antisymmetric) : 위의 조건을 만족하지 않습니다.
• 추이적(Transitive) : 만약 (a,b)와 (b,c)가 모두 관계에 속해 있으면, (a,c)도 관계에 포함됩니다.

  또한 함수를 포함하는 개념인 만큼, 역함수와 합성함수에 해당하는 역관계(Inverse)와 합성관계(Composition)도 존재합니다.

행렬을 이용해 나타내는 관계

이 부분은 행렬 곱셉 연산을 다룹니다. 행렬과 행렬연산에 대해 모른다면 이해가 어려울 수 있습니다!

 혹은 행과 열에 두 집합의 원소들을 나열해서 행렬로 나타낼 수도 있습니다. 각 칸마다 순서쌍이 관계에 속한다면 1, 아니라면 0으로 채우면 됩니다. 이렇게 하면 단순한 집합의 나열이나 그래프를 보는 것 보다 더 쉽게 관계의 특징을 알아낼 수 있답니다.

 가령, 행령의 대각성분이 모두 1인지 확인하면 이 관계가 반사적(Relflextive)인지 쉽게 알 수 있습니다. 그리고 이 대각선을 기준으로 양 옆이 대칭이라면 관계도 대칭적(Symmetric)이게 됩니다.

 관계가 추이적(Transitive)인지는 합성관계를 이용하면 됩니다. 두 관계 $R_1$, $R_2$를 나타낸 행렬 $A_1$, $A_2$가 있을 때, 두 관계를 합성한 행렬은 행렬 곱 $A_1A_2$로 나타낼 수 있습니다(이 때, 0이 아닌 수는 전부 1로 나타냅니다).

 이를 이용해 관계 $R$을 나타낸 행렬을 $A$라고 할 때, $A$를 한 번 더 곱한 행렬 $A^2$는 자기 자신을 두 번 합성한 관계가 됩니다. 원소 (a, b), (b, c)가 있다면 (a, c)가 나오게 되는 것이죠. 그러므로 $A^2$에 있는 모든 1 원소가 원본 $A$에도 있다면, 관계가 추이적이다고 말할 수 있습니다.

폐포 (Closure)

 여러분이 어떤 관계 하나를 들고 있다고 해봅시다. 그리고 여러분은 이 관계가 여러가지 성질을 가지고 있기를 바라고 있고요.

 하지만 애석하게도 이 관계는 갖가지 성질을 만족시키기에는 너무나도 작습니다. 새로운 성질을 만족시키려면 아무래도 관계에 새로운 요소들을 더 추가할 필요가 있겠죠.

 관계가 어떤 성질을 가지기 위해 최소한의 조건을 갖춘 형태를 그 관계의 폐포(Closure)라고 합니다. 이렇게만 말하면 조금 두리뭉실 하니까, 집합 $A$의 어떤 관계 $R$이 앞서 언급한 관계의 세 가지 성질(반사성, 대칭성, 추이성)을 만족하기 바란다고 가정해봅시다.

반사성 폐포

 반사성은 자기 자신의 순서쌍이 존재해야 합니다. 그러므로

\[\Delta = \{(n, n) \; | \; \text{(n는 A가 가지는 모든 원소)}\}\]

 순서쌍들을 추가해야 할겁니다. 따라서 반사성 폐포(Reflextive closure)는 $R \cup \Delta$가 됩니다.

대칭성 폐포

 대칭성은 각 순서쌍을 뒤집은 순서쌍도 있어야겠죠. 간단히 원래 관계 R을 뒤집으면 됩니다. 이렇게요.

\[R^{-1} = \{(b, a) \; | \; (a, b) \in R\}\]

 그러므로 대칭성 폐포(Symmetric closure)는 $R \cup R^{-1}$가 됩니다.

추이적 폐포

 추이성은 조금 까다롭습니다. 관계마다 생긴게 조금씩 다르니까요. 그러니 우리는 경로라는 개념을 사용해야 합니다.

Theorem 1.
집합 $A$의 관계 $R$에 대하여, $A$의 원소 $a$에서 $b$까지의 경로의 길이는 $(a, b) \in R^n$ (n번 거듭제곱)이 되었을 때 n의 최솟값이다.

 이를 토대로 새로운 정의를 내릴 수 있습니다.

Definition.
집합 $A$의 관계 $R$에 대하여, 연결관계(Connectivity relation) $R^{\star}$는 모든 순서쌍 $(a, b)$가 최소 1 이상의 경로 길이를 가지는 관계로, 다음과 같이 표기한다.
\(\begin{align} R^{\star} = \bigcup_{n=1}^{\infty}R^n \end{align}\)

 눈치 채셨겠지만, 이 $R^{\star}$가 바로 추이성 폐포(transitive closure)입니다.

순서가 없는 관계

 관계가 대칭성을 가진다면 그래프는 방향성이 사라집니다. 순서가 사라지게 되는 것이죠. 이를 동치관계(Equivalence relation)이라고 합니다. 대표적인 예로는 약분했을 때 동일한 기약분수를 가지는 유리수가 있겠네요.

순서가 있는 관계

 하지만 관계가 비대칭성을 가지게 되면 그림이 변합니다.

 일종의 방향성이 느껴지지 않나요? 방향성이 있다면 방향대로 순서가 있을테고, 순서가 있다면 원소들을 서로 비교할 수도 있을 것입니다. 그래서 만약 한 집합 안의 두 원소가 관계에 있다면 그 두 원소는 서로 비교가능하다(Comparable)고 합니다. 관계에 없다면 비교불가능하다(incomparable)고 하고요.

부분순서 (Partial Order)

 만약 모든 순서쌍들이 관계에 있어 그 순서를 비교할 수 있다면, 그 관계는 전순서(Total order)에 있다고 합니다. 다른 말로 선형 정렬(Linear order) 또는 사슬(Chain)이라고도 합니다.

 하지만 모든 순서쌍이 관계에 있는 경우는 흔하지 않습니다. 이 중에서 몇몇 순서쌍이 빠지게 될 수도 있죠. 만약 여기서 몇 가지 조건을 만족한다면, 그 관계는 부분순서(Partial order)에 있다라고 말할 수 있습니다.

• 조건 1. 반사적일 것 (reflextive)
• 조건 2. 대칭적이지 않을 것 (antisymmetric)
• 조건 3. 추이적일 것 (transitive)

 부분집합의 대표적인 예시로는 부분 집합 관계가 있습니다. 1. {ㄱ}과 {ㄱ}은 서로 같은 순서이고 2. {ㄱ}은 {ㄱ, ㄴ}에 속하나 그 반대는 불가능하며 3. {ㄱ, ㄴ}이 {ㄱ, ㄴ, ㄷ}의 부분집합이니 {ㄱ}도 {ㄱ, ㄴ, ㄷ}의 부분집합이 되니까요.

 만약 부분순서 관계를 가지는 집합에서 모든 순서쌍이 공통된 최소 상한선과 최대 하한선을 가진다면 그 집합을 격자(Lattice)라고 합니다.

사전식 순서 (Lexicographic Order)

 단어의 순서를 세우는 것을 사전식 순서(Lexicographic Order)라고 하고, 기호로는 $\preceq$으로 표기할 수도 있습니다.(일반 부등호와는 달리, 일반적인 순서 관계를 뜻합니다).
 사전순의 대소관계는 크게 두 가지 경우로 나뉘어 정의됩니다. 부분순서 관계 $R$에 있는 집합 $X$에서 문자를 뽑아 두 단어 $A = a_1a_2…a_m, \; B = b_1b_2…b_n$가 있을 때, 아래 두 경우를 만족하면 $A \preceq B$가 성립합니다.

1. $m \leq n$ 이고 m 번째 까지 A와 B가 동일하다면

2. 적당한 수 $k$에 대해 k-1 번째 까지 A와 B가 동일하고, k번째 두 문자가 $a_k \; R \; b_k$라면

잘-정렬된 집합 (Well-ordered set)

 이제 순서 관계에 좀 더 복잡한 조건을 추가해봅시다. 집합 $A$와 관계 $\preceq$에 대하여,

1. $\preceq$는 전순서(total order)관계이어야 한다. 즉, $A$에서 어떤 수 둘을 가져와도 대소비교를 할 수 있어야 한다.

2. $A$의 모든 부분집합은 반드시 최솟값을 가져야 한다. 무한집합이어도 최솟값이 존재하기만 하면 된다.

 이 두 조건을 만족한다면, 우리는 $(A, \preceq)$를 잘 정렬된 집합(Well-ordered set)이라고 부를 수 있습니다.

 우리는 이때까지 논리와 증명을 통해 생각을 어떻게 서술하는지 다루었고, 집합과 관계를 통해 서술한 요소들을 어떻게 모으고 연결하는지 익혔습니다. 아직까지는 ‘이걸 어디 쓰나?’ 싶은 정도이긴 합니다. 하지만 앞으로 온갖 개념들을 만나게 될 텐데, 그 재료를 미리 맛만 본 것이라고 해두면 되겠습니다.