[Set Theory] [1-2] Building Classes

1.2 Building Classes

0. Introduction

이제부터는 본격적으로 공리적 집합론(axiomatic set theory)을 시작한다. 1.1에서 “문장(sentence)”과 논리 연산을 준비했다면, 1.2에서는 이 논리 언어 위에 올려놓을 기본 대상을 정한다. 그 기본 대상이 바로 클래스(class)이다.

이 섹션의 핵심 목표는 다음과 같다.

• “클래스(class)”와 “원소(element)”를 정의 없이 기본 개념으로 받아들이기
• “집합(set)”과 “진클래스(proper class)”의 구분 직관 잡기
• 클래스를 비교하는 기본 관계들: 동등(equal), 포함(subclass / subset) 정리
• 공리로부터 클래스를 만드는 법(class construction)을 명시하기
• 합집합, 교집합, 공집합, 전체 클래스, 여집합 같은 기본 연산을 클래스 수준에서 도입하기

이걸 이해하면, 뒤에서 나오는 “집합”, “자연수 집합”, “순서수/기수” 등을 모두 클래스 위에 쌓이는 구조로 볼 수 있다.

[[picture : 기하학 공리계와 집합론 공리계를 비교하는 그림. 왼쪽에는 ‘점(point), 직선(line), 포함관계(incidence)’를 기본 기호로 둔 그림, 오른쪽에는 ‘클래스(class), 원소 관계 $\in$’를 기본 기호로 둔 그림을 나란히 배치]]

---

1. 핵심 정의 및 개념

1.1 공리계와 ‘정의되지 않는 말’

공리적 이론을 만들 때는 항상 정의하지 않고 그냥 쓰는 말이 필요하다.

• 유클리드 기하학에서는 “점(point)”, “직선(line)”, “사이에 있다(incidence)”가 그런 예이다.
• 집합론에서는 이 역할을 클래스(class)와 원소 관계(membership relation) $\in$가 맡는다.

이 책에서의 규칙은 다음과 같다.

• 이론 안에서 다루는 모든 대상은 클래스(class)라고 부른다.
• 이들 중 일부는 나중에 집합(set)으로 정의된다.
• 집합이 아닌 클래스는 진클래스(proper class)라고 부른다.

직관적으로는 이렇게 이해할 수 있다.

• “클래스” = 어떤 조건을 만족하는 객체들의 모임(컬렉션)
• “집합” = 그중에서 크기가 ‘적당히 작은’ 것들
• “진클래스” = “모든 집합들의 모임”처럼 너무 큰 것들

이 구분은 러셀의 역설 같은 모순을 피하기 위한 핵심 장치이다.

[[picture : 전체 ‘클래스 세계’를 큰 직사각형으로 그리고, 그 안에 여러 개의 동그라미를 ‘집합들’로 표시. 직사각형 전체(모든 집합과 다른 객체들의 모임)를 ‘진클래스’로 강조해서 보여주는 그림]]

1.2 원소(element)와 기호 규칙

두 클래스 $x, A$가 있을 때,

• $x \in A$ : “$x$는 $A$의 원소(element)이다.”
• $x \notin A$ : “$x$는 $A$의 원소가 아니다.”

여기서 “원소”라는 말도 정의하지 않고 사용한다. 대신 다음처럼 규정한다.

어떤 클래스 $x$가 어떤 클래스 $A$의 원소로 등장할 수 있다면, 우리는 $x$를 “원소(element)”라고 부른다.

표기 관례(매우 중요):

• 소문자 $x, y, z, a, b, c, \dots$ : 항상 원소를 나타내는 데만 사용
• 대문자 $A, B, C, \dots$ : 클래스 전체를 나타내는 기호로 사용

즉, $A$는 “어떤 클래스”일 수 있고, $x$는 “반드시 어떤 클래스의 원소가 될 수 있는 대상”으로 생각한다.

1.3 클래스의 동등성: $A = B$

두 클래스 $A, B$가 있을 때, 동일한 클래스로 보려면 무엇이 같아야 할까? 집합론에서는 아주 자연스럽게, “같은 원소들을 가지고 있으면 같다”고 정한다.

