집합, 관계, 함수: 구조의 언어

📍 현재 위치: 1부 · 밑바닥부터의 논리 — 1장. 머리말은 한 번에 돌 하나씩 쌓아 올리는 기반을 약속했습니다. 이것이 바로 그 첫 번째 돌입니다 — 이후의 모든 장, 그리고 이후의 모든 권이 조용히 그 위에 서게 될 구조(structure)의 어휘입니다.

바로 다음 장들의 주제인 논리(logic)는 참인 것을 진술하기 위한 언어입니다. 그런데 언어가 무언가를 진술하려면, 먼저 이야기할 대상이 될 명사와 그 명사들이 서로 어떻게 얽혀 있는지 말할 방법이 필요합니다. 수학은 이 출발 도구 세트 전체를 세 가지 개념, 즉 집합(set), 관계(relation), 함수(function)에 담아냅니다. 이들은 이 책에서 가장 단순하면서도 가장 많은 것을 떠받치는 개념입니다: 지금 이 개념들을 명확히 해두면, 이 권의 나머지 부분은 그 위에 얹는 부수적인 정리 작업에 불과합니다.

이 장은 이 세 가지의 이름만 나열하지 않습니다. 각각을 아무것도 없는 상태에서부터 만들어 내고, 이후 장들이 기대는 모든 성질을 그저 단언하는 대신 유도하며, 처음 등장하는 모든 기호를 그 자리에서 풀어 설명한 다음, 실제로 작성된 코드에 정의를 한 줄 한 줄 그대로 적용해 실행합니다. 그 결과 "advises는 추이적이지 않다", "affiliated는 함수다", "cites를 닫으면 p3에서 p1에 도달한다" 같은 주장들은 우리가 들려주는 이야기가 아니라 프로그램이 실제로 출력하는 결과가 됩니다.

쉽게 말하면

휴대폰의 연락처 목록을 떠올려 보십시오. 그 목록 자체가 집합(set)입니다 — 이름들의 자루이며, 중복이 없고, 순서는 상관없습니다. "누가 누구를 팔로우하는가"는 관계(relation)입니다 — 이름들 사이에 그어진 화살표들의 엉킴입니다. 그리고 "각 사람의 유일한 집 주소"는 함수(function)입니다 — 결코 갈라지지 않는 화살표, 즉 사람마다 정확히 하나의 목적지만 있는 화살표입니다. 이 장 전체가 바로 이것입니다: 집합은 자루이고, 관계는 화살표들의 그물망이며, 함수는 모든 화살표가 각 이름에서 정확히 한 번만 출발하는 그물망입니다. 이후 논리가 하는 모든 일 — 그리고 놀랍게도, 이후 신경망이 하는 모든 일까지도 — 이 세 가지를 쌓아 올려서 만들어집니다.

이 장에서 다루는 내용

• 집합과 소속 — 사물들의 자루라는 개념, 외연성, 크기, 공집합, 그리고 부분집합을 우리의 예시 학계 세계에 등장하는 사람, 논문, 기관을 바탕으로 다룹니다.
• 순서쌍과 데카르트 곱 — 두 집합으로부터 생각할 수 있는 모든 짝을 만드는 방법, 순서쌍 안의 순서가 왜 의미를 지니는지, 그리고 짝의 개수와 관계의 개수가 도대체 얼마나 되는지를 다룹니다.
• 튜플들의 집합으로서의 관계 — advises, cites, affiliated는 마법이 아닙니다. 각각은 문자 그대로 데카르트 곱에서 뽑아낸 순서쌍들의 집합이며, 지식베이스에서 그대로 읽어낸 것입니다.
• 중요한 세 가지 모양 — 반사적, 대칭적, 추이적 모양을 각각의 정확한 술어와 함께 손으로 직접 계산하고 기계로 확인합니다(advises는 추이적이 아닙니다).
• 함수 — 각 입력이 정확히 하나의 출력을 갖는 관계입니다. affiliated는 이 조건을 만족하고 advises는 만족하지 않으며, 코드 속 단일값(single-valued) 검사가 정확히 그 이유를 말해줍니다.
• 합성과 추이적 폐쇄 — advises를 그 자신과 사슬처럼 잇는 것이 곧 grand-advising이고, cites를 닫는 것이 곧 인용 도달가능성임을, 한 라운드씩 고정점(fixpoint)까지 추적하며 실제 프로그램 출력과 대조해 확인합니다.
• 뉴로-심볼릭 AI가 왜 이것을 필요로 하는가 — 지식 그래프는 유형화된 관계들의 집합이고, 추론은 관계를 합성하는 것이며, 임베딩은 기호에서 벡터로 가는 함수입니다.

집합: 사물들의 자루

집합(set)이란 서로 구별되는 것들의 순서 없는 모음이며, 그 안의 개별 항목을 원소(element) 또는 멤버(member)라고 부릅니다. 이 문장 속 두 낱말이 모든 일을 합니다. 순서가 없다는 것은 집합이 오직 어떤 것들이 그 안에 들어있는가에 의해서만 정해지고 다른 어떤 것에도 좌우되지 않는다는 뜻이며, 그래서 {alice, bob}과 {bob, alice}는 같은 집합입니다. 구별된다는 것은 어떤 원소가 들어있거나 들어있지 않거나 둘 중 하나일 뿐이라는 뜻이며, 두 번 들어있다는 것 자체가 존재하지 않으므로 {alice, alice, bob}은 그저 {alice, bob}입니다. 이 두 사실은 하나의 원리, 즉 외연성 공리(axiom of extensionality)가 지닌 두 얼굴입니다: 두 집합이 같다는 것은 정확히 그 둘이 같은 멤버를 가질 때이며, 그것들이 어떻게 나열되었는지는 상관이 없습니다 [1].

