순서와 격자: 사물에 순위가 있을 때

📍 우리가 있는 곳: Part I · 밑바닥부터 시작하는 논리학 — 2장. 집합, 관계, 함수는 우리에게 순서쌍과 사상을 건네주었다. 이제 우리는 특별한 종류의 관계 하나가 자신의 정의역을 계층으로 순위 매기는 것을 지켜본다 — 최상원소, 최하원소, 그리고 임의의 두 사물에 대해 잘 정의된 "가장 가까운 공통 조상"을 가진 계층으로.

지난 장에서 관계는 그저 순서쌍들의 집합, 즉 "이것이 저것과 연결되어 있다"는 사실들의 묶음에 불과했다. 대부분의 관계는 특별한 모양이 없다. 하지만 몇몇 관계는 놀라운 일을 해낸다. 그것들은 자신의 정의역 전체를 하나의 사다리로 배열해서, 임의의 두 원소를 두고 어느 쪽이 더 위에 있는지 종종 말할 수 있게 만든다. 하위클래스 관계가 바로 그런 일을 완벽하게 해낸다. 이 장은 그 모양, 즉 순서(order)와, 순서를 계산 가능한 기계로 만들어 주는 두 연산인 미트(meet)와 조인(join)에 관한 것이다. 이것들은 이 시리즈에 등장하는 모든 계층 구조 아래에 조용히 자리 잡은 엔진이다.

우리는 "두 개념의 조인은 그들이 공유하는 가장 가까운 조상이다"라는 말을 그저 곧이곧대로 믿지는 않을 것이다. 우리는 순서를 세 가지 법칙으로부터 정의하고, 몇 개의 간선으로부터 전체 순서를 구축하면서 그 구성이 단계별로 종료되는 것을 지켜보고, 조인과 미트를 유계 문제(bounding problem)의 유일한 해로서 유도하고, 최하원소 하나를 추가하는 것만으로 이 특정 순서가 격자로 완성되는 이유를 증명하며, 이 모든 움직임을 그것을 실제로 수행하는 커밋된 코드의 정확한 줄에 연결할 것이다. 마지막에 이르면 join(professor, student) = researcher라는 문장은 더 이상 슬로건이 아니라, 여러분이 직접 손으로 수행하고 실제 프로그램의 출력과 대조하여 확인할 수 있는 하나의 계산이 될 것이다.

쉽게 말하면

사람 대신 아이디어로 이루어진 가계도를 상상해 보자. "교수"와 "학생"은 모두 "연구자" 아래에 있고, "연구자"는 다시 "사람" 아래에 있다. 임의의 두 상자를 가리키며 물어보자. 두 상자를 모두 포함하는 가장 가까운 위쪽 상자는 무엇인가? 교수와 학생의 경우 그것은 연구자, 즉 그들이 공유하는 가장 가까운 조상이다. 그 질문, "가장 가까운 공통 조상"이 바로 조인(join)이며, 그 거울상인 "가장 가까운 공통 후손"은 미트(meet)이다. 모든 쌍이 이 두 질문에 대해 깔끔한 답을 갖는 구조가 격자(lattice)이며, 일단 이것을 보고 나면 어디에서나 그것을 보게 된다. 클래스 계층에서, 신뢰도 점수에서, 그리고 이후 권에서 배울 임베딩의 기하학에서까지.

이 장에서 다루는 내용

• 관계에서 순서로 — 세 가지 법칙(반사성, 반대칭성, 추이성)을 각각 정량화된 명제로 적어보고, 사람 위에 연구자, 그 위에 교수와 학생이 있는 개념 계층에서 한 줄씩 검증한다.
• 전체 순서 구축하기 — 세 개의 덮개 간선을 아홉 개 쌍의 순서로 바꾸는 반사-추이 폐포의 실전 추적, $7 \to 9 \to 9$로 커지다가 스스로 멈추는 크기의 상승 사슬.
• 하세 다이어그램 — 덮개 간선만으로 순서를 그리기, 추이성이 복원할 수 있는 모든 간선을 생략하기.
• 유계, 조인, 미트 — 최소공통포섭자(least common subsumer)로서의 조인(최소상계), 그 거울상인 미트(최대하계). 각각을 유계 문제의 유일한 해로 유도하고 실제 코드를 통해 추적한다.
• 격자와 유계 격자 — 모든 쌍이 조인과 미트를 가질 때, 미트가 실패할 수 있는 이유, 그리고 이 순서에서는 최하원소 ⊥ 하나만으로 정확히 복구가 충분하다는 짧은 증명.
• 단조 사상과 커지는 사슬 — 순서를 보존하는 함수와 상승 사슬의 최소상계: 쌍에서 전체 커지는 집합으로 확장된 조인, 이는 이후 고정점 장들이 딛고 설 토대이다.
• 왜 이것이 반복되는가 — 포섭 순서(2권), 신뢰도 격자(2권과 5권), 상자 포함 관계(3권), 이 모두가 같은 모양이다.

관계에서 순서로: 세 가지 법칙