정의(클래스의 동등성):

$$A = B \quad\Longleftrightarrow\quad \forall x \; (x \in A \iff x \in B).$$

즉, 모든 원소 $x$에 대해 “$x$가 $A$에 속하는지”와 “$x$가 $B$에 속하는지”가 항상 동시에 참/거짓이면 두 클래스는 같다.

“모양이 어떻게 생겼는지”는 중요하지 않고, 어떤 원소들을 포함하느냐만이 클래스를 결정한다는 철학이다.

1.4 공리 A1: 외연성(extensionality)의 공리

직관적으로, “같은 원소들을 가지면 같은 클래스”라는 아이디어는 다음과 같은 성질도 당연히 만족해야 한다.

$x = y$이고 $x \in A$라면, $y \in A$이어야 한다.

이것이 첫 번째 공리 A1 (외연성의 공리, axiom of extent)이다.

• “같은 대상”이라면, 어떤 클래스에 속하는지 여부도 완전히 같아야 한다.
• 특히, 같은 대상 사이에서는 원소 관계 $\in$를 자유롭게 치환할 수 있다.

이 공리는 나중에 “동치 관계”, “동형(isomorphism)” 등의 개념에서도 반복해서 나타나는 “같은 것에 대해 동일하게 취급한다”는 원칙과 연결된다.

1.5 서브클래스(subclass)와 부분집합(subset)

두 클래스 $A, B$를 비교하는 가장 기본적인 관계는 포함 관계다.

정의(부분클래스 / 서브클래스):

$$A \subseteq B \quad\Longleftrightarrow\quad \forall x \; (x \in A \Rightarrow x \in B).$$

• $A \subseteq B$ : “$A$의 원소는 모두 $B$의 원소다” → $A$는 $B$의 부분클래스(subclass)
• $A \subset B$ (또는 $A \subsetneq B$) : $A \subseteq B$이면서 $A \ne B$ → 진부분클래스(strict subclass)

여기서 중요한 점:

• 클래스 수준의 포함이므로, $A, B$는 꼭 “집합(set)”일 필요가 없다.
• 나중에 “집합(set)” 개념을 정의한 뒤에는 “$A$가 집합이고 $A \subseteq B$이면, $A$를 $B$의 부분집합(subset)이라고 부른다.”라고 정한다.

즉, “부분클래스(subclass)”는 클래스 일반에 대한 포함 관계이고, “부분집합(subset)”은 집합인 클래스에 대해서만 쓰는 용어이다.

1.6 Theorem 1.11: 동등성과 포함의 기본 성질

모든 클래스 $A,B,C$에 대해 다음이 성립한다.

1. $A = A$ (반사성, reflexivity)
2. $A = B$이면 $B = A$ (대칭성, symmetry)
3. $A = B$이고 $B = C$이면 $A = C$ (추이성, transitivity)
4. $A \subseteq B$이고 $B \subseteq A$이면 $A = B$
5. $A \subseteq B$이고 $B \subseteq C$이면 $A \subseteq C$

즉, “클래스의 동등성(=)”은 동치 관계(equivalence relation)이고, “부분클래스 관계 $\subseteq$”는 반사적, 추이적이며, 양방향 포함이 있으면 두 클래스가 같다.

이 정리의 증명은, 위에서 정의한 “동등”과 “부분클래스” 개념을 그대로 풀어 써서 논리식으로 변환하고, 1.1에서 배운 논리 규칙들을 적용하면 된다.

1.7 공리 A2: 클래스 구성(class construction)의 공리

직관적으로 우리는 “조건 $P(x)$를 만족하는 모든 원소의 모임”으로 클래스를 만든다.

예:

• “짝수 정수들의 모임”
• “실수 중에서 $x^2 < 2$를 만족하는 것들의 모임”

공리 A2는 이런 직관을 정확하게 허용하는 범위를 정해 준다.

$P(x)$가 우리가 사용하는 논리 기호와 변수들만으로 표현된 문장이라면, $P(x)$를 만족하는 모든 원소 $x$들로 이루어진 클래스를 항상 만들 수 있다.

기호로는 보통

$$\{x \mid P(x)\}$$