어떤 것이 집합에 속한다는 것을 말하려면 소속 기호(membership symbol) ∈를 쓰며, "~의 원소이다"라고 읽습니다: alice ∈ People은 alice가 그 사람들 중 한 명이라는 것을 주장합니다. 그 부정은 ∉이며, "~의 원소가 아니다"라고 읽습니다: carol ∉ Institutions. 집합 A의 원소 개수는 그 크기(cardinality)이며, 양쪽에 세로줄을 둘러 $\lvert A \rvert$로 씁니다(이 세로줄은 "~의 크기"를 뜻하며, 다음 절에서 만나게 될 "조건을 만족하는"이라는 뜻의 세로줄과는 다른 용법이므로 어느 쪽을 읽고 있는지 주의해야 합니다). kb.py에 정의된 우리의 예시 학계 세계는 32–34번째 줄에서, 앞으로 쓰게 될 세 개의 개체-집합(individual-set)으로 문을 엽니다.

PEOPLE = ["alice", "bob", "carol", "dave", "erin"]
PAPERS = ["p1", "p2", "p3"]
INSTITUTIONS = ["mit", "cmu"]

그러므로 $\lvert \text{People} \rvert = 5$, $\lvert \text{Papers} \rvert = 3$, $\lvert \text{Institutions} \rvert = 2$입니다. (코드는 이들을 파이썬 리스트로 적고 있으며, 리스트는 실제로 순서를 기록하고 중복을 허용할 수 있습니다. 집합이라는 개념은 우리가 그 두 가지 힘 중 어느 것도 쓰지 않겠다는 약속이며, 아래의 모든 연산은 그 약속을 그대로 지킵니다.)

아무것도 들어있지 않은 집합이 공집합(empty set)이며, ∅로 쓰고, $\lvert \varnothing \rvert = 0$인 유일한 집합입니다. 답이 없는 질문을 던지는 순간 공집합이 등장합니다. 누가 alice를 지도하는가? advising 사실들을 훑어보면 alice는 두 번째 자리에 결코 나타나지 않으므로, alice의 지도교수들의 집합은 ∅입니다. 공집합은 "아무것도 아닌 것"이 아니라, 마침 원소를 0개 가지고 있는, 완전히 정상적인 하나의 집합입니다. 그리고 이것을 평범한 대상으로 취급하는 것이야말로 이후의 정의들이 예외적인 경우(edge case)에서 무너지지 않도록 지켜줍니다 [1].

한 집합은 다른 집합 안에 통째로 들어갈 수 있습니다. A의 모든 원소가 B의 원소이기도 하다면, A는 B의 부분집합(subset)이라 하고 A ⊆ B로 씁니다. 한정기호 ∀("모든 ~에 대해"라고 읽습니다)와 함의 →("만약 ~라면"이라고 읽습니다)를 써서 풀어 쓰면, 이는 다음과 같습니다.

$$A \subseteq B \quad\Longleftrightarrow\quad \forall x\,\big(x \in A \;\rightarrow\; x \in B\big),$$

즉 "모든 것 $x$에 대해, $x$가 $A$에 들어있다면 $x$는 $B$에도 들어있다"는 뜻입니다. 이는 $A$가 공집합일 때 공허하게(vacuously) 참이 되므로, 모든 $B$에 대해 $\varnothing \subseteq B$가 성립한다는 점에 주목하십시오: $\varnothing$에는 이 검사를 통과하지 못할 원소 자체가 없기 때문입니다. kb.py의 규칙들은 부분집합의 작은 탑을 하나 쌓아 올립니다. 교수들은 {alice, bob}이고(40–41번째 줄의 사실들), 75번째 줄의 규칙 researcher(X) ⟸ professor(X)는 모든 교수를 연구자로 만들며, 76번째 줄의 규칙은 모든 학생에 대해 같은 일을 하므로 다섯 사람 모두가 연구자가 됩니다. 그리고 77번째 줄의 규칙 person(X) ⟸ researcher(X)는 모든 연구자를 사람으로 만듭니다. 이 세 규칙을 집합 포함 관계로 읽으면 다음과 같습니다.

$$\{\text{alice},\text{bob}\} \;\subseteq\; \text{researchers} \;\subseteq\; \text{persons},$$

크기로 보면 $2 \le 5 \le 5$입니다(유한 집합의 부분집합은 그 집합보다 클 수 없으므로, 크기는 오직 올라가거나 그대로일 뿐입니다). 부분집합은 이후 논리가 아무도 일일이 나열하지 않고도 "모든 교수는 사람이다"라고 말하는 방식이며, 딱 떨어지는 집합 관계 하나가 일반적인 참을 대신할 수 있다는 첫 번째 암시입니다.

순서쌍과 데카르트 곱

집합은 순서를 잊어버리지만, 세상은 그렇지 않습니다: "alice가 bob을 지도한다"는 "bob이 alice를 지도한다"와는 다른 사실입니다. 이 방향성을 담아내려면 순서쌍(ordered pair)이 필요하며, (a, b)로 씁니다. 집합과 달리 (alice, bob)과 (bob, alice)는 진짜로 서로 다른 대상입니다. 순서쌍을 "순서가 있게" 만드는 것은 정확히 다음과 같은 특징적 성질(characteristic property)입니다.

$$(a, b) = (c, d) \quad\Longleftrightarrow\quad a = c \ \text{ and } \ b = d,$$

두 순서쌍이 같으려면 첫 번째 자리에서도 일치하고 그리고 두 번째 자리에서도 일치해야 합니다 [2].

