관계의 표현과 성질

"팔로우한다", "같은 반이다", "먼저 끝내야 한다"는 모두 대상 사이의 관계이지만 성질이 다릅니다. 같은 반이라는 관계는 내가 너와 같은 반이면 너도 나와 같은 반이지만, 팔로우는 내가 너를 팔로우해도 네가 나를 팔로우하지 않을 수 있습니다. 이런 차이를 정확하게 다루려면 관계를 수학의 대상으로 정의해야 합니다. 이 글에서는 곱집합을 바탕으로 관계를 정의하고, 관계가 가질 수 있는 네 가지 성질을 검사하는 방법을 익힙니다.

관계는 순서쌍의 집합이다

집합 A의 원소와 집합 B의 원소 사이의 이항관계(binary relation) R은 곱집합 $A\times B$의 부분집합입니다. 관계가 있는 원소 쌍 $(a,b)$만 골라 모은 것이라는 뜻입니다. $(a,b)\in R$을 짧게 $aRb$로 쓰고 "a는 b와 R 관계에 있다"라고 읽습니다. 같은 집합 A의 원소들 사이의 관계는 $A\times A$의 부분집합이고, 이것을 A 위의 관계라고 합니다.

$A=\{1,2,3\}$ 위의 관계 $R=\{(1,1),(1,2),(2,3)\}$을 보겠습니다. 1은 1과 2에 관계가 있고, 2는 3에 관계가 있습니다. $(1,2)$는 있지만 $(2,1)$은 없으므로, 관계는 방향이 있고 순서쌍의 앞뒤를 바꾸어 읽으면 안 됩니다.

관계는 두 가지 그림으로도 나타냅니다. 원소에 순서를 정해 두고, i번째 원소가 j번째 원소와 관계가 있으면 i행 j열에 1을, 없으면 0을 적은 표를 관계 행렬(relation matrix)이라고 합니다. 원소마다 점을 찍고 순서쌍 $(a,b)$마다 a에서 b로 화살표를 그린 것은 방향 그래프입니다. $(1,1)$처럼 자기 자신과의 관계는 자기에게 돌아오는 고리로 그립니다. 관계 행렬은 인접 행렬과 같은 것이고, 방향 그래프는 8장에서 그래프로 자세히 다룹니다.

네 가지 성질

A 위의 관계 R이 가질 수 있는 대표적인 성질은 네 가지입니다.

정의가 모두 "모든" 원소나 "모든" 쌍에 대한 조건이므로, 성질이 없다는 것은 조건을 어기는 예 하나로 보일 수 있습니다. 앞의 R을 정의대로 검사해 보겠습니다.

def properties(A, R):
    reflexive = all((a, a) in R for a in A)
    symmetric = all((b, a) in R for a, b in R)
    antisymmetric = all(a == b for a, b in R if (b, a) in R)
    transitive = all((a, d) in R for a, b in R for c, d in R if b == c)
    return reflexive, symmetric, antisymmetric, transitive


A = [1, 2, 3]
R = {(1, 1), (1, 2), (2, 3)}
print(properties(A, R))
print([[1 if (a, b) in R else 0 for b in A] for a in A])

(False, False, True, False)
[[1, 1, 0], [0, 0, 1], [0, 0, 0]]

네 줄의 조건은 표의 정의를 그대로 옮긴 것입니다. 추이성은 R의 두 쌍 $(a,b)$와 $(c,d)$를 모두 짝지어, 이어지는 경우($b=c$)마다 $(a,d)$가 있는지 봅니다. 결과를 읽으면, $(2,2)$와 $(3,3)$이 없어 반사적이지 않고, $(1,2)$의 반대인 $(2,1)$이 없어 대칭적이지 않습니다. 서로 다른 두 원소를 양방향으로 잇는 쌍은 없으므로 반대칭적입니다. $(1,2)$와 $(2,3)$이 이어지는데 $(1,3)$이 없으므로 추이적이지 않습니다. 둘째 줄은 이 관계의 관계 행렬로, 대각선이 1, 0, 0이라 반사적이지 않다는 것이 한눈에 보입니다.

헷갈리기 쉬운 경우들

반대칭은 "대칭이 아니다"라는 뜻이 아닙니다. 반대칭은 서로 다른 두 원소가 양방향으로 관계를 맺는 것만 금지하므로, 대칭이면서 반대칭인 관계도 있고 둘 다 아닌 관계도 있습니다. 같은 원소끼리의 쌍만 있는 항등관계 $\{(1,1),(2,2),(3,3)\}$은 대칭이면서 반대칭이고, 반사적이고 추이적이기도 합니다.

빈 관계도 주의해야 합니다. 원소가 있는 집합 위의 빈 관계 $\varnothing$은 $(a,a)$가 하나도 없으므로 반사적이지 않습니다. 하지만 대칭성, 반대칭성, 추이성은 "어떤 쌍이 있으면 어떤 쌍도 있어야 한다"는 조건이라, 쌍이 하나도 없으면 조건을 어기는 경우도 없어 모두 성립합니다. 조건명제의 가정이 거짓이면 참이 되는 것, 빈 정의역에서 전칭 명제가 참이 되는 것과 같은 이유입니다.