지난 장의 설정을 떠올려 보자. 집합 $S$ 위의 관계(relation)란 데카르트 곱(Cartesian product) $S \times S$의 부분집합이다. 여기서 $S \times S$는 $S$에서 뽑은 $a$와 $b$로 이루어진 모든 순서쌍 $(a, b)$의 집합이다. (기호 $\in$는 "~의 원소이다"로 읽고, $\subseteq$는 "~의 부분집합이다"로 읽는다. 따라서 $R \subseteq S \times S$라고 쓰면 $R$의 모든 쌍이 $S$에 대해 가능한 쌍들 중 하나임을 말하는 것이다.) 어떤 관계가 세 가지 법칙을 만족할 때, 우리는 더 이상 그것을 관계라고 부르지 않고 순서(order)라고 부르며, 기호도 ≤로 바꾼다. 기호를 설명하기 전에 평이한 말로 풀어보자면, 여기서 a ≤ b는 "a는 b만큼 혹은 그보다 더 특수하다"로 읽으면 된다. 즉 a는 계층에서 b보다 아래이거나 같은 위치에 있다. 그래서 professor ≤ researcher는 교수가 연구자의 특수한 한 종류임을 말한다. 기술논리학(description-logic) 문헌에서는 완전히 같은 개념을 다른 기호로 professor ⊑ researcher라고 쓰고, "교수는 연구자에 포섭된다(subsumed by)"라고 읽는다. ≤와 ⊑는 같은 관계가 두 가지 표기법을 입고 있는 것일 뿐이며, 우리는 이 둘을 서로 바꿔가며 사용할 것이다.

부분순서(partial order, 수학자들은 "부분순서집합"(partially ordered set)을 줄여 "poset"이라고도 쓴다)란 다음 세 가지 법칙을 만족하는 관계 ≤이다. 여기서 기호 $\forall$는 "모든 ~에 대해", $\land$는 "그리고", $\Rightarrow$는 "함의한다"로 읽는다 [1]:

• 반사성(Reflexive): $\forall x \in S,\; x \le x$. 모든 개념은 그 자신의 특수한 한 경우이다.
• 반대칭성(Antisymmetric): $\forall a, b \in S,\; (a \le b \,\land\, b \le a) \Rightarrow a = b$. 서로 다른 두 개념이 서로에 대해 각각 아래에 있을 수는 없다. 동률도, 두 원소로 이루어진 순환도 없다.
• 추이성(Transitive): $\forall a, b, c \in S,\; (a \le b \,\land\, b \le c) \Rightarrow a \le c$. 아래에-있음은 계속 전달된다. 교수는 연구자이고 연구자는 사람이므로, 교수는 사람이다.

"부분(partial)"이라는 단어가 정직한 부분이다. 관계가 추가로 $\forall a, b \in S,\; (a \le b) \lor (b \le a)$를 만족하면 그것은 전순서(total order)가 된다. 여기서 $\lor$는 "또는"으로 읽으며, 이는 임의의 두 원소가 비교 가능함을 뜻한다. 수직선은 전순서이다. 서로 다른 두 수가 주어지면 그중 하나는 더 작다. 부분순서는 그 요구를 내려놓는다. 어떤 쌍들은 비교 불가능(incomparable)하다. $\text{professor} \le \text{student}$도, $\text{student} \le \text{professor}$도 성립하지 않으므로, 교수와 학생은 어느 쪽도 다른 쪽 아래에 있지 않은 채 나란히 놓인다. 이것은 결함이 아니라, 가지를 뻗는 계층이라는 것의 요점 그 자체이다.

덮개 간선으로부터 전체 순서 구축하기

우리가 사용해 온 학계 세계는 순서를 매길 깔끔한 조각을 제공한다. 동반 파일 orders.py는 관계 전체를 일일이 나열하지 않고, 덮개 쌍(covering pairs), 즉 "바로 아래에 있다"는 직접적인 연결만을 명시한다(18행부터 23행):

COVERS = [
    ("professor", "researcher"),
    ("student", "researcher"),
    ("researcher", "person"),
]
CONCEPTS = ["professor", "student", "researcher", "person"]

세 개의 간선. 하지만 전체 순서 ≤는 이보다 더 많은 쌍을 가진다. 그것은 ("professor", "professor")와 같은 모든 반사 쌍을 포함해야 한다. 반사성이 $x \le x$를 요구하기 때문이다. 그리고 ("professor", "person")과 같은 모든 추이적 귀결도 포함해야 한다. $\text{professor} \le \text{researcher}$이고 $\text{researcher} \le \text{person}$이므로 그것이 강제되기 때문이다. 세 개의 간선으로부터 전체 관계를 구축하는 데는 반사-추이 폐포(reflexive-transitive closure)를 사용한다. 반사 쌍들과 덮개 쌍들로 시작하여, 추이성이 강제하는 쌍을 새로 아무것도 나타나지 않을 때까지 반복해서 추가하는 것이다. 이 엔진은 작은 동그라미 ∘로 표기하는 관계 합성(relational composition)이다. 합성 $\le \circ \le$는, 중간 원소 $b$가 존재하여 $a \le b$이고 $b \le c$일 때마다 $(a, c)$를 포함한다. 즉 두 개의 단일 단계가 사슬처럼 이어져 하나가 될 때마다 성립한다. 다음이 폐포 루프이다(26행부터 33행):

def leq_relation(covers, elements) -> set:
    """Reflexive-transitive closure of the covering pairs = the full ≤ order."""
    leq = {(x, x) for x in elements} | set(covers)
    while True:
        added = {(a, c) for (a, b) in leq for (b2, c) in leq if b == b2} - leq
        if not added:
            return leq
        leq |= added

이제 이것을 손으로 직접 실행하면서 관계가 커지는 것을 지켜보자. 관계 $R$의 크기(size), 즉 그것이 담고 있는 쌍의 개수를 $|R|$이라고 쓰자(세로 막대 $|\cdot|$은 집합에 속한 원소의 개수를 나타낸다). 28행의 씨앗은 네 개의 반사 쌍과 세 개의 덮개 쌍을 합집합하는데, 이 일곱 개의 쌍이 모두 서로 다르므로 씨앗은 $|R_0| = 7$개의 쌍을 갖는다:

$$R_0 = \underbrace{\{(\text{prof},\text{prof}),\, (\text{stud},\text{stud}),\, (\text{res},\text{res}),\, (\text{pers},\text{pers})\}}_{\text{반사, } 4} \;\cup\; \underbrace{\{(\text{prof},\text{res}),\, (\text{stud},\text{res}),\, (\text{res},\text{pers})\}}_{\text{덮개, } 3}.$$

30행의 루프 본문은 현재의 모든 쌍에 대해 합성 $\le \circ \le$를 형성하고 진짜로 새로운 것만 남긴다(- leq가 이미 존재하는 쌍을 빼준다). 첫 번째 패스에서, 공유된 중간 원소 $b$를 거쳐 $R_0$에 아직 없는 쌍을 만들어 내는 합성은 정확히 두 개이며, 둘 다 연구자를 거쳐 간다:

$$(\text{prof} \le \text{res}) \,\land\, (\text{res} \le \text{pers}) \;\Rightarrow\; \text{prof} \le \text{pers}, \qquad (\text{stud} \le \text{res}) \,\land\, (\text{res} \le \text{pers}) \;\Rightarrow\; \text{stud} \le \text{pers}.$$

그래서 첫 번째 패스는 $\{(\text{prof},\text{pers}),\, (\text{stud},\text{pers})\}$를 추가하여 관계를 $|R_1| = 9$로 키운다. 두 번째 패스에서는 모든 합성이 이미 존재하는 쌍에 착지한다(예를 들어 $\text{prof} \le \text{pers}$와 $\text{pers} \le \text{pers}$를 합성해도 그저 다시 $\text{prof} \le \text{pers}$를 줄 뿐이다). 그래서 added는 비어 있고 함수는 반환된다. 이 구성은 고정점(fixpoint), 즉 연산자가 더 이상 바꾸지 않는 값에 도달하는 짧은 상승 사슬의 크기들이다:

| 패스 $t$ | 루프 본문이 하는 일 | 추가된 쌍 | $|R_t|$ | |---|---|---|---| | $0$ | 씨앗: 반사 쌍 ∪ 덮개 쌍 | — | $7$ | | $1$ | 추이적 합성 $\le \circ \le$ 추가 | $(\text{prof},\text{pers}),\,(\text{stud},\text{pers})$ | $9$ | | $2$ | 추이적 합성 $\le \circ \le$ 추가 | 없음 | $9$ |

이것이 실제 숫자이다. 씨앗은 $7$개의 쌍이고, 한 번의 패스가 그것을 $9$로 만들며, 확인용 패스는 아무것도 찾지 못한다. 그래서 폐포는 아홉 개의 쌍으로 이루어진 관계를 반환한다. (이는 실행 예시가 더 큰 규모에서 사용하는 것과 동일한 "새로운 것이 나타나지 않을 때까지 성장한다"는 레시피이다. 그것의 전진 연쇄는 $23, 41, 47, 47$이라는 누적 물결 속에서 $47$개의 원자로 이루어진 모델에 도달한다. 같은 기계, 더 많은 간선일 뿐이다.) 전체 순서, 즉 아홉 개의 쌍 전부는 ✓ 표시가 있는 표로 가장 쉽게 읽을 수 있다. 가능한 하위 원소 $a$마다 한 행, 가능한 상위 원소 $b$마다 한 열, 그리고 $a \le b$인 곳에 정확히 ✓가 표시된다:

$a \le b$	professor	student	researcher	person
professor	✓		✓	✓
student		✓	✓	✓
researcher			✓	✓
person				✓

체크 표시를 세어보자. $3 + 3 + 2 + 1 = 9$로, $|R_1|$과 정확히 일치한다. (professor, student)에 있는 빈 칸과 그 거울상인 (student, professor)의 빈 칸이 바로 눈에 보이는 비교 불가능한 쌍이다.

실제 관계에서 세 가지 법칙 확인하기

아홉 개의 쌍으로 이루어진 관계를 손에 넣었으니, 그것이 정말로 부분순서임을 검증하는 일은 세 가지 법칙을 파이썬 한 줄씩으로 직접 옮기는 작업이다(43행부터 48행):

def is_partial_order(leq_set: set, elements) -> bool:
    reflexive = all((x, x) in leq_set for x in elements)
    antisym = all(a == b for (a, b) in leq_set if (b, a) in leq_set)
    transitive = all((a, c) in leq_set
                     for (a, b) in leq_set for (b2, c) in leq_set if b == b2)
    return reflexive and antisym and transitive

각 검사는 표에서 곧바로 읽어낼 수 있다. 반사성(44행)은 대각선 네 칸이 체크되어 있는지를 묻는데, 실제로 그렇다. 반대칭성(45행)은 체크된 모든 칸 $(a, b)$에 대해 그 거울상 $(b, a)$도 체크되어 있는 경우를 훑으면서 $a = b$를 요구한다. 서로 체크된 칸은 오직 네 개의 대각선 칸뿐이며, 그곳에서는 구성상 $a = b$가 성립하므로 이 법칙은 통과하고, 대각선 밖의 두-사이클도 없다. 추이성(46행부터 47행)은 합성 검사를 다시 실행하여 사슬로 이어진 모든 쌍이 이미 존재함을 확인한다. 예를 들어 $(\text{prof},\text{res})$와 $(\text{res},\text{pers})$를 합성하면 $(\text{prof},\text{pers})$가 되는데, 이는 체크되어 있다. 이 모듈을 실행하면 첫 줄에 판정 결과가 출력된다:

is a partial order: True

하세 다이어그램: 잡음 없이 순서 그리기

화살표로 그리면 아홉 개의 쌍으로 이루어진 전체 순서는 헝클어진 실타래가 된다. professor는 researcher를, person을, 그리고 자기 자신을 가리킨다. 하세 다이어그램(Hasse diagram)은 이를 정돈한 대안이다. 이를 정확히 정의하려면 순서의 엄격한 부분과 덮개 관계가 필요하다. $a \lt b$("엄격하게 아래에 있다")를 $a \le b$이고 $a \ne b$인 것으로 쓰자. 이는 네 개의 반사 쌍을 벗겨내고 다섯 개의 엄격한 쌍만 남긴다. 그러면 $a \lt c \lt b$인 중간 원소 $c$가 존재하지 않을 때, 즉 그 둘 사이에 엄격하게 놓인 것이 아무것도 없을 때, $a$는 $b$에 의해 덮인다(covered by)고 말한다. 하세 다이어그램은 덮개 간선만을 그리고, 더 일반적인 개념을 더 높이 배치하며, 위쪽으로 훑어 올라가는 것만으로 나머지 모든 것을 눈으로 복원할 수 있게 해준다.

이 장부 정리는 정확하다. 전체 순서는 아홉 개의 쌍을 갖는다. 네 개의 반사 루프를 제거하면 다섯 개의 엄격한 쌍이 남는다. 그중 중간 원소가 다리를 놓아주는 두 개, 즉 $(\text{prof},\text{pers})$와 $(\text{stud},\text{pers})$를 제거하면 — 둘 다 researcher가 다리를 놓아준다 — 세 개의 덮개 간선만이 남는다. 이는 정확히 COVERS에 있는 세 쌍이다. professor → person 간선은 결코 그려지지 않는다. researcher를 거쳐 이미 그곳에 걸어갈 수 있으므로, 잉크가 할 필요 없는 일을 추이성이 대신 해주는 것이다.

하세 다이어그램으로 그린 학계 세계의 개념 계층: 직접 간선만 그려져 있고, 높이가 일반성을 인코딩하며, researcher가 professor와 student 둘 모두의 바로 위에 있는 가장 가까운 상자임이 한눈에 보인다. 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

위에서 아래로 읽으면 순서는 한눈에 드러난다. person이 가장 일반적이고, professor와 student가 가장 특수하며, researcher가 그 사이의 경첩이다. 이 그림이 바로 이 장의 나머지 부분이 그 위에서 계산을 수행하는 구조 그 자체이다.

유계, 조인, 미트

두 원소 $a$와 $b$를 생각해 보자. 그것들의 상계(upper bound)란 $a \le x$와 $b \le x$가 함께 성립하도록, 즉 둘 다의 위에 놓이는 임의의 원소 $x$이다. 단 하나의 가장 작은 상계가 존재할 때, 그 최소상계(least upper bound)가 바로 조인(join)이며, a ⊔ b("a 조인 b")라고 쓴다. 정확히 말하면, $j$가 상계이면서 다른 모든 상계보다 아래에 있을 때, 즉 $a \le j$, $b \le j$이며 모든 상계 $x$에 대해 $j \le x$일 때, $j$는 $a$와 $b$의 조인이다. 개념 계층에서 조인은 여러분이 앞으로 계속 다시 만나게 될 이름을 갖는다. 바로 최소공통포섭자(least common subsumer, LCS), 즉 둘 다를 여전히 포함하는 가장 특수한 개념이다. 다른 연산에 대해서도 모든 단어를 거울처럼 뒤집으면 된다. 하계(lower bound)는 $x \le a$이고 $x \le b$이도록 둘 다의 아래에 놓이며, 그 최대하계(greatest lower bound)가 바로 미트(meet)이고, a ⊓ b("a 미트 b")라고 쓴다.

한 가지 사실이 이 두 연산을 모두 잘 정의된 것으로 만들어준다. 조인이 존재할 때, 그것은 유일하다. $j_1$과 $j_2$가 둘 다 $a$와 $b$의 최소상계라고 가정해 보자. 각각은 상계이고, 각각은 모든 상계보다 아래에 있으므로, $j_1 \le j_2$($j_1$이 최소이고 $j_2$가 상계이므로)이면서 $j_2 \le j_1$(대칭적으로)이다. 그러면 두 번째 법칙인 반대칭성이 $j_1 = j_2$를 강제한다. 그러므로 "그" 조인이라는 말은 정당한 표현이며, 같은 논증으로 "그" 미트도 유일하다. 이것이 바로 코드가 단일한 값이나 None을 반환할 수 있고 경쟁자들 사이에서 선택할 필요가 결코 없는 정확한 이유이다.

코드는 그 정의를 거의 그대로 옮긴 것이다. 상계는 필터이다(51행부터 52행). 조인은 다른 모든 상계보다 아래에 있는 상계만을 남긴다(55행부터 59행):

def upper_bounds(a, b, elements):
    return [x for x in elements if leq(a, x) and leq(b, x)]


def join(a: str, b: str, elements=CONCEPTS):
    """Least upper bound (least common subsumer), or ``None`` if none is least."""
    ubs = upper_bounds(a, b, elements)
    least = [x for x in ubs if all(leq(x, y) for y in ubs)]
    return least[0] if len(least) == 1 else None