순서쌍을 별다른 의심 없이 마음껏 써도 되는 더 깊은 이유는, 순서쌍이 전혀 새로운 종류의 대상이 아니기 때문입니다. 순서쌍은 집합만으로 만들어낼 수 있으며, 그래서 우리의 세 가지 개념 바깥에서 몰래 끼어든 것이 아무것도 없습니다. 쿠라토프스키(Kuratowski)의 표준 구성법은 $(a, b) := \{\{a\}, \{a, b\}\}$입니다 [3]. 이것이 특징적 성질을 갖는지 확인하려면, 먼저 두 좌표가 일치하는 퇴화(degenerate) 경우를 처리해야 합니다. $a = b$일 때 이 순서쌍은 $\{\{a\}, \{a,a\}\} = \{\{a\}\}$로, 멤버가 하나뿐인 집합족(family)이 됩니다. 이때 $(a,b) = (c,d)$는 $\{\{a\}\} = \{\{c\}, \{c,d\}\}$로 읽히는데, 멤버가 하나뿐인 집합족이 다른 것과 같으려면 그 다른 쪽 역시 같은 내용의 멤버 하나만을 가져야 하므로 $\{c\} = \{c,d\} = \{a\}$이고, 이는 $c = d = a = b$를 강제합니다 — 정확히 $a = c$이고 $b = d$입니다. 이제 $a \neq b$라고 가정하면, 이 순서쌍은 진짜로 서로 다른 두 멤버 $\{a\}$와 $\{a,b\}$를 갖습니다. 두 가지 추출 연산으로 좌표를 되찾을 수 있습니다: 이 순서쌍의 두 멤버의 교집합은 $\{a\} \cap \{a,b\} = \{a\}$이고, 그 합집합은 $\{a\} \cup \{a,b\} = \{a,b\}$입니다. $(a,b) = (c,d)$가 같은 두-멤버 집합이라면(따라서 $c \neq d$이기도 합니다), 양쪽에서의 추출 결과도 일치해야 합니다: 교집합을 취하면 $\{a\} = \{c\}$이므로 $a = c$이고, 합집합을 취하면 $\{a,b\} = \{c,d\} = \{a,d\}$인데, 이는 $a \neq b$와 함께 $b = d$를 강제합니다. 이렇게 순서는, 오직 어떤 원소가 자신만의 싱글턴(singleton) 안에 홀로 앉아 있는가만으로, 순서 없는 그릇으로부터 온전히 복원될 수 있습니다 [2].

이제 집합 A에서 첫 번째 원소를, 집합 B에서 두 번째 원소를 가져와 만들 수 있는 모든 순서쌍을 모아 봅시다. 그 모음이 바로 데카르트 곱(Cartesian product)이며, A × B로 씁니다. 조건제시법(set-builder notation)으로 쓰면 — 여기서 세로줄 $\mid$은 "조건을 만족하는"이라고 읽고 ∧는 "그리고"라고 읽습니다 — 다음과 같습니다.

$$A \times B \;=\; \{\, (a, b) \;\mid\; a \in A \ \wedge\ b \in B \,\}.$$

그 크기는 얼마나 될까요? 순서쌍 하나를 고르려면 두 번의 독립적인 선택을 해야 합니다: 첫 번째 좌표를 $\lvert A \rvert$가지 방법 중에서, 두 번째 좌표를 $\lvert B \rvert$가지 방법 중에서 고릅니다. 독립적인 선택은 곱해지므로,

$$\lvert A \times B \rvert \;=\; \lvert A \rvert \cdot \lvert B \rvert.$$

우리의 사람들에 대해, People × People은 $5 \times 5 = 25$개에 이르는 생각할 수 있는 모든 "누가 누구에게" 짝짓기를 담고 있습니다: 참이든 아니든, (alice, alice)와 같은 다섯 개의 자기-짝(self-pair)을 포함해서 존재할 수 있는 모든 지도 관계 링크입니다. 데카르트 곱은 모든 가능성의 공간이며, 다음에 다룰 개념은 그중 실제로 성립하는 가능성을 어떻게 골라내는가입니다.

관계: 튜플들의 집합

관계(relation)란 그저 데카르트 곱의 부분집합, R ⊆ A × B이며, 생각할 수 있는 모든 순서쌍 중에서 골라낸 한 줌의 순서쌍입니다. 이것이 정의의 전부이며, 놀라울 만큼 강력합니다. 관계란 25개의 순서쌍 중 어떤 부분집합이든 될 수 있고, 그 25개의 순서쌍 각각은 독립적으로 들어있거나 들어있지 않거나 둘 중 하나이므로, People 위에서 가능한 서로 다른 관계의 개수는

$$2^{\lvert \text{People} \times \text{People} \rvert} \;=\; 2^{25} \;=\; 33{,}554{,}432,$$

입니다(각 순서쌍이 들어있는가 아닌가라는 독립적인 2의 인수를 하나씩 기여하므로, 그 인수들이 곱해져 $2^{25}$이 됩니다). advises는 그 3,300만 가지 중 하나의 구체적인 선택입니다: People × People 중 실제로 성립하는 네 개의 순서쌍이며, kb.py의 47–50번째 줄에 나열되어 있습니다.

("advises", "alice", "bob"),
("advises", "bob", "carol"),
("advises", "bob", "dave"),
("advises", "carol", "erin"),

같은 방식으로 cites는 Papers × Papers의 부분집합이 되고(kb.py 57–58번째 줄: p2가 p1을 인용하고, p3가 p2를 인용), affiliated는 People × Institutions의 부분집합이 됩니다(60–64번째 줄: 각 사람이 자신의 소속 학교와 짝지어짐). sets_relations.py에서 도우미 함수 pairs(16–19번째 줄)는 이러한 사실들을 순서쌍으로 이루어진 수학적 집합으로 그대로 다시 읽어내는 것 말고는 별다른 일을 하지 않습니다.

def pairs(predicate: str) -> set:
    """Extract a binary relation from the KB as a set of (a, b) pairs."""
    return {(a, b) for (p, a, b) in
            (f for f in FACTS if len(f) == 3) if p == predicate}

