정초 관계

집합론에서, 정초 관계(整礎關係, 영어: well founded relation)는 (무한히 재귀적이지 않은) 집합의 원소 관계로서 나타낼 수 있는 이항 관계이다. 이 경우 초한 귀납법을 적용할 수 있다.

정의

집합 $X$ 위의 이항 관계 $R\subseteq X^{2}$에 대하여 다음 네 조건이 서로 동치이며, 이를 만족시키는 이항 관계를 정초 관계라고 한다.^{:98, Definition III.3.1}

• 임의의 부분 집합 $\varnothing \neq 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$
• (모스토프스키 붕괴 정리) 다음 조건을 만족시키는 집합 $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\upharpoonright S$ 역시 $S$ 위의 정초 관계이다.

초한귀납법

 이 부분의 본문은 초한귀납법입니다.

집합 $X$ 위의 정초 관계 $\sim _{R}$가 주어졌을 때, 다음과 같은 초한귀납법을 사용할 수 있다. 임의의 술어 $P(-)$에 대하여, 다음 조건이 성립한다고 하자.

• 임의의 $x\in X$에 대하여, 만약 $\forall y\in X\colon y\sim _{R}x\implies P(x)$라면, $P(x)$이다.

그렇다면, $\forall x\in X\colon P(x)$가 성립한다.

예

정초 집합

집합 $X$에서, 원소 관계 $\in$가 $X$ 위의 정초 관계라면, $X$를 정초 집합(整礎集合, 영어: well-founded set)이라고 한다. 체르멜로-프렝켈 집합론의 정칙성 공리(正則性公理, 영어: axiom of regularity)에 따르면 모든 집합은 정초 집합이다.

정렬 원순서 집합

 이 부분의 본문은 정렬 원순서 집합입니다.

원순서 집합 $(X,\lesssim )$에 대하여 다음 두 조건이 서로 동치이다.^{:116, 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$는 하폐포를 뜻한다.)

외부 링크

• “Well-founded relation”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Noetherian induction”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Well-founded relation”. 《nLab》 (영어). 
• “Definition: foundational relation”. 《ProofWiki》 (영어). 
• “Definition: well-founded”. 《ProofWiki》 (영어). 2015년 6월 19일에 원본 문서에서 보존된 문서. 2016년 8월 23일에 확인함. 
• “Definition: strongly well-founded relation”. 《ProofWiki》 (영어). 
• “Condition for well-foundedness”. 《ProofWiki》 (영어). 2019년 2월 20일에 원본 문서에서 보존된 문서. 2016년 8월 23일에 확인함. 
• “Definition: well-founded set”. 《ProofWiki》 (영어). 
• “Well-founded recursion”. 《ProofWiki》 (영어). 
• “Well-founded induction”. 《ProofWiki》 (영어). 
• “Well-founded relation determines minimal elements”. 《ProofWiki》 (영어). 2013년 3월 25일에 원본 문서에서 보존된 문서. 2016년 8월 23일에 확인함. 
• “Restriction of foundational relation is foundational”. 《ProofWiki》 (영어).