정초 관계

집합론에서 **정초 관계**(整礎關係, well-founded relation)는 (무한히 재귀적이지 않은) 집합의 원소 관계로서 나타낼 수 있는 이항 관계이다. 정초 관계가 주어진 집합 위에서는 **초한 귀납법**(超限歸納法, transfinite induction)과 **초한 재귀**(超限再歸, transfinite recursion)를 사용할 수 있다. 초한 귀납법은 모든 원소가 어떤 성질을 만족시킴을 증명할 때 사용한다. 초한 귀납법에 따르면, 어떤 술어가 모든 원소에 대하여 참임을 보이려면, 주어진 원소 ‘이전’의 모든 원소들에 대하여 참임을 가정한 채로, 그 주어진 원소에 대하여 참임을 보이면 충분하다. 이는 자연수에 대한 수학적 귀납법을 일반화한다. 초한 재귀는 정초 관계가 주어진 집합을 정의역으로 하는 함수를 정의하는 방법이다. 초한 재귀에 따르면, 주어진 원소의 함숫값을 그 ‘이전’의 원소들의 함숫값들로부터 결정하는 방법(#초한 귀납법에서의 함수 g)이 정해졌을 때, 모든 원소에 대한 함숫값은 유일하게 결정된다.
# 정의
집합 X 위의 이항 관계 R\subseteq X^2에 대하여 다음 다섯 조건이 서로 동치이며, 이를 만족시키는 이항 관계를 **정초 관계**라고 한다.url-status=dead98, Definition III.3.1 * 임의의 부분 집합 \varnothing\ne S\subseteq X에 대하여, \forall s\in S\colon (s,m)\not\in R인 m\in S가 존재한다. * 다음 조건을 만족시키는 열 (x_i)_{i=0}^\infty\subseteq X이 존재하지 않는다. ** 임의의 i\in\mathbb N에 대하여, (x_{i+1},x_i)\in R * 다음 조건을 만족시키는 정렬 전순서 집합 (Y,\le)과 단사 함수 f\colon X\to Y가 존재한다.zbl=0819.04002352, Appendix B ** 임의의 x,y\in X에 대하여, (x,y)\in R\implies f(x) * (모스토프스키 붕괴 정리) 다음 조건을 만족시키는 집합 M과 단사 함수 j\colon X\to M가 존재한다. ** 임의의 x,y\in X에 대하여, (x,y)\in R\iff j(x)\in j(y) * (모스토프스키 붕괴 정리) 다음 조건을 만족시키는 추이적 집합 M과 전단사 함수 j\colon X\to M가 유일하게 존재한다. ** 임의의 x,y\in X에 대하여, (x,y)\in R\iff j(x)\in j(y) 마지막 두 조건은 체르멜로-프렝켈 집합론의 정칙성 공리를 필요로 한다.
# 성질
집합 X에 대하여, 다음 두 조건이 서로 동치이다. * 공집합이다. * X 위에 반사 관계인 정초 관계 \sim가 존재한다. 이는 x\in X에 대한 상수열은 x\sim x\sim x\sim\cdots이므로 정초 관계의 정의를 위반하기 때문이다. 집합 X 위의 정초 관계 R 및 부분 집합 S\subseteq X에 대하여, R의 제한 R\restriction S 역시 S 위의 정초 관계이다.
## 초한 귀납법
집합 X 위의 정초 관계 \sim_R가 주어졌을 때, 다음과 같은 **초한 귀납법**을 사용할 수 있다. 임의의 술어 P(-)에 대하여, 다음 조건이 성립한다고 하자. * 임의의 x\in X에 대하여, 만약 \forall y\in X\colon y\sim_Rx\implies P(y)라면, P(x)이다. 그렇다면, \forall x\in X\colon P(x)가 성립한다. 증명 귀류법을 사용하여, \\{x\in X\colon\lnot P(x)\\}가 공집합이 아니라고 가정하자. 그렇다면, \sim_R의 정초성에 따라 다음 두 조건을 만족시키는 x_0\in X가 존재한다. * P(x_0)은 거짓이다. * \forall x\in X\colon \lnot P(x)\implies\lnot(x\sim_Rx_0) 두 번째 조건에 대우를 취하면 다음과 같다. * \forall x\in X\colon x\sim_Rx_0\implies P(x) 따라서, P(-)가 만족시켜야 한다고 가정한 조건에 의하여 P(x_0)은 참이 되는데, 이는 모순이다. 증명 끝 집합 X 위의 정초 관계 \sim_R가 주어졌을 때, X를 정의역으로 하는 함수를 **초한 재귀**를 통해 정의할 수 있다. 이는 다음과 같다. 임의의 집합 Y 및 함수 :g\colon X\times\bigsqcup_{S\subseteq X}Y^S\to Y 에 대하여, 다음 조건을 만족시키는 유일한 함수 f\colon X\to Y가 존재한다. :\forall x\in X\colon f(x)=g(x,f\restriction\\{y\in X\colon y\sim_Rx\\}) 여기서 \restriction은 함수의 제한이다. 증명 다음 세 조건을 만족시키는 함수 h\colon\operatorname{dom}h\to Y들의 집합 \mathcal F를 생각하자. * \operatorname{dom}h\subseteq X * 임의의 x\in\operatorname{dom}h 및 y\in X에 대하여, y\sim_Rx라면, y\in\operatorname{dom}h * 임의의 x\in\operatorname{dom}h에 대하여, h(x)=g(x,h\restriction\\{y\in X\colon y\sim_Rx\\}) 그렇다면, 다음 사실들을 보일 수 있다. * 임의의 h,h'\in\mathcal F에 대하여, h\restriction\operatorname{dom}h\cap\operatorname{dom}h'=h'\restriction\operatorname{dom}h\cap\operatorname{dom}h' ** 증명: 초한 귀납법을 사용하여, x\in\operatorname{dom}h\cap\operatorname{dom}h'이며, h\restriction\\{y\in X\colon y\sim_Rx\\}=h'\restriction\\{y\in X\colon y\sim_Rx\\}라고 가정하자. 그렇다면 h(x)=g(x,h\restriction\\{y\in X\colon y\sim_Rx\\})=g(x,h'\restriction\\{y\in X\colon y\sim_Rx\\})=h'(x)이다. * \textstyle\bigcup_{h\in\mathcal F}\operatorname{dom}h=X ** 증명: 초한 귀납법을 사용하여, x\in X이며 \textstyle\\{y\in X\colon y\sim_Rx\\}\subseteq\bigcup_{h\in\mathcal F}\operatorname{dom}h라고 가정하자. \textstyle\tilde h\colon\\{x\\}\cup\bigcup_{h\in\mathcal F}\operatorname{dom}h\to Y이며, \forall h\in\mathcal F\colon\tilde h\restriction\operatorname{dom}h=h이며, \tilde h(x)=g(x,\tilde h\restriction\\{y\in X\colon y\sim_Rx\\})라고 정의하자. 그렇다면, \tilde h\in\mathcal F이며, 따라서 \textstyle x\in\bigcup_{h\in\mathcal F}\operatorname{dom}h이다. 이제, :f\colon X\to Y :\forall h\in\mathcal F\colon f\restriction\operatorname{dom}h=h 라고 하자. 그렇다면 f는 원하는 조건을 만족시킨다. 또한, 첫 번째 사실에 따라 이러한 f는 유일하다. 증명 끝
# 예

## 정초 집합
집합 X에서, 원소 관계 \in가 X 위의 정초 관계라면, X를 **정초 집합**(整礎集合, well-founded set)이라고 한다. 체르멜로-프렝켈 집합론(ZF)의 **정칙성 공리**(正則性公理, axiom of regularity)에 따르면 모든 집합은 정초 집합이다.
## 정초 모임
사실, 정칙성 공리에 따라 모든 모임은 정초 모임이다 (즉, 공집합이 아닌 모든 부분 모임은 원소 관계에 대한 극소 원소를 갖는다). 증명 임의의 모임 X\ne\varnothing에 대하여, Y\cap X=\varnothing인 Y\in X가 존재함을 보이면 충분하다. 임의의 Y\in X를 고르자. 만약 Y\cap X=\varnothing라면 증명은 끝난다. Y\cap X\ne\varnothing라고 가정하자. :\bar Y=Y\cup\bigcup Y\cup\bigcup\bigcup Y\cup\cdots 가 Y의 추이적 폐포라고 하자. 그렇다면 Z\cap X\cap\bar Y=\varnothing인 Z\in X\cap\bar Y가 존재한다. \bar Y가 추이적 집합이므로, Z\subseteq\bar Y이다. 즉, Z\cap X=\varnothing이다. 증명 끝 보다 일반적으로, 모임 X 및 이항 관계 R\subseteq X^2에 대하여, 다음 두 조건이 서로 동치이다. * 임의의 부분 집합 \varnothing\ne S\subseteq X에 대하여, \forall s\in S\colon s\not\sim_Rm인 m\in S가 존재한다. * 임의의 부분 모임 \varnothing\ne S\subseteq X에 대하여, \forall s\in S\colon s\not\sim_Rm인 m\in S가 존재한다. (물론, 두 번째 조건은 모임에 대하여 전칭을 가하므로 ZF 내에서 형식화할 수 없다.) 증명 임의의 부분 집합 \varnothing\ne S\subseteq X이 R에 대한 극소 원소를 갖는다고 가정하고, 임의의 부분 모임 \varnothing\ne Y\subseteq X의 R-극소 원소를 찾는 것으로 충분하다. 임의의 집합 A\in Y를 고르고, :Z=\bigcup_{n=0}^\infty Z_n :Z_0=\\{A\\} :Z_{n+1}=\\{B\in Y|\exists C\in Z_n\colon B\sim_RC\land\operatorname{rank}B=\min\\{\operatorname{rank}B'|\exists C\in Z_n\colon B'\sim_RC\\}\\} 라고 하자 (\operatorname{rank}는 폰 노이만 전체에서의 계수). 그렇다면, \varnothing\ne Z\subseteq Y\subseteq X는 집합이며, R-극소 원소 B\in Z를 갖는다. 이제, B가 Y의 R-극소 원소임을 보이면 족하다. 만약 C'\sim_RB인 C'\in Y가 존재한다면, 이들 사이에서 최소의 계수를 갖는 C\in Y를 고를 수 있다. 이 경우, 만약 B\in Z_n이라면 C\in Z_{n+1}이다. 즉, C\in Z이다. 증명 끝
## 정렬 원순서 집합
정렬 원순서 집합 원순서 집합 (X,\lesssim)에 대하여 다음 두 조건이 서로 동치이다.언어=en116, Remark 5 * (X,\lesssim)는 정렬 원순서 집합이다. * \mathcal P(X) 위의 원순서 S\lesssim^\star T\iff S\subseteq\downarrow T를 정의하였을 때, 이항 관계 S\prec^\star T\iff S\lesssim^\star T\not\lesssim^\star S는 정초 관계이다. (여기서 \downarrow는 하폐포를 뜻한다.)
## 순서수
순서수의 정렬 전순서 모임 \operatorname{Ord} 위에서는 흔히 다음과 같은 (조금 더 약한) 초한 귀납법이 사용된다. 임의의 술어 P(-)가 다음 두 조건을 만족시킨다고 하자. * 만약 P(\alpha)라면, P(\alpha+1)이다. * 극한 순서수 \lambda에 대하여, 만약 \forall\alpha<\lambda\colon P(\alpha)라면, P(\lambda)이다. ** 특히, P(0)이다. 그렇다면, \forall\alpha\in\operatorname{Ord}\colon P(\alpha)이다. 순서수의 정렬 전순서 모임 \operatorname{Ord} 위에서는 흔히 다음과 같은 특수한 꼴의 초한 재귀가 사용된다. 임의의 집합 X 및 함수 :F\colon X\to X :G\colon\bigsqcup_{\alpha\in\operatorname{OrdX^\alpha\to X 에 대하여, 다음 두 조건을 만족시키는 함수 f\colon\operatorname{Ord}\to X가 존재한다. * 임의의 순서수 \alpha에 대하여, f(\alpha+1)=F(f(\alpha)) * 임의의 극한 순서수 \lambda에 대하여, f(\lambda)=G(f\restriction\lambda) ** 특히, f(0)=G(\varnothing\to X) (순서수의 모임은 고유 모임이지만, 초한 귀납법과 초한 재귀는 정초 관계가 주어진 모임 위에서도 성립한다.)