이 중괄호와 세로줄로 이루어진 컴프리헨션(comprehension)은 조건제시법을 파이썬으로 옮겨 적은 것입니다: "(p, a, b)가 길이 3짜리 사실이고 p가 요청받은 술어와 같은, 그러한 모든 (a, b)의 집합"이라고 읽습니다. 여기에는 코드와 수학 사이에 아무런 간극이 없습니다: pairs("advises")는 관계 advises 그 자체입니다. 화면에 표시하기 위해 정해진 순서로 정렬하면, sorted(pairs("advises"))는 다음 네 순서쌍으로 계산됩니다.

sorted(pairs("advises")) = [('alice', 'bob'), ('bob', 'carol'), ('bob', 'dave'), ('carol', 'erin')]

이는 가능한 25개 중 $\lvert \text{advises} \rvert = 4$개입니다. 이 장의 나머지에서 다루는 모든 연산은 바로 이런 종류의 집합에 대한 연산입니다.

집합과 관계로 본 학계 세계: 사람, 논문, 기관은 개체(individual)이고, advises, cites, affiliated는 순서쌍들의 집합이며, 이 순서쌍들을 합성하거나 폐쇄하는 것이 바로 grand-advising과 인용 도달가능성이 나타나는 방식입니다. 저자들이 AI의 도움을 받아 제작한 원본 도표입니다.

관계가 가질 수 있는 세 가지 모양

관계가 순서쌍들의 집합이라는 것을 알고 나면, 그 관계가 어떤 모양을 하고 있는지 물을 수 있습니다. 그리고 세 가지 모양이 하도 자주 등장해서 저마다 이름이 붙어 있습니다. sets_relations.py는 각 모양을 정확한 술어(predicate)로 바꾸어 놓으며(39–48번째 줄), 우리는 코드에서 곧바로 그 정의를 읽어낼 수 있습니다 [4].

def is_reflexive(R: set, domain) -> bool:
    return all((x, x) in R for x in domain)

def is_symmetric(R: set) -> bool:
    return all((b, a) in R for (a, b) in R)

def is_transitive(R: set) -> bool:
    return all((a, c) in R for (a, b) in R for (b2, c) in R if b == b2)

반사적(reflexive)이라는 것은 모든 원소가 자기 자신과 관계를 맺는다는 뜻입니다: $\forall x \in \text{domain},\ (x, x) \in R$. 술어 is_reflexive는 정의역(domain) 전체, 즉 리스트를 순서대로 훑으면서 매번 자기-짝(self-pair)을 요구합니다. Advising은 바로 첫 번째 사람에서부터 실패합니다: (alice, alice)는 그 네 개의 순서쌍 안에 없으므로, all(...)은 곧바로 False로 단락(short-circuit)됩니다. 아무도 자기 자신을 지도하지 않으므로 advises는 반사적이지 않습니다. 반면 "같은 기관에 있다"처럼 자기 자신도 셈에 넣는 관계라면 반사적일 것입니다.

대칭적(symmetric)이라는 것은 화살표가 양방향으로 온다는 뜻입니다: $\forall (a, b) \in R,\ (b, a) \in R$. 이 술어는 저장된 각 순서쌍 (a, b)를 가져와 그 역순인 (b, a)도 들어있는지 확인합니다. Advising은 단연코 대칭적이 아닙니다: 저장된 어떤 순서쌍, 이를테면 (alice, bob) ∈ advises의 역순인 (bob, alice) ∉ advises이므로, 집합을 어떤 순서로 훑든 상관없이 all(...)은 False를 반환합니다. 대칭성이 실제로 성립하는 경우를 보려면, kb.py의 82–83번째 줄에 정의된 파생 관계 colleague(동료)를 살펴보십시오: 서로 다른 두 사람이 같은 기관을 공유하면 동료입니다. affiliated에 대해 이 규칙을 돌려보면(mit 그룹 {alice, bob}과 cmu 그룹 {carol, dave, erin}), 각 그룹 안의 순서 없는 짝마다 양방향 모두가 나옵니다.

colleague = [('alice','bob'), ('bob','alice'),
             ('carol','dave'), ('carol','erin'), ('dave','carol'),
             ('dave','erin'), ('erin','carol'), ('erin','dave')]

여덟 개의 순서쌍입니다(mit 그룹이 $2$개, cmu 그룹이 $3 \times 2 = 6$개를 기여합니다). 그리고 is_symmetric(colleague)는 True를 반환합니다: colleague의 정의 자체가 "같은 기관을 공유한다"는 대칭적인 조건으로부터 만들어졌으므로, 그것이 그리는 모든 화살표에는 그 역순도 공짜로 딸려 옵니다.

추이적(transitive)은 추론에서 가장 중요한 성질입니다: (a, b)와 (b, c)가 둘 다 들어있을 때마다 (a, c)도 반드시 들어있어야 하며, 화살표들이 사슬처럼 이어져 지름길이 됩니다. 형식적으로는 $\forall (a,b),(b,c) \in R,\ (a,c) \in R$이며, 술어 is_transitive는 안쪽 끝점이 일치하는(가드 if b == b2) 저장된 순서쌍의 모든 짝을 찾아 지름길 (a, c)를 요구합니다. 여기 이 시리즈 전체가 기대고 있는 반례가 있습니다. advises의 두 순서쌍 (alice, bob)과 (bob, carol)을 봅시다: 이 둘의 안쪽 끝점은 bob에서 일치하므로, 추이성이 성립하려면 (alice, carol) ∈ advises이어야 합니다. 하지만 그것은 거기 없습니다. 그래서 검사는 실패하고, advises는 추이적이 아닙니다. 이 빠진 지름길은 버그가 아니라 다른 관계, 즉 grand-advising이며, 다음 절은 advises가 이미 그것을 담고 있는 척하는 대신 이를 의도적으로 구축합니다. advises에 대해 세 가지 모양 술어를 모두 평가해 보면 손으로 한 논증이 정확히 확인됩니다.

is_reflexive(advises, people) = False
is_symmetric(advises)         = False
is_transitive(advises)        = False