미묘한 부분은 join의 가운데 줄이다. least는 모든 상계 $x$ 아래에 있는 상계 $x$만을 남기는데, 이것이 바로 유한집합 ubs에 적용된 "최소"의 정의이다. 방금 증명한 유일성은 마지막 줄에 날카로운 결론을 남긴다. 리스트 least는 결코 서로 다른 두 원소를 담을 수 없다. 서로 다른 두 원소가 각각 서로의 아래에 있다면 반대칭성을 위반하기 때문이다. 그래서 len(least)는 항상 $0$ 또는 $1$이다. 최소상계가 존재할 때는 $1$이고, 존재하지 않을 때는 $0$이다. 따라서 if len(least) == 1 else None이라는 보호 조건은 어림짐작이 아니라 "최소상계가 존재하는가?"라는 질문에 대한 정확한 검사이며, None 분기는 답이 "아니오"일 때 정확히 발동한다. 그 "혹은 None"이라는 부분에 정직함이 깃들어 있으며, 다음 절이 바로 그것이 물어뜯는 지점이다.

실전 실행: 성공하는 조인, 실패하는 미트

다음은 이 모듈의 요점 전부를 실제 출력 세 줄로 보여준다(76행부터 78행에서 생성됨):

join(professor, student) = researcher
meet(professor, student) = None
join(professor, person)  = person

각각을 ✓ 표와 대조하여 추적해 보자. join(professor, student)의 경우, upper_bounds는 네 개의 개념을 훑으면서 둘 다의 위에 있는 것들을 남긴다. 표에서 professor 행과 student 행을 읽어보면, 두 행 모두에서 체크된 열은 researcher와 person이므로, ubs = ['researcher', 'person']이다. 이제 최소 필터는 그 각각이 ubs의 모든 원소 아래에 있는지를 묻는다:

• researcher: $\text{researcher} \le \text{researcher}$ ✓이고 $\text{researcher} \le \text{person}$ ✓이므로 살아남는다.
• person: $\text{person} \le \text{researcher}$는 거짓이다((person, researcher) 칸이 비어 있다). 그래서 탈락한다.

least = ['researcher'], 길이 $1$이고, 함수는 researcher를 반환한다. 이것이 바로 작동하는 최소공통포섭자이다. 상계는 researcher와 person이지만, researcher가 person 아래에 있으므로 researcher가 가장 가까운 공유 조상이며, 이는 정확히 하세 다이어그램이 보여준 경첩이다.

join(professor, person)의 경우, professor 행과 person 행은 오직 person 열에서만 체크를 공유하므로 ubs = ['person']이고, 최소 필터는 그것을 남기며, 조인은 person이 된다. 이것은 쉬운 경우이다. person이 이미 professor 위에 있으므로, 둘 다의 위에 있는 가장 가까운 것은 person 자기 자신이다.

meet(professor, student) = None은 정직한 실패이다. 거울상 코드(62행부터 71행)는 하계들을 필터링하고 그중 가장 큰 것을 남긴다:

def lower_bounds(a, b, elements):
    return [x for x in elements if leq(x, a) and leq(x, b)]


def meet(a: str, b: str, elements=CONCEPTS):
    """Greatest lower bound, or ``None`` (e.g. professor and student share no
    common sub-concept — their meet would be ⊥, which we have not added)."""
    lbs = lower_bounds(a, b, elements)
    greatest = [x for x in lbs if all(leq(y, x) for y in lbs)]
    return greatest[0] if len(greatest) == 1 else None

lower_bounds(professor, student)는 $x \le \text{professor}$이고 $x \le \text{student}$인 임의의 $x$를 찾아 훑는다. professor 열을 아래로 읽어보면 오직 professor만 체크되어 있고, student 열을 아래로 읽어보면 오직 student만 체크되어 있다. 둘 다에 나타나는 단일 개념은 없으므로 lbs = []이다. 빈 리스트이므로 greatest도 비어 있고, 그 길이는 $0$이며, 미트는 None이다. professor와 student 둘 다의 아래에 있는 개념은 진정으로 존재하지 않는다. 우리 세계에서 그 둘을 동시에 만족하는 것은 아무것도 없다. professor들은 alice와 bob이고, student들은 carol, dave, erin으로 서로소인 두 그룹이다. 그래서 공통 하계는 비어 있고 미트는 존재하지 않는다. 계층의 언어로 말하면 professor ⊓ student는 그 구성원이 둘 다인 개념일 텐데, 그런 것은 없다. 즉 공허하고 불가능한 개념이다. 미트가 틀린 것이 아니다. 그것은 진정으로 부재하는 것이며, 코드는 답을 지어내는 대신 None이라고 말한다.

격자와 유계 격자: 빈틈 메우기

격자(lattice)란 모든 쌍이 조인과 미트를 둘 다 갖는 부분순서이다 [1][2]. 우리의 네 개념짜리 순서는 완전히 그렇지는 않다. 모든 쌍이 조인을 갖기는 한다. 최악의 경우라도 person이라는 공유 조상까지는 항상 올라갈 수 있기 때문이다. 그래서 이것은 person을 최고 원소로 갖는 조인반격자(join-semilattice)이다. 하지만 professor와 student의 미트가 없으므로 완전한 격자 검사는 통과하지 못한다.

이를 고치는 것은 두 개의 특수한 원소이다. ⊤로 쓰는 최상원소(top)는 $\forall x,\; x \le \top$이도록 모든 것의 위에 있다. 클래스 계층에서 그것은 보편 개념 "Thing"이다. ⊥로 쓰는 최하원소(bottom)는 $\forall x,\; \bot \le x$이도록 모든 것의 아래에 있다. 그것은 구성원이 전혀 없는, 공허하고 충족 불가능한 개념 "Nothing"이다. professor와 student 아래에 ⊥를 추가하면 그들의 미트는 더 이상 부재하지 않는다. 그것은 ⊥가 되며, 이는 방금 설명한 "구성원이 없는 개념"과 정확히 일치한다.