처럼 쓴다.

여기서 중요한 제한:

• $P(x)$는 원소 $x$에 대한 조건이어야 한다.
• $P(x)$는 $\in, \land, \lor, \lnot, \Rightarrow, \exists, \forall$와 괄호, 변수들만으로 표현되어야 한다.

이 제한이 바로 러셀의 역설 같은 모순을 막아 준다. 즉, “모든 클래스를 모아놓은 클래스” 같은 과도한 대상은 공리 A2로는 만들 수 없게 설계되어 있다.

1.8 합집합, 교집합, 전체 클래스, 공집합

공리 A2(클래스 구성 공리)를 이용하면 다양한 클래스를 “조건으로부터” 만들 수 있다.

1. 합집합(union)

   두 클래스 $A, B$의 합집합은

   $$A \cup B = \{x \mid x \in A \text{ 또는 } x \in B\}$$

   로 정의한다. (둘 중 하나라도 원소로 포함하면 된다.)

2. 교집합(intersection)

   교집합은

   $$A \cap B = \{x \mid x \in A \text{ 그리고 } x \in B\}$$

   로 정의한다.

3. 전체 클래스(유니버설 클래스, universal class)

   모든 원소를 전부 모은 클래스를 $\mathcal{U}$로 쓰자.

   $$\mathcal{U} = \{x \mid x = x\}$$

   “자기 자신과 같은 것”이라는 조건은 모든 대상이 만족하므로, 이 클래스는 “모든 원소 전체”가 된다.

4. 공집합(empty class)

   원소가 하나도 없는 클래스를 $\varnothing$ 또는 $\emptyset$ 으로 쓴다.

   $$\varnothing = \{x \mid x \ne x\}$$

   $x \ne x$를 만족하는 원소는 없기 때문에, 이 클래스에는 원소가 전혀 없다.

이 네 가지는 앞으로 집합론 전체의 기본 재료가 된다.