advises는 이 세 가지 모양 중 어느 것도 갖고 있지 않으며, 바로 그렇기 때문에 우리가 계속해서 되돌아가는 관계입니다: 앞으로 나올 모든 연산은 advises에게 없는 구조를 만들어내는 일에 관한 것입니다.

함수: 결코 갈라지지 않는 관계

부분 함수(partial function)란 관계에 한 가지 약속이 더해진 것입니다: 각 입력은 많아야 하나의 순서쌍에서 첫 번째 원소로 나타납니다. 어떤 입력도 서로 다른 두 출력으로 대응되지 않습니다. 화살표가 결코 갈라지지 않습니다. 공식으로 쓰면, R ⊆ A × B가 부분 함수라는 것은 다음이 성립할 때입니다.

$$\forall a,\ \forall b,\ \forall b',\quad \big((a, b) \in R \ \wedge\ (a, b') \in R\big) \;\rightarrow\; b = b',$$

즉 "만약 $a$가 $b$와 $b'$ 둘 다를 가리킨다면, $b$와 $b'$는 애초부터 같은 것이었다"는 뜻입니다. $A$에서 $B$로 가는 전역 함수(total function)는 여기에 더해 $A$의 모든 입력이 나타나야 하므로, 각 입력은 정확히 하나의 출력을 갖습니다. 이때 이를 $f : A \to B$로 쓰고, $f(a) = b$라고 쓰며, $a \mapsto b$(막대-화살표 ⟼는 "~로 대응된다"라고 읽습니다)로도 그립니다 — 입력 $a$에 속하는 유일한 출력을 명명하는 것입니다 [1]. sets_relations.py는 이 정의 가운데 단일값 조건을 직접 검사합니다(51–58번째 줄).

def is_function(R: set) -> bool:
    """A relation is a (partial) function iff no input maps to two outputs."""
    seen = {}
    for a, b in R:
        if a in seen and seen[a] != b:
            return False
        seen[a] = b
    return True

딕셔너리 seen은 각 입력이 이미 주장한 출력을 기억합니다. 어떤 입력이 다른 출력과 함께 다시 나타나는 바로 그 순간, 갈라짐이 감지되고 단일값 약속은 깨집니다. 이를 두 관계에 대해 추적해 봅시다.

affiliated는 People에서 Institutions로 가는 전역 함수입니다. 그 다섯 순서쌍은 alice ↦ mit, bob ↦ mit, carol ↦ cmu, dave ↦ cmu, erin ↦ cmu입니다. 각 사람은 정확히 한 번만 첫 번째 좌표로 나타나므로, 모든 입력이 나타나고, 어떤 입력도 다시 나타나지 않으며, seen[a] != b 분기는 결코 발동하지 않고, 루프는 끝까지 돌아 return True를 실행합니다. 이는 kb.py의 모델링 주석(59번째 줄)과 정확히 일치합니다: "Affiliation is functional: each person works at exactly one institution"(소속은 함수적이다: 각 사람은 정확히 하나의 기관에서 일한다). affiliated가 단사(injective, 일대일)는 아니라는 점에 주목하십시오: mit는 서로 다른 두 입력의 출력이고 cmu는 세 입력의 출력이므로, 많은 입력이 하나의 출력을 공유합니다. 이는 아무 문제도 없습니다 — 함수는 하나의 입력이 두 출력으로 갈라지는 것을 금지할 뿐, 두 입력이 하나의 출력에서 만나는 것을 금지하지는 않습니다.

advises는 부분 함수조차 아닙니다. bob은 (bob, carol)과 (bob, dave)라는 서로 다른 두 순서쌍의 첫 번째 좌표입니다. 루프가 둘 중 어느 것을 먼저 만나든 그것이 seen[bob]에 기록되고, 다른 하나를 만났을 때 bob이 이미 seen에 있는데 그 출력이 다르다는 것이 발견되어, 가드 seen[a] != b가 발동하고 함수는 False를 반환합니다. 이 판정은 bob의 두 순서쌍 중 어느 쪽이 먼저 오는지에 좌우되지 않습니다: bob은 두 학생을 지도하므로, 어느 쪽이든 입력 bob은 갈라집니다. 이것이 조회 테이블(lookup table)(함수 — bob의 기관을 물으면 답이 하나 나옵니다)과 일반적인 화살표들의 그물망(관계 — bob이 누구를 지도하는지 물으면 집합이 나옵니다) 사이의 차이입니다. 각 관계에 대해 is_function을 평가하면 다음과 같이 일치합니다.

is_function(affiliated) = True
is_function(advises)    = False

이 구분을 분명히 해 두어야 합니다. 왜냐하면 이 장의 끝에서 얻게 될 결론이 임베딩은 함수다라는 것이고, 함수야말로 기호에서 하나의 벡터로 가는 조회로 바꿀 수 있는 바로 그런 종류의 관계이기 때문입니다. 세는 김에 덧붙이자면, People에서 Institutions로 가는 전역 함수의 개수는 $\lvert \text{Institutions} \rvert^{\lvert \text{People} \rvert} = 2^{5} = 32$개입니다: 다섯 사람 각각이 두 학교 중 하나로 보내지는, 다섯 번의 독립적인 이항 선택이기 때문입니다. affiliated는 그 서른두 가지 중 하나입니다.

합성과 추이적 폐쇄

두 가지 연산이 이 정적인 집합들을 추론으로 바꾸어 놓습니다. 첫 번째는 합성(composition)입니다. 두 관계를 합성한다는 것은 그것들을 사슬처럼 잇는 것입니다: R을 따라 a에서 어떤 중간 지점 b로 간 다음, S를 따라 b에서 c로 나아가서 지름길 (a, c)를 기록합니다. R ∘ S로 쓰고 "R을 한 다음 S를 한다"라고 읽습니다(일부 문헌은 오른쪽 사상이 먼저 작동하는 함수 합성에 맞추기 위해 이 똑같은 사슬을 S ∘ R, 즉 뒤 관계가 먼저 오는 방식으로 씁니다. 우리는 코드와 맞추기 위해 왼쪽에서 오른쪽으로 "하고-그다음에"라고 읽는 순서를 씁니다). 이는 다음과 같은 집합입니다(중간 원소를 위해 ∃를 도입하며, "존재한다"라고 읽습니다).

