관계와 동치관계

개요 — 동기·문제의식

집합론의 야심은 "수학의 모든 대상은 집합이다"라는 환원주의 프로그램이다. 자연수가 집합으로 구성될 수 있다는 것은(zfc axioms) 비교적 받아들이기 쉽지만, 순서(ordered pair) — "$a$ 가 먼저, $b$ 가 나중"이라는 비대칭적 정보 — 까지 집합만으로 부호화할 수 있을까? 집합 $\{a,b\}$ 자체는 순서가 없다($\{a,b\}=\{b,a\}$). 이 문제를 푼 것이 1921년 Kuratowski의 영리한 트릭이다. 이 한 가지 정의로부터 관계·함수·순서·동치류 — 수학 전체에서 쓰이는 거의 모든 "구조"가 순수 집합론적으로 재구성된다.

이 페이지는 그 토대 공사를 다룬다: 순서쌍을 어떻게 집합으로 만드는가, 그 위에 관계와 함수를 어떻게 정의하는가, 그리고 이것이 정렬순서·순서수·농도 같은 이후의 모든 개념을 위한 공통 언어가 되는 과정.

직관

순서쌍 $(a,b)$ 를 "$a$ 와 $b$ 를 비대칭적으로 묶는 법"이라고 생각하자. 비대칭성을 만드는 가장 간단한 방법은 "어느 쪽이 더 적게 등장하는가"로 순서를 표시하는 것이다 — Kuratowski의 아이디어가 정확히 이것이다: $\{a\}$ 라는 "한 겹"과 $\{a,b\}$ 라는 "두 겹"을 만들어, 한 겹짜리 안에 든 원소가 "첫 번째"임을 표시한다. $\{\{a\},\{a,b\}\}$ 를 보면, 두 내부 집합의 교집합이 항상 $\{a\}$(첫 원소를 복원)이고, 그 차이가 둘째 원소를 알려준다.

관계는 "두 대상 사이에 어떤 관계가 성립하는가"를 묻는 가장 일반적인 틀이다 — 순서쌍들의 집합일 뿐이다. 함수는 그중 "각 입력에 출력이 정확히 하나"라는 결정론적 제약을 추가한 특별한 관계다. 동치관계는 "구별 안 함"을 형식화하고(같은 동치류 = 같은 것으로 취급), 순서관계는 "더 작음/더 큼"을 형식화한다. 이 셋(관계·함수·순서)이 거의 모든 수학적 구조의 골격이다.

정의