[[picture : 두 클래스 $A, B$를 원으로 표시하고, 각각의 벤 다이어그램에서 (1) 합집합 $A \cup B$ 영역, (2) 교집합 $A \cap B$ 영역, (3) 전체 직사각형을 $\mathcal{U}$로 두고 그 안에서 $A$의 여집합 $A'$ 영역을 차례로 음영 처리한 세 개의 그림]]

1.9 공리에서 나오는 간단한 정리: $\varnothing \subseteq A$, $A \subseteq \mathcal{U}$

모든 클래스 $A$에 대해

1. $\varnothing \subseteq A$
2. $A \subseteq \mathcal{U}$

가 성립한다.

직관적으로는 다음과 같이 이해할 수 있다.

• $\varnothing \subseteq A$ : 공집합에는 원소가 없으므로, “$x \in \varnothing$이면 $x \in A$”는 항상 참이다. (전건이 거짓)
• $A \subseteq \mathcal{U}$ : $A$의 원소는 모두 “어떤 원소”이므로, “세계의 모든 원소를 모은 클래스” $\mathcal{U}$에 반드시 포함된다.

1.10 서로소(disjoint)와 여집합(complement)

1. 서로소(disjoint)

   두 클래스 $A, B$가 한 원소도 공유하지 않으면 서로소라고 한다.

   $$A \cap B = \varnothing$$

2. 여집합(complement)

   전체 클래스 $\mathcal{U}$를 기준으로, $A$에 속하지 않는 모든 원소들의 클래스를 $A$의 여집합이라고 한다.

   $$A' = \{x \mid x \notin A\}$$

   직관적으로 $\mathcal{U}$에서 $A$를 뺀 나머지 영역이다.

[[picture : 전체 직사각형을 $\mathcal{U}$로 두고, 안에 원 $A$와 원 $B$를 그린 뒤, (1) $A$와 $B$가 겹치지 않을 때(서로소)의 벤 다이어그램, (2) $A'$를 직사각형에서 $A$를 제외한 영역으로 채운 그림]]

---

2. 중요한 정리 / 원리 / 아이디어

1. “대상을 어떻게 볼 것인가?”의 전환

   • 직관적 집합론에서는 “어떤 객체들의 모임”을 무심코 집합이라고 부르다가 러셀의 역설 같은 모순을 만난다.
   • 여기서는 “클래스”를 기본으로 두고, 그중 일부만 “집합”으로 인정한다.
   • “너무 큰 모임” = 진클래스(proper class)로 따로 분류하여, 직접 집합 연산의 대상으로 쓰지 않는다.

2. 외연성(extensionality)의 철학

   • 클래스는 “원소의 목록”으로 완전히 결정된다.
   • “같은 원소 집합을 가지면 같은 클래스”가 된다.
   • 이 철학 때문에 집합론은 “내부 구조” 대신 “소속 관계 $\in$만으로 세계를 설명하는 이론”이 된다.

3. 클래스 구성 공리(A2)와 그 제한

   • 조건 $P(x)$에 따라 클래스를 만드는 것은 허용한다.
   • 그러나 $P$는 반드시 “원소에 대한 논리식”이어야 하고, 허용된 기호만 써야 한다.
   • 이 미묘한 제한 덕분에, “모든 클래스의 클래스” 같은 위험한 대상을 만들 수 없고, 결과적으로 대부분의 고전적 패러독스가 차단된다.

4. 합집합, 교집합, 전체/공집합, 여집합이 모두 ‘조건으로부터’ 나온다

   • $A \cup B$ : “$x\in A$ 또는 $x\in B$”라는 조건
   • $A \cap B$ : “$x\in A$ 그리고 $x\in B$”라는 조건
   • $\mathcal{U}$ : “$x = x$”라는 조건
   • $\varnothing$ : “$x \ne x$”라는 조건
   • $A'$ : “$x\notin A$”라는 조건

   결국 집합 연산은 모두 논리식의 조합으로 이해할 수 있다.

---

3. 예제와 reasoning 과정

예제 1: “클래스의 동등성” 증명 맛보기

정리: $A \subseteq B$이고 $B \subseteq A$이면 $A = B$.

증명 스케치:

• $A \subseteq B$이므로, 임의의 원소 $x$에 대해 $x\in A \Rightarrow x\in B$.
• $B \subseteq A$이므로, $x\in B \Rightarrow x\in A$.
• 따라서 모든 $x$에 대해 $x\in A$와 $x\in B$가 서로 함의한다. 즉, $x\in A \iff x\in B$.
• 그러므로 정의에 의해 $A=B$.

이 증명은 전형적인 집합론 방식이다: “정의”를 논리식으로 풀어 쓰고, $\Rightarrow$와 $\iff$로 차분히 연결한다.

예제 2: Russell 클래스는 왜 “진클래스”인가? (직관)

고전적인 역설의 주인공인

$$R = \{x \mid x \notin x\}$$

를 생각해 보자. 직관적으로는 “자기 자신을 원소로 갖지 않는 모든 것들의 모임”이다.

질문: $R \in R$인가?

• 만약 $R \in R$라면, 정의상 $R \notin R$이어야 한다. (모순)
• 반대로 $R \notin R$라면, 정의상 $R \in R$이어야 한다. (또 모순)

그래서 $R$을 “집합”으로 취급하면 공리계가 무너진다. 이런 이유로, 이런 종류의 “너무 큰 클래스”는 진클래스(proper class)로 분류하고 “원소가 될 수 없다”고 보는 것이 현대 공리적 집합론의 관점이다.

예제 3: 합집합/교집합 정의를 그대로 쓰는 연습

두 클래스 $A, B$에 대해 다음을 직접 정의에서 확인해 보자.

$x \in A\cap B$ 이면 $x\in A$이고 $x\in B$이다.

정의에 따르면

$$A \cap B = \{x \mid x \in A \text{ 그리고 } x \in B\}.$$

따라서 “$x\in A\cap B$”라는 말은 “$x\in A$이고 $x\in B$이다”라는 말과 완전히 같다. 반대로, $x\in A$이고 $x\in B$이면 곧바로 $x\in A\cap B$이다.

이렇게, 기호 정의를 자연어로 풀어 읽고 다시 기호로 되넣는 작업이 집합론에서 가장 기본적인 ‘문제 풀이 패턴’이다.

예제 4: 분배법칙 $A \cap (B \cup C) = (A\cap B)\cup (A\cap C)$ 직관

이 등식은 이후 섹션에서 본격적으로 다루지만, 이 섹션의 도구만으로도 충분히 이해할 수 있다.

• 왼쪽: $A$ 안에 있으면서, 동시에 $B$나 $C$ 중 하나에 있는 원소 → “$A$에 있고, $B$ 또는 $C$에 있다”
• 오른쪽: “$A$에 있으면서 $B$에 있거나” 또는 “$A$에 있으면서 $C$에 있는” 원소 → “($A$와 $B$ 모두에 있는 원소) 또는 ($A$와 $C$ 모두에 있는 원소)”

논리식으로 쓰면

$$x \in A \cap (B \cup C) \quad\iff\quad x\in A \land (x\in B \lor x\in C)$$

인데, 논리의 분배법칙에 따라

$$x\in A \land (x\in B \lor x\in C) \quad\iff\quad (x\in A \land x\in B) \lor (x\in A \land x\in C),$$

즉,

$$x\in (A\cap B) \lor x\in (A\cap C) \quad\iff\quad x\in (A\cap B)\cup(A\cap C).$$

[[picture : 세 클래스 $A,B,C$를 원 세 개로 그린 뒤, 왼쪽은 $A \cap (B \cup C)$를, 오른쪽은 $(A\cap B)\cup(A\cap C)$를 음영 처리한 두 개의 벤 다이어그램을 나란히 배치. 두 그림에서 음영 영역이 같다는 것을 시각적으로 보여 줌]]

---

4. 응용 또는 컴퓨터공학적 맥락

1) 타입 이론(type theory)과의 유사성

• 프로그래밍 언어에서 “모든 타입의 집합”을 진짜 값으로 가지려고 하면 보통 문제가 생긴다.
• 그래서 실무에서는 “타입의 우주(universe type)”를 조심스럽게 설계한다.
• 이것은 집합론에서 “모든 집합의 모임”을 진클래스로 두고, 집합으로 다루지 않는 것과 매우 비슷한 철학이다.

2) 리스트 컴프리헨션(list comprehension) / SQL WHERE 절

• 파이썬의 [x for x in S if P(x)]
• SQL의 SELECT * FROM T WHERE P(x)

이런 것들은 사실상 공리 A2의 “$\{x \mid P(x)\}$”와 같은 구조다. “조건을 만족하는 원소만 모아서 새로운 컬렉션을 만든다”는 아이디어는 집합론과 프로그래밍 양쪽의 공통 기반이다.

3) 집합 연산 = 논리 연산

• 합집합($\cup$)은 논리식에서 “또는($\lor$)”에 대응
• 교집합($\cap$)은 “그리고($\land$)”에 대응
• 여집합($'$)은 “부정($\lnot$)”에 대응

따라서 집합에 대한 식을 변형하는 것은 사실상 논리식을 변형하는 것과 같다. 이는 비트 연산(bitwise operation), 집합 기반 권한 모델(permissions), 쿼리 최적화 등에서 그대로 나타난다.

---

5. 요약

• 공리적 집합론에서는 클래스(class)와 원소 관계 $\in$를 정의 없이 기본 기호로 사용한다. 집합(set)은 클래스 중 일부이며, 나머지는 진클래스(proper class)이다.
• 클래스의 동등성은 원소가 완전히 같을 때로 정의되고(외연성), 공리 A1은 “같은 대상은 같은 클래스의 원소가 된다”는 대체 가능성을 보장한다.
• 공리 A2(클래스 구성 공리)는 “조건 $P(x)$를 만족하는 모든 원소의 모임”으로 클래스를 만들 수 있게 하지만, 표현 가능한 $P(x)$에 제한을 두어 패러독스를 피한다.
• 이 공리들로부터 합집합, 교집합, 전체 클래스, 공집합, 여집합, 포함 관계 등의 기본 구조가 정의되고, 이는 곧 집합 연산 = 논리 연산이라는 관점을 형성하여 이후 집합론과 컴퓨터공학적 응용의 기반이 된다.