$$R \circ S \;=\; \{\, (a, c) \;\mid\; \exists b\ \big((a, b) \in R \ \wedge\ (b, c) \in S\big) \,\},$$

이는 정확히 sets_relations.py의 compose(22–24번째 줄)입니다 [4].

def compose(R: set, S: set) -> set:
    """Relational composition R ∘ S = {(a, c) | (a, b) ∈ R and (b, c) ∈ S}."""
    return {(a, c) for (a, b) in R for (b2, c) in S if b == b2}

advises를 그 자신과 합성하면 얻어지는 지름길들은 정확히 kb.py의 grandAdvisor 규칙(79번째 줄)과 일치하는 grand-advisor 링크입니다. 여기 손으로 계산한 전체 과정이 있습니다. 시작하는 순서쌍을 하나씩 가져와서, 각 (a, b) ∈ advises에 대해 (b, c) ∈ advises인 모든 것을 찾아 (a, c)를 만들어냅니다.

advises에서 가져온 (a, b)	advises에서 일치하는 (b, c)	방출되는 지름길 (a, c)
(alice, bob)	(bob, carol), (bob, dave)	(alice, carol), (alice, dave)
(bob, carol)	(carol, erin)	(bob, erin)
(bob, dave)	없음(dave는 아무도 지도하지 않음)	—
(carol, erin)	없음(erin은 아무도 지도하지 않음)	—

세 개의 지름길이 살아남고, 프로그램은 정확히 그것들을 출력합니다.

advises ∘ advises (grand-advising): [('alice', 'carol'), ('alice', 'dave'), ('bob', 'erin')]

alice는 (bob을 거쳐) carol과 dave를 grand-advise하고, bob은 (carol을 거쳐) erin을 grand-advise합니다: 이 순서쌍들은 advises가 결코 담고 있지 않던 것들이며, 사슬 잇기를 한 라운드 돌려서 만들어낸 것입니다.

두 번째 연산은 추이적 폐쇄(transitive closure)입니다: 주어진 관계를 포함하는 가장 작은 추이적 관계이며, 달리 말하면 "화살표를 한 번 이상 따라가서 도달할 수 있는 모든 것"입니다. $R$을 그 자신과 $k$번 합성한 관계를 $R^k$로 쓰면($R^1 = R$, $R^2 = R \circ R$, 이런 식으로 계속됩니다), 폐쇄란 모든 홉(hop) 수에 대한 합집합입니다.

$$R^{+} \;=\; R \cup R^{2} \cup R^{3} \cup \cdots \;=\; \bigcup_{k \geq 1} R^{k}.$$

무한히 많은 항을 실제로 더할 수는 없지만, 유한한 관계에서는 그럴 필요가 전혀 없습니다: 한 라운드에서 새로운 순서쌍이 하나도 추가되지 않으면, 그 이후의 모든 라운드에서도 아무것도 추가되지 않으므로 합집합은 안정됩니다. 이것이 바로 transitive_closure가 하는 일입니다(27–36번째 줄) [4].

def transitive_closure(R: set) -> set:
    """Smallest transitive relation containing R (reachability). Computed by
    repeatedly adding composed pairs until a fixpoint — the same "iterate to a
    limit" idea as forward chaining, one relation at a time."""
    closure = set(R)
    while True:
        added = compose(closure, R) - closure
        if not added:
            return closure
        closure |= added

added = compose(closure, R) - closure라는 줄은 정확히 새로운 순서쌍들(한 홉을 더 간 compose(closure, R)에서 이미 가지고 있는 것을 뺀 것)을 계산합니다. |=는 그것들을 접어 넣습니다. 이 루프는 아무것도 새로 나타나지 않는 라운드에서 멈춥니다. 이를 두 순서쌍 (p2, p1)과 (p3, p2)를 가진 cites에 대해 추적해 봅시다.

라운드	시작 시점의 closure	compose(closure, cites)의 새 순서쌍	이후의 closure
1	{(p2,p1), (p3,p2)}(크기 2)	(p3, p2)가 (p2, p1)에 도달 ⟹ (p3, p1) 추가	{(p2,p1), (p3,p1), (p3,p2)}(크기 3)
2	{(p2,p1), (p3,p1), (p3,p2)}(크기 3)	한 홉 확장이 모두 이미 존재 ⟹ ∅	변화 없음 — 고정점, return

라운드 1에서 자신의 끝점이 다른 인용으로 이어지는 유일한 순서쌍은 (p3, p2)이고, p2는 p1을 인용하므로 (p3, p1)이 태어납니다. 라운드 2에서는 새로운 것이 전혀 만들어질 수 없습니다(p1은 아무것도 인용하지 않으므로 사슬이 그 너머로 확장되지 않습니다). added는 비어 있고 루프는 반환됩니다. 프로그램은 이 고정점을 출력합니다.

transitive closure of cites: [('p2', 'p1'), ('p3', 'p1'), ('p3', 'p2')]

두 개의 순서쌍이 폐쇄되어 세 개가 되었으며, 새로 온 것은 ('p3', 'p1')입니다: p3는 p1을 직접 인용한 적이 없지만 p2를 거쳐 p1에 도달합니다. 이는 정확히 kb.py의 재귀 규칙 citesTransitively(86–88번째 줄)가 계산하는 것이며, "아무것도 새로 나타나지 않을 때까지 반복한다"는 이 루프는 전방 연쇄(forward chaining)가 지식베이스 전체에 대해 돌리는 것과 똑같은 고정점까지 반복(iterate-to-a-fixpoint) 엔진입니다. 거기서는 kb.py의 23개 기본 사실이 몇 번의 파도를 거치며 늘어나다가, 파생된 사실들이 더는 바뀌지 않을 때 멈춥니다. 이 장치 전체가 고정점: 극한에 도달하는 것으로서의 추론 장의 주제이며, 여기서는 이미 그것을 관계 하나에 대해 열 줄로 미리 맛본 것입니다. 이 모듈의 시연 블록(sets_relations.py, 61–67번째 줄)을 실행하면 네 가지 결과가 한 번에 모두 나오는데, 그 실제 출력은 다음과 같습니다.