이제 신중하게 살펴볼 부분이다. 유계 격자(bounded lattice)란 추가로 ⊤와 ⊥를 갖는 격자이다 [2]. 단어의 순서에 유의하라. 두 개의 닻이 명명되기 전에 이미 격자여야 한다. ⊤와 ⊥를 임의의 부분순서집합에 그냥 붙인다고 해서 없던 유계가 생겨나지는 않는다. 비교 불가능한 두 원소가 비교 불가능한 여러 상계를 공유하면서도 top의 유무와 무관하게 단 하나의 최소 상계를 갖지 못할 수 있으므로, ⊤가 존재하더라도 조인은 실패할 수 있다. 우리 순서를 구해주는 것은 특정한 구조적 사실이며, 그것은 그냥 주장하기보다 증명할 가치가 있다.

주장. 최하원소 ⊥를 갖는 유한 조인반격자는 완전한 격자이다. 즉 모든 쌍 $a, b$가 미트를 얻는다.

증명. $L(a, b)$를 $a$와 $b$의 공통 하계들의 집합이라고 하자. $\bot \in L(a, b)$이므로 이 집합은 공집합이 아니며, 전체 순서가 유한하므로 이 집합도 유한하다. 조인반격자에서는 모든 유한하고 공집합이 아닌 집합이 최소상계를 가지며, 이는 이항 조인을 그 원소들에 대해 접어나가는 것으로 계산된다. ⊔가 결합적이고 교환적이므로, 반복된 쌍별 조인은 원소들을 결합하는 순서와 무관하며, 그 (유한한) 집합의 크기에 대한 귀납법에 의해, 그 접기 결과는 전체 집합의 최소상계와 같다. 그러므로 $m = \bigsqcup L(a, b)$를 모든 공통 하계의 조인이라고 하자. 우리는 $m$이 $a$와 $b$의 최대하계임을 두 단계로 보인다. 첫째, $m$ 자체가 $a$와 $b$의 하계이다. $L(a, b)$의 모든 원소는 $a$ 아래에 있으므로, $a$는 집합 $L(a, b)$의 상계이다. $m$이 그 집합의 최소 상계이므로 $m \le a$이고, 마찬가지로 $m \le b$이다. 따라서 $m$은 공통 하계이며, $m \in L(a, b)$이다. 둘째, $m$은 그중 가장 크다. 임의의 공통 하계 $\ell \in L(a, b)$는 $\ell \le m$을 만족한다. $m$이 전체 집합 $L(a, b)$의 상계이기 때문이다. 그러므로 $m$은 다른 모든 하계를 지배하는 하계이다. 즉 최대하계, 곧 미트이다. $\blacksquare$

이는 정확히 우리 순서가 처한 상황이다. 우리 순서는 이미 유한 조인반격자이며(계층은 나무 모양이므로 임의의 두 원소는 유일한 가장 가까운 조상을 가지고, 따라서 잘 정의된 조인을 가진다), 그 최상원소 person은 처음부터 있었다. 최하원소 ⊥ 하나를 추가하면 주장의 가정이 충족되고, 그래서 모든 쌍이 이제 미트를 얻으며, 이 순서는 진정한 유계 격자가 된다. 이전에는 None이었던 professor와 student의 미트는 $\bigsqcup \{\bot\} = \bot$이 되어, meet 함수의 문서화 문자열이 한 약속과 일치한다. 이것이 바로 ⊤와 ⊥가 모든 순서를 완성한다는 일반 법칙이 아니라, ⊥가 이 순서를 완성하는 특정한 이유이다. 학계-세계 조각은 일부러 그 ⊥ 없이 출시되었으며, 그래서 meet(professor, student)는 None을 반환하여, 패치를 보여주기 전에 여러분에게 그 빈틈을 먼저 보여준다.

단조 사상과 커지는 사슬: 축소판 최소 고정점

지금까지 우리는 두 원소를 조인했다. 두 가지 더 나아간 아이디어는 순서가 전체 커지는 집합 위에서 계산할 수 있게 해주며, 이는 다음 장들이 그 위에 고정점을 세울 정확한 토대이다.

첫 번째는 단조 사상(monotone map), 또는 순서보존함수(order-preserving function)라고도 부르는 것이다. 이는 한 순서집합 $(P, \le_P)$에서 다른 순서집합 $(Q, \le_Q)$으로 가는 함수 $f$로서 $\forall a, b \in P,\; a \le_P b \Rightarrow f(a) \le_Q f(b)$를 만족한다. 그것은 결코 순위를 흐트러뜨리지 않는다. 우리 세계에는 자연스러운 예가 있다. 각 개념을 그 외연(extension), 즉 그것에 속하는 개체들의 집합으로 보내는 것이다. $\text{professor} \le \text{researcher}$이고 모든 professor가 researcher이므로, 우리는 $\text{members}(\text{professor}) \subseteq \text{members}(\text{researcher})$를 얻는다. 즉 $\{\text{alice}, \text{bob}\} \subseteq \{\text{alice}, \text{bob}, \text{carol}, \text{dave}, \text{erin}\}$이다. ≤로 순서 매겨진 개념들로부터 ⊆로 순서 매겨진 구성원-집합들로 가는 이 사상은 순서를 보존한다. 개념 계층을 올라갈수록 외연은 커지기만 할 뿐 결코 줄어들지 않는다.

