동치관계와 부분순서

학생들을 같은 학년끼리 묶는 일과, 선수 과목을 따라 과목의 수강 순서를 정하는 일은 둘 다 관계를 쓰지만 목적이 다릅니다. 앞의 것은 서로 같다고 볼 대상끼리 무리를 짓는 것이고, 뒤의 것은 대상 사이에 앞뒤를 정하는 것입니다. 이 글에서는 관계의 성질과 집합의 분할을 이어, 무리를 짓는 동치관계와 앞뒤를 정하는 부분순서를 다룹니다.

동치관계와 동치류

반사적이고 대칭적이며 추이적인 관계를 동치관계(equivalence relation)라고 합니다. "같은 학년이다"는 누구나 자기와 같은 학년이고, 내가 너와 같은 학년이면 너도 나와 같은 학년이며, 나와 너, 너와 그가 같은 학년이면 나와 그도 같은 학년이므로 동치관계입니다. 동치관계는 "어떤 기준에서 같다"는 생각을 관계로 나타낸 것입니다.

동치관계 R에서 원소 a와 관계가 있는 원소를 모두 모은 집합을 a의 동치류(equivalence class)라 하고 $[a]$로 씁니다. 정수 위에서 "$a-b$가 3의 배수"를 관계로 쓰면, 3으로 나눈 나머지가 같은 정수끼리 관계가 있습니다. $[0]$은 $\ldots,-3,0,3,6,\ldots$, $[1]$은 $\ldots,-2,1,4,\ldots$, $[2]$는 $\ldots,-1,2,5,\ldots$이고, 정수 전체가 이 세 동치류로 나뉩니다.

classes = {}
for x in range(-6, 7):
    classes.setdefault(x % 3, []).append(x)
print(classes)

{0: [-6, -3, 0, 3, 6], 1: [-5, -2, 1, 4], 2: [-4, -1, 2, 5]}

setdefault는 키가 없으면 빈 리스트를 만들어 두고 그 리스트를 돌려줍니다. Python의 %는 음수에서도 0 이상의 나머지를 돌려주므로 -4는 나머지 2의 무리에 들어갑니다. $-4=3\cdot(-2)+2$이기 때문입니다.

동치류는 분할을 이룬다

동치관계의 동치류들은 언제나 집합의 분할을 이룹니다. 이것을 증명하려면 동치류가 비어 있지 않고, 빠지는 원소가 없으며, 서로 다른 두 동치류가 겹치지 않음을 보이면 됩니다. 반사성에 따라 모든 a는 $aRa$이므로 $a\in[a]$입니다. 그래서 모든 동치류는 비어 있지 않고, 모든 원소가 적어도 하나의 동치류에 들어갑니다.

겹치는 부분이 있으면 두 동치류가 아예 같다는 것도 보일 수 있습니다. $[a]$와 $[b]$에 공통 원소 x가 있다고 합시다. 그러면 $aRx$이고 $bRx$입니다. 대칭성으로 $xRb$이고, $aRx$와 $xRb$에 추이성을 쓰면 $aRb$입니다. 이제 $[b]$의 임의의 원소 y는 $bRy$이므로, $aRb$와 추이성으로 $aRy$, 곧 $y\in[a]$입니다. 같은 방식으로 $[a]$의 원소도 모두 $[b]$에 들어가므로 $[a]=[b]$입니다. 따라서 서로 다른 동치류는 겹치지 않고, 동치류들은 분할을 이룹니다. 세 성질이 각각 어디에 쓰였는지 눈여겨볼 만합니다.

거꾸로 분할이 주어지면 "같은 블록에 들어 있다"를 관계로 정해 동치관계를 만들 수 있습니다. 모든 원소는 자기와 같은 블록에 있고, 둘이 같은 블록이면 순서를 바꾸어도 같은 블록이며, 블록이 겹치지 않으므로 a와 b, b와 c가 같은 블록이면 a와 c도 같은 블록입니다. 동치관계와 분할은 같은 것을 두 가지로 나타낸 셈입니다.

부분순서: 대칭 대신 반대칭

반사적이고 반대칭적이며 추이적인 관계를 부분순서(partial order)라고 합니다. 동치관계와 비교하면 대칭성 자리에 반대칭성이 들어간 것입니다. 정수의 $\le$, 집합의 포함 관계 $\subseteq$가 대표적인 부분순서입니다.

"부분"이라는 말은 모든 두 원소를 비교할 수 있을 필요가 없다는 뜻입니다. 포함 관계에서 $\{1,2\}$와 $\{2,3\}$은 어느 쪽도 다른 쪽의 부분집합이 아니므로 비교할 수 없습니다. 모든 두 원소를 비교할 수 있는 부분순서는 전순서(total order)라 하며, 정수의 $\le$가 그 예입니다.

$A=\{1,2,3,6\}$ 위에서 "a가 b를 나눈다", 곧 $b=ak$인 정수 k가 있다는 관계를 보겠습니다. 1은 모든 원소를 나누고, 2와 3은 6을 나누지만 2와 3은 서로를 나누지 않으므로 비교할 수 없습니다. 부분순서를 그림으로 나타낼 때는 Hasse 도표를 씁니다. 자기 자신과의 관계와, 추이성으로 저절로 따라오는 관계는 생략하고, 바로 위의 원소로 가는 관계만 선으로 이으며, 위쪽에 있을수록 순서가 뒤라고 약속합니다.

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, 6]
divides = {(a, b) for a in A for b in A if b % a == 0}
print(properties(A, divides))
cover = [(a, b) for a, b in sorted(divides)
         if a != b and not any(c not in (a, b) and (a, c) in divides and (c, b) in divides for c in A)]
