정초 관계

집합론에서 **정초 관계**(整礎關係, )는 (무한히 재귀적이지 않은) 집합의 원소 관계로서 나타낼 수 있는 이항 관계이다. 정초 관계가 주어진 집합 위에서는 **초한 귀납법**(超限歸納法, )과 **초한 재귀**(超限再歸, )를 사용할 수 있다. 초한 귀납법은 정초 관계를 갖춘 집합의 모든 원소가 어떤 성질을 만족시킴을 귀납적으로 증명하는 방법이다. 초한 재귀는 정초 관계를 갖춘 집합 위에 정의된 함수를 재귀적으로 정의하는 방법이다.

## 정의
집합 X 위의 이항 관계 R\subseteq X^2에 대하여 다음 다섯 조건이 서로 동치이며, 이를 만족시키는 이항 관계를 **정초 관계**라고 한다.
* 임의의 부분 집합 \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가 존재한다.
** 임의의 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를 **정초 집합**(整礎集合, )이라고 한다. 체르멜로-프렝켈 집합론(ZF)의 **정칙성 공리**(正則性公理, )에 따르면 모든 집합은 정초 집합이다.

### 정초 모임
사실, 정칙성 공리에 따라 모든 모임은 정초 모임이다 (즉, 공집합이 아닌 모든 부분 모임은 원소 관계에 대한 극소 원소를 갖는다).

임의의 모임 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)에 대하여 다음 두 조건이 서로 동치이다.
* (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라면, 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{Ord}}X^\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)

(순서수의 모임은 고유 모임이지만, 초한 귀납법과 초한 재귀는 정초 관계가 주어진 모임 위에서도 성립한다.)

## 참고 문헌

## 외부 링크
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 

분류:집합론