• Kuratowski 순서쌍: $(a,b):=\{\{a\},\{a,b\}\}$.¹ 짝공리를 두 번 적용해 만든 집합.
• 곱집합: $A\times B=\{(a,b):a\in A,b\in B\}$. $A\times B\subseteq\mathcal{P}(\mathcal{P}(A\cup B))$ 이므로 멱집합·분리로 집합임이 보장.
• 관계(relation): $R\subseteq A\times B$. $aRb\iff(a,b)\in R$. $A=B$ 일 때 "$A$ 위의 관계".
• 함수(function): 관계 $f$ 로서, 모든 $a\in\operatorname{dom}(f)$ 에 대해 $(a,b)\in f$ 인 $b$ 가 유일하게 존재 — 이때 $b=f(a)$ 로 쓴다.
• 정의역(domain) $\operatorname{dom}(f)$, 치역(range)(상, image) $\operatorname{ran}(f)$.
• 단사(injective): $f(a)=f(a')\Rightarrow a=a'$. 전사(surjective, onto $B$): $\operatorname{ran}(f)=B$. 전단사(bijective): 둘 다.
• ${}^AB$: $A$ 에서 $B$ 로의 모든 함수의 모임. $A$ 가 순서수일 때 ${}^\alpha B$ 는 "길이 $\alpha$ 의 $B$-값 수열"로도 읽는다.
• 이항관계의 성질: $A$ 위의 관계 $R$ 이 반사적($\forall a,\,aRa$), 대칭적($aRb\Rightarrow bRa$), 반대칭적($aRb\wedge bRa\Rightarrow a=b$), 추이적($aRb\wedge bRc\Rightarrow aRc$)일 수 있다.
• 동치관계(equivalence relation): 반사·대칭·추이. 각 $a$ 에 대해 동치류 $[a]=\{b:aRb\}$ 를 정의하며, 동치류 전체가 $A$ 의 분할(partition)을 이룬다.
• 순서관계: 반사·반대칭·추이($\le$ 류) 또는 비반사·추이($<$ 류) → 부분순서·전순서·정렬순서로 이어짐.

주요 정리

정리 (순서쌍이 well-defined). $(a,b)=(c,d)\iff a=c\wedge b=d$.¹

양쪽 경우 모두 $a=c,\,b=d$. ∎

이 증명이 작동하는 이유가 정의의 핵심이다 — "한 겹"과 "두 겹"의 구별이 본질적으로 첫째·둘째 원소를 구분 가능하게 만든다.

정리 (곱집합은 집합). $A,B$ 가 집합이면 $A\times B$ 도 집합이다.¹

정리 (동치관계 ↔ 분할). 집합 $A$ 위의 동치관계와 $A$ 의 분할(서로소인 비공집합 부분집합들로 $A$ 를 덮는 것) 사이에는 일대일 대응이 있다.

정리 (함수공간의 집합성). $A$ 에서 $B$ 로의 모든 함수의 모임 ${}^AB$ 는 집합이다 (∵ ${}^AB\subseteq\mathcal{P}(A\times B)$, 분리로 함수 조건을 만족하는 것만 추출). 이 사실이 기수 지수 $\kappa^\lambda=|{}^\lambda\kappa|$ 의 정의를 정당화한다.

예제

예제 1 (순서쌍 검증). $(2,3)=\{\{2\},\{2,3\}\}$ 과 $(3,2)=\{\{3\},\{2,3\}\}$ 을 비교하면, 전자의 "한 겹"은 $\{2\}$, 후자는 $\{3\}$ — 서로 다르므로 $(2,3)\ne(3,2)$. 순서가 제대로 부호화됨을 확인.

예제 2 (동치류, 모듈러 산술). $\mathbb{Z}$ 위에서 $a\sim b\iff 3\mid(a-b)$ 는 동치관계(반사: $3\mid0$; 대칭: $3\mid(a-b)\Rightarrow3\mid(b-a)$; 추이: 합이 $3$ 으로 나누어떨어짐). 동치류는 정확히 3개 $[0]=\{\dots,-3,0,3,6,\dots\}$, $[1]$, $[2]$ — 이것이 $\mathbb{Z}/3\mathbb{Z}$ 다. 대수학의 합동(congruence) 개념과 정확히 같은 구조.

예제 3 (함수 개수와 기수 지수의 동기). $|A|=m,|B|=n$ (유한)이면 ${}^AB$ 의 함수 개수는 $n^m$ — 각 $A$ 의 원소마다 독립적으로 $n$ 가지 선택. 이 유한 사실이 무한 기수로 일반화되어 $\kappa^\lambda=|{}^\lambda\kappa|$(cardinal arithmetic)라는 정의의 동기가 된다.

예제 4 (전순서가 아닌 부분순서). $\mathcal{P}(\{1,2\})=\{\varnothing,\{1\},\{2\},\{1,2\}\}$ 에 $\subseteq$ 를 주면 부분순서이지만 전순서는 아니다 — $\{1\}$ 과 $\{2\}$ 는 어느 쪽도 다른 쪽을 포함하지 않아 비교 불가능. 이런 "비교 불가능한 쌍이 있는" 순서가 부분순서의 전형.

예제 5 (관계의 합성). 관계 $R\subseteq A\times B$, $S\subseteq B\times C$ 의 합성 $S\circ R=\{(a,c):\exists b,\,aRb\wedge bSc\}$ 는 $A\times C$ 의 부분집합 — 분리·곱집합으로 집합임이 보장. 함수의 합성도 이 특수한 경우.

예제 6 (Vitali 동치관계의 예고). $\mathbb{R}$ 위에서 $x\sim y\iff x-y\in\mathbb{Q}$ 는 동치관계이며, 그 동치류는 비가산 개(cardinality and countability)다. 각 동치류에서 대표원 하나씩 고르는 일은 선택공리 없이는 불가능하다는 것이 밝혀진다(Vitali 집합) — 동치관계가 단순한 토대 개념을 넘어 AC의 필요성을 드러내는 예.

흔한 오해와 함정

• "순서쌍의 정의는 그냥 표기법일 뿐, 본질적인 게 아니다" — 어떤 의미에선 맞다(다른 인코딩도 가능, 예: $(a,b)=\{a,\{a,b\}\}$ 도 작동). 하지만 어떤 인코딩을 쓰든 $(a,b)=(c,d)\iff a=c\wedge b=d$ 라는 핵심 성질만 만족하면 이론 전개에 차이가 없다 — 중요한 건 인코딩의 세부가 아니라 이 성질이 성립한다는 사실.
• "관계 = 함수"라고 혼동 — 모든 함수는 관계이지만, 관계가 함수이려면 "각 입력에 출력이 유일"이라는 추가 조건이 필요하다. $R=\{(1,2),(1,3)\}$ 은 관계이지만 함수가 아니다($1$ 에 두 출력).
• 동치관계의 세 조건 중 하나만 확인하고 끝내기 — 반사성을 빠뜨리는 실수가 흔하다. 예를 들어 "$x<y$"는 대칭이 아니어서 동치관계가 아니지만, "$x\le y$"는 반대칭이라 동치관계가 아니다(다른 이유로) — 세 조건을 모두 점검해야 한다.
• 단사·전사를 정의역/공역 명시 없이 말하기 — "$f$ 가 전사다"는 항상 어떤 공역에 대해 전사인지를 함께 말해야 의미가 있다. $f:\mathbb{N}\to\mathbb{Z}$, $f(n)=n$ 은 $\mathbb{Z}$ 로의 전사가 아니지만 $\mathbb{N}$ 으로의 전사는 자명하게 다른 이야기.
• 곱집합 $A\times B$ 가 "당연히" 집합이라 여기고 근거를 안 댐 — 토대론적으로는 멱집합·합집합·분리 공리의 조합이 필요한 비자명한 사실이다(zfc axioms).

큰 그림 / 연결

이 페이지의 순서쌍·관계·함수는 집합론 전체의 문법이다. 정렬순서는 특별한 순서관계이고, 거기서 순서수가 "정렬집합의 표준형"으로 정의된다. 농도는 전단사라는 함수 개념으로 정의되고, 기수 지수 $\kappa^\lambda$ 는 함수공간 ${}^\lambda\kappa$ 의 농도다. 더 나아가 초한 재귀로 정의되는 모든 대상(순서수 연산, $V_\alpha$, 알레프)이 결국 "모임 함수"라는 같은 틀을 쓴다. 수학의 다른 분야로 가면, 위상수학의 동치관계(상공간), 대수학의 합동관계(몫구조), 해석학의 함수공간 — 모두 이 페이지에서 형식화한 같은 집합론적 기계 위에 서 있다. Vitali 동치관계가 보여주듯, 단순해 보이는 토대 개념이 선택공리의 필요성을 드러내는 통로가 되기도 한다.

연습문제

1. $(a,b)=(c,d)\iff a=c\wedge b=d$ 를 Kuratowski 정의로 (양쪽 경우를 나누어) 증명하라.
2. $A\times B$ 가 집합임을 멱집합·분리공리로 보여라(힌트: $A\times B\subseteq\mathcal{P}(\mathcal{P}(A\cup B))$).
3. $\mathbb{R}$ 에서 $x\sim y\iff x-y\in\mathbb{Q}$ 가 동치관계임을 보여라.
4. 단사 $f:A\to B$, 단사 $g:B\to A$ 가 모두 존재하면 $A,B$ 사이 전단사가 존재한다는 정리의 이름은?
5. $|{}^{\{0,1\}}A|=|A\times A|$ 임을 보여라.
6. $A$ 위의 동치관계 $\sim$ 에서 동치류들이 $A$ 의 분할을 이룸을 증명하라.
7. 부분순서이지만 전순서가 아닌 구체적인 예를 들고, 비교 불가능한 두 원소를 명시하라.
8. 관계의 합성 $S\circ R$ 이 집합임을 어떤 공리로 보장받는지 설명하라.

관련 개념

• zfc axioms — 순서쌍·곱집합·함수가 집합인 근거
• well orderings — 특별한 순서관계(정렬순서)
• cardinality and countability — 전단사로 농도 정의
• cardinal arithmetic — 함수공간의 농도 $\kappa^\lambda$
• axiom of choice — Vitali류 동치관계에서 대표원 선택