두 번째는 커지는 집합의 최소상계이다. 조인을 쌍에서 상승 사슬(ascending chain)로 확장해 보자. 상승 사슬이란 오직 커지기만 하는 수열 $X_0 \le X_1 \le X_2 \le \cdots$이며, 그 최소상계(그 상한(supremum))는 사슬 전체의 위에 동시에 있는 가장 작은 원소이다.

여러분은 이미 그런 것을 하나 실행해 본 적이 있다. 위에서 추적한 leq_relation 루프는 정확히 ⊆로 순서 매겨진 관계들의 격자 안에서의 상승 사슬이다. 각 패스는 이전 것을 포함하는 관계를 만들어낸다. $R_0 \subseteq R_1 \subseteq R_2$이며, 우리가 계산한 구체적인 크기는 $7 \to 9 \to 9$이다(⊆는 관계들을 서로 관련짓고, 크기는 단지 그것들의 정수 개수일 뿐이다). 이 루프는 그 사슬의 최소상계, 즉 덮개 쌍들을 포함하는 가장 작은 반사적·추이적 관계(반사-추이 폐포, 그 씨앗 $R_0$이 이미 네 개의 반사 쌍을 담고 있다)에서 멈춘다. 이는 단조 연산자(연산자 "모든 합성을 추가하라")의 최소 고정점(least fixpoint)이다. 맨 아래에서 시작해, 새로운 것이 나타나지 않을 때까지 단조 연산자를 적용한 다음, 커지는 사슬의 최소상계를 취하라. 이 레시피가 바로 이 시리즈의 모든 추론기가 실제로 계산하는 방식이며, 다음 장은 이를 정면으로 명명한다.

왜 이 모양은 계속 다시 나타나는가

이렇게 작은 아이디어에 장 하나를 통째로 쏟는 이유는, 부분순서, 그리고 이상적으로는 조인과 미트를 가진 유계 격자라는 이 동일한 구조가 이 시리즈 전체를 떠받치고 있기 때문이다:

• 포섭 순서(2권). 온톨로지의 클래스들은 ⊑ 아래에서 정확히 이 순서를 형성하며, 기술논리 추론기의 일은 그것을 계산하는 것이다. 조인은 여기서도 최소공통포섭자이다. "A와 B 둘 다의 위에 있는 가장 특수한 클래스는 무엇인가?"라고 묻는 것은, 우리가 여기서 손으로 그린 바로 그 계층을 EL 추론기가 올라가면서 답하는 질의이다.
• 신뢰도 / 주석 격자(2권과 5권). 사실들이 진리값을 가질 때, 즉 확실함, 확률적임, 알 수 없음, 모순됨과 같은 값들 자체가 격자를 형성하며, 두 증거를 결합하는 것은 그 격자에서의 미트 또는 조인이다. 등급이 있는 진리로 추론하는 것은 순서 안에서 추론하는 것이다.
• 순서로서의 상자 포함 관계(3권). 개념이 공간의 영역, 즉 상자로 학습될 때, 한 상자가 다른 상자 안에 있다는 것은 기하학적으로 ≤ 관계 그 자체이며, 두 상자의 조인은 둘 다를 감싸는 가장 작은 상자이다. 즉 기호가 아니라 좌표로 이루어진 최소공통포섭자이다. 순서에서 지식 계층으로 이어지는 이 다리는 형식개념분석(formal concept analysis)이 처음으로 지도를 그린 것이다 [3].

마지막 항목이 바로 논지이다. 조인은 논리학의 사소한 지식이 아니라 하나의 계약이다. 기호적 추론기는 간선을 걸어감으로써 join(professor, student) = researcher를 계산한다. 신경망 임베딩은 영역들을 교차시킴으로써 같은 답에 도달해야 한다. 둘이 일치할 때, 신경-기호 시스템은 정합적이다. 둘이 불일치할 때, 그중 하나는 거짓말을 하고 있는 것이다.

아직 풀리지 않은 부분

여기서는 순서가 작고, 손으로 그려졌으며, 세 개의 덮개 쌍으로 우리에게 건네졌기 때문에 조인이 정확하고 즉각적이었다. 규모가 커지면 두 가지가 그 안락함을 산산이 깨뜨린다. 첫째, 진정으로 표현력 있는 개념 언어에서는 두 클래스의 최소공통포섭자가 명명된 개념으로서 존재하지 않을 수 있다. 정직한 답은 익명의 방대한 서술일 수 있으며, 더 많은 개념을 조합할수록 그것은 지수적으로 자라날 수 있다. 그래서 "그냥 조인을 계산하라"는 더 이상 값싸지도, 심지어 유한하지도 않게 된다. 둘째, 이 시리즈에 더 날카롭게 관련된 것으로, 신경망 임베딩은 개념들을 연속 공간에 배치하며 미트와 조인을 오직 근사적으로만 지킬 수 있다. 기하학으로 학습된 포함 관계는 의도한 포섭 사실을 지키지 못할 수 있어서, professor의 상자가 researcher의 상자 안에 부분적으로만 들어가 목표 관계 professor ⊑ researcher가 더 이상 보존되지 않게 되거나, 기호적 순서가 금지하는 방식으로 두 개념이 겹치게 만들 수도 있다. 학습된 기하학이 평균적으로만이 아니라 정확하고 증명 가능하게 격자를 존중할 수 있는지는, 신경-기호 프로그램 전체가 계속 되돌아오는 미해결 질문 중 하나이다. 이 장은 여러분에게 그 잣대를 주고, 이후 권들은 그 간극을 측정한다.

왜 중요한가