advises ∘ advises (grand-advising): [('alice', 'carol'), ('alice', 'dave'), ('bob', 'erin')]
transitive closure of cites: [('p2', 'p1'), ('p3', 'p1'), ('p3', 'p2')]
affiliated is a function: True
advises is transitive: False

이 네 줄을 천천히 읽어보십시오. 이것이 바로 이 장의 축소판이기 때문입니다: 합성은 grand-advisor 지름길을 만들고, 폐쇄는 인용 도달가능성을 만들며, affiliated는 단일값 검사를 통과하고, advises는 추이성 검사에 실패합니다 — 이는 우리가 손으로 논증했던 두 가지 모양 주장이 이제 기계에 의해 확인된 것입니다.

뉴로-심볼릭 AI가 이 토대 위에 서 있는 이유

이 어휘는 준비 운동이 아닙니다. 이는 이 시리즈가 다루는 분야의 양쪽 절반이 공유하는 공통 토대입니다. 심볼릭(symbolic) 쪽에서 보면, 지식 그래프(knowledge graph) — 이름표가 붙은 네트워크로 그려진 사실들의 데이터베이스 — 는 관계-트리플(relation-triple)들의 집합 그 자체입니다: 모든 엣지는 advises의 순서쌍들과 정확히 똑같이 어떤 유형화된 관계의 멤버입니다. 그 그래프 위에서의 추론은 관계 대수(relation algebra)이며, 방금 우리가 실행한 두 연산에 지나지 않습니다. grand-advisor를 유도하는 것은 합성이고, 어떤 논문이 추이적으로 인용하는 모든 것을 찾는 것은 추이적 폐쇄입니다. 2부의 엔진들은 이것을 대규모로 수행할 뿐, 이 장이 이미 이름 붙이지 않은 어떤 것도 하지 않습니다 [5].

뉴럴(neural) 쪽에서 보면, 임베딩(embedding) — 뉴로-심볼릭(neuro-symbolic)에서 "뉴로"에 해당하는 다리 — 은 기호에서 벡터로 가는 함수입니다: 각 개체(alice, p1, mit)를 연속 공간 안의 한 점으로 보내며, 결코 갈라지지 않습니다 — 이는 방금 우리가 정의하고 검사한 단일값 약속 그대로입니다. 임베딩을 흥미롭게 만들고 이후의 권들을 이끌어가는 것은, 우리가 그 함수가 구조를 보존하기를 바란다는 점입니다. 그래서 그래프 안에서 관계를 합성하는 것이 벡터에 대한 어떤 깔끔한 연산에 대응하게 됩니다. 되풀이해서 등장하는 목표 모델은 평행이동(translational) 임베딩 모델이며, 여기서는 관계가 고정된 벡터이고 어떤 트리플이 성립한다는 것은 머리 벡터에 관계 벡터를 더한 결과가 꼬리 벡터 근처에 놓인다는 뜻입니다. 그 모델에서는, 우리가 끝점이 일치하는 순서쌍들을 이어서 계산했던 합성 advises ∘ advises가 두 관계 벡터의 덧셈으로 다시 나타납니다 [6]. 이렇게 해서 집합, 관계, 함수는 논리학자의 증명과 신경망의 벡터 연산 양쪽 모두를 적어놓고 비교할 수 있는 공통 언어가 되며, 양쪽 모두가 서 있는 토대가 됩니다.

아직 풀리지 않은 부분

여기 이 토대에 있는 솔직한 균열이 있습니다. 관계는 딱 떨어집니다(crisp): 어떤 순서쌍은 advises 안에 있거나 없거나 둘 중 하나이며, 소속(membership)은 $0$이거나 $1$이고 그 사이는 없습니다 — 이것이 바로 is_function과 is_transitive가 깔끔한 불리언(Boolean) 값을 반환할 수 있는 이유입니다. 그러나 우리가 추론하고 싶어 하는 것들 중 상당수는 등급이 있고 불확실합니다. 반쯤 끝난 공동 지도(co-supervision)는 advising 링크일까요? 모델이 80퍼센트 확신하는 인용은 cites의 멤버로 쳐야 할까요? 집합론적인 답은 인정사정없습니다: 들어있거나 아니거나, 다이얼 같은 것은 없습니다. 이 딱 떨어짐(crispness)은 증명에 있어서는 강점입니다 — 바로 이것이 추이성을 한 번에 계산할 수 있는 예/아니오 성질로 만들어주는 것입니다 — 하지만 세상이 모호한 곳이라면, 즉 대부분의 곳에서는 진짜 한계이기도 합니다.

뉴로-심볼릭 프로그램은, 합성과 추이성과 함수 약속이라는 이 딱 떨어지는 관계들의 구조는 그대로 유지하면서, 소속만은 딱딱한 $0/1$에서 $0$과 $1$ 사이 전체 구간에 걸친 부드럽고 학습 가능한 숫자로 완화하려는 하나의 길고 긴 시도로 읽을 수 있습니다 — 이는 자데(Zadeh)가 형식화한 등급적 소속의 발상입니다 [7]. 하지만 일단 소속이 실수(real number)가 되면, 그 깔끔한 정리들은 흔들리기 시작합니다: "0.8만큼 참"인 두 순서쌍의 합성은 어느 정도로 참이며, 모든 화살표가 가중치를 지닐 때도 추이성은 여전히 유일한 고정점으로 닫힐까요? 기호를 유용하게 만들었던 바로 그 구조가 그런 완화를 거치고도, 슬그머니 무너지지 않고 살아남을 수 있는지는 아직 정해지지 않았습니다 — 이것이 바로 이 시리즈의 나머지 부분이 계속 맴도는 열린 질문입니다.