print(cover)

(True, False, True, True)
[(1, 2), (1, 3), (2, 6), (3, 6)]

나눗셈 관계는 대칭적이지 않고 나머지 세 성질을 가지므로 부분순서입니다. cover는 사이에 다른 원소 c가 끼지 않는 쌍, 곧 Hasse 도표에 선으로 그릴 쌍만 고릅니다. $(1,6)$은 1→2→6으로 추이성에 따라 따라오므로 빠졌습니다. 그래서 도표는 아래에 1, 그 위에 2와 3, 맨 위에 6을 두고 네 선으로 이은 마름모 모양입니다.

최소와 극소

부분순서에서는 "가장 작은 원소"라는 말을 두 가지로 나누어야 합니다. 모든 원소보다 작거나 같은 원소를 최소원소(least element)라 하고, 자기보다 엄격히 작은 원소가 없는 원소를 극소원소(minimal element)라고 합니다. 전순서에서는 두 말이 같지만, 비교할 수 없는 원소가 있으면 달라집니다.

$\{2,3,6\}$의 나눗셈 순서에서 2와 3은 자기를 나누는 다른 원소가 없으므로 둘 다 극소입니다. 그러나 2는 3을 나누지 않고 3도 2를 나누지 않으므로, 모든 원소를 나누는 최소원소는 없습니다. 최소원소는 있다면 하나뿐이지만, 극소원소는 여러 개일 수 있습니다. 방향을 바꾸면 최대원소와 극대원소도 같은 방식으로 정의됩니다.

def minimal(S, rel):
    return [x for x in S if not any(y != x and (y, x) in rel for y in S)]


def maximal(S, rel):
    return [x for x in S if not any(y != x and (x, y) in rel for y in S)]


S = [2, 3, 6]
rel = {(a, b) for a in S for b in S if b % a == 0}
print(minimal(S, rel), maximal(S, rel))

[2, 3] [6]

더 깊이: 유한 부분순서는 한 줄로 늘어놓을 수 있다

원소가 유한하고 비어 있지 않은 부분순서 집합에는 극소원소가 적어도 하나 있습니다. 아무 원소 $x_1$에서 시작해 극소가 아니면 그보다 엄격히 작은 $x_2$를, 다시 그보다 작은 $x_3$을 고르는 식으로 내려가 봅니다. 추이성 때문에 이렇게 고른 원소는 앞의 모든 원소보다 엄격히 작고, 반대칭성 때문에 같은 원소가 다시 나올 수 없습니다. 원소가 유한하므로 이 사슬은 언젠가 멈추고, 멈춘 곳의 원소가 극소원소입니다.

이 사실을 되풀이하면 부분순서를 어기지 않고 모든 원소를 한 줄로 늘어놓을 수 있습니다. 남은 원소 가운데 극소원소 하나를 꺼내 줄 끝에 놓고, 그 원소를 지운 나머지에서 다시 극소원소를 꺼내기를 원소가 다 떨어질 때까지 반복합니다. $a$가 $b$보다 엄격히 작다면 a가 남아 있는 동안 b는 극소가 될 수 없으므로, 줄에서 a는 언제나 b보다 앞에 섭니다. 이렇게 만든 전순서를 원래 부분순서의 선형 확장(linear extension)이라고 합니다.

$\{2,3,6\}$의 나눗셈 순서라면 극소원소 2와 3 가운데 무엇을 먼저 꺼내느냐에 따라 2, 3, 6과 3, 2, 6의 두 줄이 나옵니다. 선형 확장은 대개 여러 개이며, 선후 관계가 있는 작업들의 실행 순서를 정하는 위상 정렬(topological sorting)이 바로 이 과정을 방향 그래프 위에서 하는 것입니다.

정리

• 동치관계는 반사적, 대칭적, 추이적인 관계이며, 원소 a와 관계가 있는 원소의 집합을 동치류 $[a]$라고 합니다.
• 동치류들은 비어 있지 않고 빠지는 원소가 없으며, 겹치면 같으므로 집합의 분할을 이룹니다. 거꾸로 분할에서 "같은 블록에 있다"는 동치관계가 됩니다.
• 부분순서는 반사적, 반대칭적, 추이적인 관계이며, 모든 두 원소를 비교할 수 있을 필요는 없습니다. 모든 쌍을 비교할 수 있으면 전순서입니다.
• Hasse 도표는 자기 관계와 추이성으로 따라오는 관계를 생략하고 바로 위의 원소로 가는 관계만 그립니다.
• 최소원소는 모든 원소 이하인 원소, 극소원소는 자기보다 엄격히 작은 원소가 없는 원소이며, 극소원소는 여러 개일 수 있습니다.

연습 문제

1. 홀짝으로 나누기

$\{0,1,2,3,4,5\}$에서 "홀짝이 같다"를 동치관계로 보면 동치류는 무엇이고, 어떤 분할이 만들어지나요?

2. 최소, 최대, 극대

$\{2,4,6\}$의 나눗셈 순서에서 최소원소, 최대원소, 극대원소를 찾으세요.

3. 동치관계가 아닌 관계

정수 위에서 "$|a-b|\le1$이면 $aRb$"로 정의한 관계는 동치관계인가요?

블록이 겹친다면 동치관계의 세 성질 가운데 무엇이 빠졌는지 확인해 보세요. 입력 하나에 출력이 하나씩 정해지는 특별한 관계는 다음 장의 함수와 일대일·전사에서, 선수 관계 같은 순서를 그림으로 다루는 방법은 그래프에서 이어집니다.