여러분이 신경-기호 AI에서 만나게 될 모든 계층은, 즉 추론기가 걸어가는 클래스 분류체계든, 확률적 층이 결합하는 신뢰도 값이든, 임베딩이 학습하는 상자든, 모두 부분순서이며, 그중 어느 것에서든 흥미로운 계산은 조인 또는 미트이다. 이 하나의 추상을 제대로 갖추면 세 가지 보상이 따라온다. 즉 기호적 포섭을 하든 기하학적 포함을 하든 동일한 어휘("조인은 최소공통포섭자와 같다")를 얻고, 하이브리드 시스템의 두 절반이 서로 동의하는지에 대한 진단("내 임베딩의 조인이 내 추론기의 조인과 일치하는가?")을 얻으며, 계층에 최하원소가 빠져 있음을 알려주는 조기 경보(미트가 None을 반환하는 것)를 얻는다. 신경망과 기호 양쪽이 같은 순서를 존중할 때, 둘은 같은 세계를 서술한다고 신뢰받을 수 있으며, 이것이 바로 이 책 전체가 향해 쌓아가고 있는 약속이다.

핵심 용어

• 부분순서(poset) — 반사적이고 반대칭적이며 추이적인 관계 ≤. 정의역에 순위를 매기면서도 비교 불가능한 쌍을 허용한다.
• 반사성, 반대칭성, 추이성 — 세 가지 정의 법칙: $x \le x$; $a \le b$이고 $b \le a$이면 $a = b$가 강제된다; $a \le b$이고 $b \le c$이면 $a \le c$가 성립한다.
• 비교 불가능(incomparable) — 어느 쪽도 다른 쪽 아래에 있지 않은 두 원소(professor와 student). 순서가 "부분적"인 이유이다.
• 반사-추이 폐포 — 한 무리의 간선을 포함하는 가장 작은 반사적·추이적 관계. 여기서는 고정점에 이를 때까지 합성을 반복해서 구축했다(크기 $7 \to 9 \to 9$).
• 관계 합성(∘) — 두 단계를 하나로 연쇄하는 것: $a \le b$이고 $b \le c$이면 합성된 쌍 $a \le c$를 낳는다.
• 덮개 쌍 / 하세 다이어그램 — "바로 아래에 있다"는 직접적인 간선($a \lt b$이며 그 사이에 아무것도 엄격하게 놓여 있지 않은 것)과, 그 간선만을 그리고 나머지는 추이성으로 복원하는 다이어그램.
• 상계 / 하계 — 주어진 두 원소 둘 다의 위(아래)에 있는 원소.
• 조인(⊔) / 최소공통포섭자 — 최소상계: 둘 다의 위에 있는 가장 특수한 원소로, 존재할 때 유일하다. 개념 계층에서 join(professor, student) = researcher이다.
• 미트(⊓) — 최대하계: 둘 다의 아래에 있는 가장 일반적인 원소. meet(professor, student)는 최하원소가 없는 여기서는 부재한다.
• 격자 / 조인반격자 / 유계 격자 — 모든 쌍이 조인과 미트를 갖는 부분순서집합. 조인반격자는 오직 모든 조인만 갖는다. 유계는 격자에 최상원소 ⊤와 최하원소 ⊥를 추가한 것이다.
• 최상원소 ⊤ / 최하원소 ⊥ — 모든 것의 위에 있는 보편 원소("Thing")와 모든 것의 아래에 있는 공허한 원소("Nothing").
• 단조 사상(순서보존함수) — $a \le b$가 $f(a) \le f(b)$를 함의하는, 순서집합 사이의 함수. 결코 순위를 흐트러뜨리지 않는다. 각 개념을 그 구성원들의 집합으로 보내는 것이 한 예이다.
• 상승 사슬 / 커지는 집합의 최소상계 — 오직 커지기만 하는 수열 $X_0 \le X_1 \le X_2 \le \cdots$와, 그 전체의 위에 동시에 있는 가장 작은 원소. 조인을 쌍에서 무한 수열로 일반화한 것이며, 최소 고정점의 씨앗이다.

이 장이 이어지는 곳

이제 우리는 계층의 모양과, 그 위에서 계산하는 두 가지 연산을 갖게 되었으며, 단조 사상과 커지는 사슬의 최소상계를 통해, 이 시리즈의 모든 추론기가 의지하는 최소 고정점의 씨앗도 얻었다. 하지만 순서는 개념들이 어떻게 순위 매겨지는지는 말해주지만, 명제들을 참 또는 거짓인 결론으로 어떻게 결합하는지는 아직 말해주지 않는다. 다음 장인 명제 논리: 참, 거짓, 그리고 귀결은 가장 작은 완전한 논리, 즉 ∧, ∨, ¬("그리고", "또는", "아님"으로 읽는다)로 결합된 원자들을 소개하며, 만족스럽게도 그 진리값들은 결국 그들만의 유계 격자를 형성하게 되는데, ⊤와 ⊥는 우리가 방금 놓은 바로 그 자리에 있을 것이다. 그리고 전진 연쇄는 유도된 사실들의 커지는 집합에 대한 최소상계로 다시 등장할 것이다. 순서는 사라지지 않는다. 그것은 진리가 매달리는 뼈대가 된다.

---

동반 코드: examples/logic/orders.py는 덮개 쌍으로부터 개념 순서를 구축하고(leq_relation), 세 가지 법칙을 검사하며(is_partial_order), 조인과 미트를 계산한다(join, meet). python3 examples/logic/orders.py를 실행하면 이 장의 모든 숫자를 재현할 수 있다: "is a partial order: True" 판정, join(professor, student) = researcher, meet(professor, student) = None, 그리고 join(professor, person) = person.