왜 중요한가

앞으로 등장할 모든 형식적 대상은 이 세 가지 중 하나가 변장한 것입니다: 논리적 술어(predicate)는 관계이고, 어떤 논리식(formula)을 참으로 만드는 해석(interpretation)은 원자(atom)들의 집합이며, 변수 할당(variable assignment)은 변수에서 개체로 가는 함수입니다. 격자(lattice)는 특별한 관계로 순서 지어진 집합이 될 것이고, 전방 연쇄(forward chaining) 유도는 고정점까지 자라나는 관계가 될 것이며, 임베딩과 그래프 신경망(graph neural network)은 관계의 정점(vertex) 위의 함수가 될 것입니다. advises를 스물다섯 쌍 중 네 쌍의 집합으로, grand-advising을 그것들의 합성으로, affiliated를 단일값 함수로 볼 수 있다면, 이어지는 모든 장의 표기법은 이미 절반은 읽은 셈입니다: 추상화는 이보다 더 이국적으로 변하는 법이 없으며, 그저 더 높이 쌓일 뿐입니다.

핵심 용어

• 집합(Set) — 서로 구별되는 원소들의 순서 없는 모음입니다. 같음은 외연성(같은 멤버를 가짐)으로 정해지고, 소속(∈)은 전부이거나 전무이며, 크기 $\lvert A \rvert$는 멤버의 수를 세고, 공집합 ∅은 아무것도 없는 집합입니다.
• 부분집합(Subset, A ⊆ B) — $\forall x\,(x \in A \rightarrow x \in B)$입니다. 아무도 이름을 대지 않고 "모든 교수는 사람이다"라고 말하는 방법이며, ∅이 모든 것의 부분집합인 이유이기도 합니다.
• 순서쌍(Ordered pair, (a, b)) — 두 자리를 가진 대상으로, $(a,b)=(c,d) \Leftrightarrow a=c \wedge b=d$라는 특징적 성질을 가지며, $\{\{a\},\{a,b\}\}$로 집합만으로 만들어집니다. 그래서 (alice, bob)은 (bob, alice)와 다릅니다.
• 데카르트 곱(Cartesian product, A × B) — 첫 번째는 A에서, 두 번째는 B에서 가져온 모든 순서쌍의 집합입니다. $\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert$이므로, People × People은 25개의 순서쌍을 갖습니다.
• 관계(Relation) — 데카르트 곱의 부분집합입니다. People 위에는 $2^{25}$개의 관계가 있으며, advises는 지식베이스에서 읽어낸 4개의 순서쌍으로 이루어진 하나의 구체적인 관계입니다.
• 반사적 / 대칭적 / 추이적(Reflexive / symmetric / transitive) — 모든 $x$에 대해 $(x,x)\!\in\!R$; $(a,b)\!\in\!R \Rightarrow (b,a)\!\in\!R$; $(a,b),(b,c)\!\in\!R \Rightarrow (a,c)\!\in\!R$. advises는 이 세 가지 중 어느 것도 갖고 있지 않으며, colleague는 대칭적입니다.
• 함수(Function) — 모든 입력이 정확히 하나의 출력을 갖는 전역 단일값 관계입니다. $\big((a,b),(a,b')\in R\big) \Rightarrow b=b'$는 단일값 조건이며, 이 조건을 만족하지만 모든 입력을 포함하지는 않는 관계는 부분 함수입니다. $f:A\to B$, $a \mapsto b$로 쓰며, affiliated는 함수이지만 advises는 bob이 두 학생을 지도하므로 함수가 아닙니다.
• 합성(Composition, R ∘ S) — $\{(a,c) \mid \exists b\,((a,b)\in R \wedge (b,c)\in S)\}$입니다. advises를 그 자신과 합성하면 세 개의 grand-advisor 순서쌍이 나옵니다.
• 추이적 폐쇄(Transitive closure, $R^{+}$) — $R$을 포함하는 가장 작은 추이적 관계, $\bigcup_{k\ge 1} R^k$입니다. 도달가능성이며, 고정점에 이를 때까지 지름길을 더해 계산합니다(cites는 2개의 순서쌍에서 3개로 폐쇄되며, ('p3','p1')을 얻습니다).
• 지식 그래프(Knowledge graph) — 유형화된 관계-트리플들의 집합입니다. 추론이 합성하고 폐쇄하는 심볼릭 대상입니다.
• 임베딩(Embedding) — 기호에서 벡터로 가는 함수이며, 이상적으로는 관계 구조를 보존합니다. 이 시리즈를 뉴로-심볼릭으로 만들어주는 신경(neural) 쪽 다리입니다.

이 다음으로 이어지는 것

이제 우리에게는 명사, 화살표, 단일값 매핑이 갖추어졌습니다 — 사물들이 서로 관계를 맺고 있다는 것은 말할 수 있지만, 아직 무엇이 다른 무엇보다 더 상위에 있는지는 말할 수 없습니다. 다음 장인 순서와 격자: 사물에 서열이 있을 때는 반사적이고 추이적이며 결코 되돌아가지 않는 특별한 관계들의 부류를 다루며, 이들이 어떻게 위계(hierarchy) — 더 크고 더 작음, 더 일반적이고 덜 일반적임, 바닥과 꼭대기 — 를 부여하는지 보여줍니다. 그 순서 매김의 장치야말로 "모든 교수는 연구자이고 연구자는 사람이다"라는 사슬을 추론자가 실제로 타고 오를 수 있는 진짜 사다리로 만들어주며, 이는 이 권 전체의 논리가 조용히 그 위에 세워지는 구조입니다.