정초 관계

집합론에서 정초 관계(整礎關係, )는 (무한히 재귀적이지 않은) 집합의 원소 관계로서 나타낼 수 있는 이항 관계이다. 정초 관계가 주어진 집합 위에서는 초한 귀납법(超限歸納法, )과 초한 재귀(超限再歸, )를 사용할 수 있다. 초한 귀납법은 모든 원소가 어떤 성질을 만족시킴을 증명할 때 사용한다. 초한 귀납법에 따르면, 어떤 술어가 모든 원소에 대하여 참임을 보이려면, 주어진 원소 ‘이전’의 모든 원소들에 대하여 참임을 가정한 채로, 그 주어진 원소에 대하여 참임을 보이면 충분하다. 이는 자연수에 대한 수학적 귀납법을 일반화한다. 초한 재귀는 정초 관계가 주어진 집합을 정의역으로 하는 함수를 정의하는 방법이다. 초한 재귀에 따르면, 주어진 원소의 함숫값을 그 ‘이전’의 원소들의 함숫값들로부터 결정하는 방법(#초한 귀납법에서의 함수 )이 정해졌을 때, 모든 원소에 대한 함숫값은 유일하게 결정된다.

정의 
집합  위의 이항 관계 에 대하여 다음 다섯 조건이 서로 동치이며, 이를 만족시키는 이항 관계를 정초 관계라고 한다.
 임의의 부분 집합 에 대하여, 인 가 존재한다.
 다음 조건을 만족시키는 열 이 존재하지 않는다.
 임의의 에 대하여, 
 다음 조건을 만족시키는 정렬 전순서 집합 과 단사 함수 가 존재한다.
 임의의 에 대하여, 
 (모스토프스키 붕괴 정리) 다음 조건을 만족시키는 집합 과 단사 함수 가 존재한다.
 임의의 에 대하여, 
 (모스토프스키 붕괴 정리) 다음 조건을 만족시키는 추이적 집합 과 전단사 함수 가 유일하게 존재한다.
 임의의 에 대하여, 
마지막 두 조건은 체르멜로-프렝켈 집합론의 정칙성 공리를 필요로 한다.

성질 
집합 에 대하여, 다음 두 조건이 서로 동치이다.
 공집합이다.
  위에 반사 관계인 정초 관계 가 존재한다.
이는 에 대한 상수열은 이므로 정초 관계의 정의를 위반하기 때문이다.

집합  위의 정초 관계  및 부분 집합 에 대하여, 의 제한  역시  위의 정초 관계이다.

초한 귀납법 
집합  위의 정초 관계 가 주어졌을 때, 다음과 같은 초한 귀납법을 사용할 수 있다. 임의의 술어 에 대하여, 다음 조건이 성립한다고 하자.
 임의의 에 대하여, 만약 라면, 이다.
그렇다면, 가 성립한다.

귀류법을 사용하여, 가 공집합이 아니라고 가정하자. 그렇다면, 의 정초성에 따라 다음 두 조건을 만족시키는 가 존재한다.
 은 거짓이다.
 
두 번째 조건에 대우를 취하면 다음과 같다.
 
따라서, 가 만족시켜야 한다고 가정한 조건에 의하여 은 참이 되는데, 이는 모순이다. 

집합  위의 정초 관계 가 주어졌을 때, 를 정의역으로 하는 함수를 초한 재귀를 통해 정의할 수 있다. 이는 다음과 같다. 임의의 집합  및 함수

에 대하여, 다음 조건을 만족시키는 유일한 함수 가 존재한다.

여기서 은 함수의 제한이다.

다음 세 조건을 만족시키는 함수 들의 집합 를 생각하자.
 
 임의의  및 에 대하여, 라면, 
 임의의 에 대하여, 
그렇다면, 다음 사실들을 보일 수 있다.
 임의의 에 대하여, 
 증명: 초한 귀납법을 사용하여, 이며, 라고 가정하자. 그렇다면 이다.
 
 증명: 초한 귀납법을 사용하여, 이며 라고 가정하자. 이며, 이며, 라고 정의하자. 그렇다면, 이며, 따라서 이다.
이제,

라고 하자. 그렇다면 는 원하는 조건을 만족시킨다. 또한, 첫 번째 사실에 따라 이러한 는 유일하다.

예

정초 집합 
집합 에서, 원소 관계 가  위의 정초 관계라면, 를 정초 집합(整礎集合, )이라고 한다. 체르멜로-프렝켈 집합론의 정칙성 공리(正則性公理, )에 따르면 모든 집합은 정초 집합이다.

정렬 원순서 집합 

원순서 집합 에 대하여 다음 두 조건이 서로 동치이다.
 는 정렬 원순서 집합이다.
  위의 원순서 를 정의하였을 때, 이항 관계 는 정초 관계이다. (여기서 는 하폐포를 뜻한다.)

순서수 
순서수의 정렬 전순서 모임  위에서는 흔히 다음과 같은 (조금 더 약한) 초한 귀납법이 사용된다. 임의의 술어 가 다음 두 조건을 만족시킨다고 하자.
 만약 라면, 이다.
 극한 순서수 에 대하여, 만약 라면, 이다.
 특히, 이다.
그렇다면, 이다.

순서수의 정렬 전순서 모임  위에서는 흔히 다음과 같은 특수한 꼴의 초한 재귀가 사용된다. 임의의 집합  및 함수

및 모임 함수

에 대하여, 다음 두 조건을 만족시키는 모임 함수 가 존재한다.
 임의의 순서수 에 대하여, 
 임의의 극한 순서수 에 대하여, 
 특히, 

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

참고 문헌

외부 링크 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

집합론