def properties(A, R):
    reflexive = all((a, a) in R for a in A)
    symmetric = all((b, a) in R for a, b in R)
    antisymmetric = all(a == b for a, b in R if (b, a) in R)
    transitive = all((a, d) in R for a, b in R for c, d in R if b == c)
    return reflexive, symmetric, antisymmetric, transitive


A = [1, 2, 3]
print(properties(A, {(a, a) for a in A}), properties(A, set()))
print(properties(A, {(a, b) for a in A for b in A if a <= b}))
print(properties(A, {(a, b) for a in A for b in A if a < b}))

(True, True, True, True) (False, True, True, True)
(True, False, True, True)
(False, False, True, True)

정수의 $\le$ 관계는 반사적, 반대칭적, 추이적이지만 대칭적이지 않습니다. $1\le2$이지만 $2\le1$이 아니기 때문입니다. $<$ 관계는 $1<1$이 거짓이라 반사적이지 않은데, 이 관계는 대각선의 쌍이 하나도 없습니다. 이처럼 모든 a에 대해 $aRa$가 아닌 관계를 비반사적(irreflexive)이라고 합니다. "반사적이지 않다"는 대각선의 쌍이 하나만 빠져도 해당하지만, 비반사적이려면 대각선의 쌍이 모두 없어야 하므로 두 말은 다릅니다. 앞의 R은 $(1,1)$이 있으므로 반사적이지 않지만 비반사적이지도 않습니다.

더 깊이: 성질마다 관계는 몇 개나 있을까

원소가 n개인 집합 위의 관계는 $n^2$개의 순서쌍 각각을 넣을지 뺄지 정해 만들므로 모두 $2^{n^2}$개입니다. 성질 하나를 요구하면 이 선택에 제약이 생기고, 그 제약을 따라 세면 개수를 바로 구할 수 있습니다. 반사적인 관계는 대각선의 n개 쌍을 반드시 넣어야 하므로 나머지 $n^2-n$개만 고를 수 있어 $2^{n^2-n}$개이고, 비반사적인 관계도 대각선을 모두 빼야 하므로 같은 수입니다.

대칭적인 관계는 대각선의 쌍 n개를 자유롭게 고르고, 서로 다른 두 원소의 쌍 $(a,b)$와 $(b,a)$는 둘 다 넣거나 둘 다 빼야 합니다. 그런 짝이 $\binom n2$개이므로 $2^{n+n(n-1)/2}=2^{n(n+1)/2}$개입니다. 반대칭적인 관계는 대각선을 자유롭게 고르고, 짝마다 둘 다 빼거나 $(a,b)$만 넣거나 $(b,a)$만 넣는 세 가지 가운데 하나를 고르므로 $2^n\cdot3^{n(n-1)/2}$개입니다. $n=2$라면 전체 16개 가운데 반사적인 것이 4개, 대칭적인 것이 8개, 반대칭적인 것이 12개입니다.

추이적인 관계에는 이렇게 간단한 식이 알려져 있지 않습니다. 추이성은 쌍 하나가 아니라 세 원소에 걸친 조건이라 선택을 서로 독립인 조각으로 나눌 수 없기 때문입니다. OEIS의 A006905에 따르면 원소가 0개부터 4개일 때 추이적인 관계는 1, 2, 13, 171, 3994개입니다. $n=2$의 13은 전체 16개에서 $(1,2)$와 $(2,1)$을 모두 가지면서 $(1,1)$이나 $(2,2)$가 빠진 세 관계를 뺀 수입니다.

정리

• A에서 B로의 이항관계는 곱집합 $A\times B$의 부분집합이고, $(a,b)\in R$을 $aRb$로 씁니다. 관계에는 방향이 있습니다.
• 관계는 순서쌍의 집합 말고도 관계 행렬이나 방향 그래프로 나타낼 수 있습니다.
• 반사성은 모든 원소가 자기와, 대칭성은 관계가 양방향으로, 추이성은 이어지는 두 관계가 바로 가는 관계로 이어진다는 조건이고, 반대칭성은 서로 다른 두 원소의 양방향 관계를 금지합니다.
• 반대칭은 대칭이 아님과 다르며, 항등관계는 대칭이면서 반대칭입니다.
• 빈 관계는 반사적이지 않지만 대칭·반대칭·추이는 조건을 어기는 쌍이 없어 성립합니다. 비반사적이라는 것은 대각선의 쌍이 모두 없다는 뜻입니다.

연습 문제

1. 모든 쌍을 가진 관계

$A=\{a,b\}$ 위의 관계 $R=\{(a,a),(b,b),(a,b),(b,a)\}$의 네 성질을 판정하세요.

2. 차가 짝수인 관계

정수 위의 관계 R을 "$a-b$가 짝수이면 $aRb$"로 정의합니다. 이 관계가 대칭적이고 추이적임을 증명하세요.

3. 쌍 하나로 성질 바꾸기

$A=\{1,2,3\}$ 위의 관계 $R=\{(1,2),(2,3)\}$에 쌍을 하나만 더해 추이적으로 만들려면 무엇을 더해야 하나요? 더한 뒤에도 반대칭인가요?

쌍이 없다는 이유만으로 모든 성질이 깨진다고 생각하지 말고, 각 성질의 조건을 어기는 쌍이 실제로 있는지 찾아보세요.