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

📍 우리가 있는 곳: 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_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$	루프 본문이 하는 일	추가된 쌍	$\lvert R_t\rvert$
$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.

이 장에서 다루는 내용​

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

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

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

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

유계, 조인, 미트​

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

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

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

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

아직 풀리지 않은 부분​

왜 중요한가​

핵심 용어​

이 장이 이어지는 곳​