정초 관계

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

정의

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

• 임의의 부분 집합 ${\displaystyle \varnothing \neq S\subseteq X}$에 대하여, ${\displaystyle \forall s\in S\colon (s,m)\not \in R}$인 ${\displaystyle m\in S}$가 존재한다.
• 다음 조건을 만족시키는 열 ${\displaystyle (x_{i})_{i=0}^{\infty }\subseteq X}$이 존재하지 않는다.
  • 임의의 ${\displaystyle i\in \mathbb {N} }$에 대하여, ${\displaystyle (x_{i+1},x_{i})\in R}$
• 다음 조건을 만족시키는 정렬 전순서 집합 ${\displaystyle (Y,\leq )}$과 단사 함수 ${\displaystyle f\colon X\to Y}$가 존재한다.^{[2]:352, Appendix B}
  • 임의의 ${\displaystyle x,y\in X}$에 대하여, ${\displaystyle (x,y)\in R\implies f(x)<f(y)}$
• (모스토프스키 붕괴 정리) 다음 조건을 만족시키는 집합 ${\displaystyle M}$과 단사 함수 ${\displaystyle j\colon X\to M}$가 존재한다.
  • 임의의 ${\displaystyle x,y\in X}$에 대하여, ${\displaystyle (x,y)\in R\iff j(x)\in j(y)}$
• (모스토프스키 붕괴 정리) 다음 조건을 만족시키는 추이적 집합 ${\displaystyle M}$과 전단사 함수 ${\displaystyle j\colon X\to M}$가 유일하게 존재한다.
  • 임의의 ${\displaystyle x,y\in X}$에 대하여, ${\displaystyle (x,y)\in R\iff j(x)\in j(y)}$

마지막 두 조건은 체르멜로-프렝켈 집합론의 정칙성 공리를 필요로 한다.

성질

집합 ${\displaystyle X}$에 대하여, 다음 두 조건이 서로 동치이다.

• 공집합이다.
• ${\displaystyle X}$ 위에 반사 관계인 정초 관계 ${\displaystyle \sim }$가 존재한다.

이는 ${\displaystyle x\in X}$에 대한 상수열은 ${\displaystyle x\sim x\sim x\sim \cdots }$이므로 정초 관계의 정의를 위반하기 때문이다.

집합 ${\displaystyle X}$ 위의 정초 관계 ${\displaystyle R}$ 및 부분 집합 ${\displaystyle S\subseteq X}$에 대하여, ${\displaystyle R}$의 제한 ${\displaystyle R\upharpoonright S}$ 역시 ${\displaystyle S}$ 위의 정초 관계이다.

초한 귀납법

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

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

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

증명:

귀류법을 사용하여, ${\displaystyle \{x\in X\colon \lnot P(x)\}}$가 공집합이 아니라고 가정하자. 그렇다면, ${\displaystyle \sim _{R}}$의 정초성에 따라 다음 두 조건을 만족시키는 ${\displaystyle x_{0}\in X}$가 존재한다.

• ${\displaystyle P(x_{0})}$은 거짓이다.
• ${\displaystyle \forall x\in X\colon \lnot P(x)\implies \lnot (x\sim _{R}x_{0})}$

두 번째 조건에 대우를 취하면 다음과 같다.

• ${\displaystyle \forall x\in X\colon x\sim _{R}x_{0}\implies P(x)}$

따라서, ${\displaystyle P(-)}$가 만족시켜야 한다고 가정한 조건에 의하여 ${\displaystyle P(x_{0})}$은 참이 되는데, 이는 모순이다.

집합 ${\displaystyle X}$ 위의 정초 관계 ${\displaystyle \sim _{R}}$가 주어졌을 때, ${\displaystyle X}$를 정의역으로 하는 함수를 초한 재귀를 통해 정의할 수 있다. 이는 다음과 같다. 임의의 집합 ${\displaystyle Y}$ 및 함수

${\displaystyle g\colon X\times \bigsqcup _{S\subseteq X}Y^{S}\to Y}$

에 대하여, 다음 조건을 만족시키는 유일한 함수 ${\displaystyle f\colon X\to Y}$가 존재한다.

${\displaystyle \forall x\in X\colon f(x)=g(x,f\upharpoonright \{y\in X\colon y\sim _{R}x\})}$

여기서 ${\displaystyle \upharpoonright }$은 함수의 제한이다.

증명:

다음 세 조건을 만족시키는 함수 ${\displaystyle h\colon \operatorname {dom} h\to Y}$들의 집합 ${\displaystyle {\mathcal {F}}}$를 생각하자.

• ${\displaystyle \operatorname {dom} h\subseteq X}$
• 임의의 ${\displaystyle x\in \operatorname {dom} h}$ 및 ${\displaystyle y\in X}$에 대하여, ${\displaystyle y\sim _{R}x}$라면, ${\displaystyle y\in \operatorname {dom} h}$
• 임의의 ${\displaystyle x\in \operatorname {dom} h}$에 대하여, ${\displaystyle h(x)=g(x,h\upharpoonright \{y\in X\colon y\sim _{R}x\})}$

그렇다면, 다음 사실들을 보일 수 있다.

• 임의의 ${\displaystyle h,h'\in {\mathcal {F}}}$에 대하여, ${\displaystyle h\upharpoonright \operatorname {dom} h\cap \operatorname {dom} h'=h'\upharpoonright \operatorname {dom} h\cap \operatorname {dom} h'}$
  • 증명: 초한 귀납법을 사용하여, ${\displaystyle x\in \operatorname {dom} h\cap \operatorname {dom} h'}$이며, ${\displaystyle h\upharpoonright \{y\in X\colon y\sim _{R}x\}=h'\upharpoonright \{y\in X\colon y\sim _{R}x\}}$라고 가정하자. 그렇다면 ${\displaystyle h(x)=g(x,h\upharpoonright \{y\in X\colon y\sim _{R}x\})=g(x,h'\upharpoonright \{y\in X\colon y\sim _{R}x\})=h'(x)}$이다.
• ${\displaystyle \textstyle \bigcup _{h\in {\mathcal {F}}}\operatorname {dom} h=X}$
  • 증명: 초한 귀납법을 사용하여, ${\displaystyle x\in X}$이며 ${\displaystyle \textstyle \{y\in X\colon y\sim _{R}x\}\subseteq \bigcup _{h\in {\mathcal {F}}}\operatorname {dom} h}$라고 가정하자. ${\displaystyle \textstyle {\tilde {h}}\colon \{x\}\cup \bigcup _{h\in {\mathcal {F}}}\operatorname {dom} h\to Y}$이며, ${\displaystyle \forall h\in {\mathcal {F}}\colon {\tilde {h}}\upharpoonright \operatorname {dom} h=h}$이며, ${\displaystyle {\tilde {h}}(x)=g(x,{\tilde {h}}\upharpoonright \{y\in X\colon y\sim _{R}x\})}$라고 정의하자. 그렇다면, ${\displaystyle {\tilde {h}}\in {\mathcal {F}}}$이며, 따라서 ${\displaystyle \textstyle x\in \bigcup _{h\in {\mathcal {F}}}\operatorname {dom} h}$이다.

이제,

${\displaystyle f\colon X\to Y}$

${\displaystyle \forall h\in {\mathcal {F}}\colon f\upharpoonright \operatorname {dom} h=h}$

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

예

정초 집합

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

정초 모임

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

증명:

임의의 모임 ${\displaystyle X\neq \varnothing }$에 대하여, ${\displaystyle Y\cap X=\varnothing }$인 ${\displaystyle Y\in X}$가 존재함을 보이면 충분하다. 임의의 ${\displaystyle Y\in X}$를 고르자. 만약 ${\displaystyle Y\cap X=\varnothing }$라면 증명은 끝난다. ${\displaystyle Y\cap X\neq \varnothing }$라고 가정하자.

${\displaystyle {\bar {Y}}=Y\cup \bigcup Y\cup \bigcup \bigcup Y\cup \cdots }$

가 ${\displaystyle Y}$의 추이적 폐포라고 하자. 그렇다면 ${\displaystyle Z\cap X\cap {\bar {Y}}=\varnothing }$인 ${\displaystyle Z\in X\cap {\bar {Y}}}$가 존재한다. ${\displaystyle {\bar {Y}}}$가 추이적 집합이므로, ${\displaystyle Z\subseteq {\bar {Y}}}$이다. 즉, ${\displaystyle Z\cap X=\varnothing }$이다.

보다 일반적으로, 모임 ${\displaystyle X}$ 및 이항 관계 ${\displaystyle R\subseteq X^{2}}$에 대하여, 다음 두 조건이 서로 동치이다.

• 임의의 부분 집합 ${\displaystyle \varnothing \neq S\subseteq X}$에 대하여, ${\displaystyle \forall s\in S\colon s\not \sim _{R}m}$인 ${\displaystyle m\in S}$가 존재한다.
• 임의의 부분 모임 ${\displaystyle \varnothing \neq S\subseteq X}$에 대하여, ${\displaystyle \forall s\in S\colon s\not \sim _{R}m}$인 ${\displaystyle m\in S}$가 존재한다.

(물론, 두 번째 조건은 모임에 대하여 전칭을 가하므로 ZF 내에서 형식화할 수 없다.)

증명:

임의의 부분 집합 ${\displaystyle \varnothing \neq S\subseteq X}$이 ${\displaystyle R}$에 대한 극소 원소를 갖는다고 가정하고, 임의의 부분 모임 ${\displaystyle \varnothing \neq Y\subseteq X}$의 ${\displaystyle R}$-극소 원소를 찾는 것으로 충분하다. 임의의 집합 ${\displaystyle A\in Y}$를 고르고,

${\displaystyle Z=\bigcup _{n=0}^{\infty }Z_{n}}$

${\displaystyle Z_{0}=\{A\}}$

${\displaystyle Z_{n+1}=\{B\in Y|\exists C\in Z_{n}\colon B\sim _{R}C\land \operatorname {rank} B=\min\{\operatorname {rank} B'|\exists C\in Z_{n}\colon B'\sim _{R}C\}\}}$

라고 하자 (${\displaystyle \operatorname {rank} }$는 폰 노이만 전체에서의 계수). 그렇다면, ${\displaystyle \varnothing \neq Z\subseteq Y\subseteq X}$는 집합이며, ${\displaystyle R}$-극소 원소 ${\displaystyle B\in Z}$를 갖는다. 이제, ${\displaystyle B}$가 ${\displaystyle Y}$의 ${\displaystyle R}$-극소 원소임을 보이면 족하다. 만약 ${\displaystyle C'\sim _{R}B}$인 ${\displaystyle C'\in Y}$가 존재한다면, 이들 사이에서 최소의 계수를 갖는 ${\displaystyle C\in Y}$를 고를 수 있다. 이 경우, 만약 ${\displaystyle B\in Z_{n}}$이라면 ${\displaystyle C\in Z_{n+1}}$이다. 즉, ${\displaystyle C\in Z}$이다.

정렬 원순서 집합

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

원순서 집합 ${\displaystyle (X,\lesssim )}$에 대하여 다음 두 조건이 서로 동치이다.^{[3]:116, Remark 5}

• ${\displaystyle (X,\lesssim )}$는 정렬 원순서 집합이다.
• ${\displaystyle {\mathcal {P}}(X)}$ 위의 원순서 ${\displaystyle S\lesssim ^{\star }T\iff S\subseteq \downarrow T}$를 정의하였을 때, 이항 관계 ${\displaystyle S\prec ^{\star }T\iff S\lesssim ^{\star }T\not \lesssim ^{\star }S}$는 정초 관계이다. (여기서 ${\displaystyle \downarrow }$는 하폐포를 뜻한다.)

순서수

순서수의 정렬 전순서 모임 ${\displaystyle \operatorname {Ord} }$ 위에서는 흔히 다음과 같은 (조금 더 약한) 초한 귀납법이 사용된다. 임의의 술어 ${\displaystyle P(-)}$가 다음 두 조건을 만족시킨다고 하자.

• 만약 ${\displaystyle P(\alpha )}$라면, ${\displaystyle P(\alpha +1)}$이다.
• 극한 순서수 ${\displaystyle \lambda }$에 대하여, 만약 ${\displaystyle \forall \alpha <\lambda \colon P(\alpha )}$라면, ${\displaystyle P(\lambda )}$이다.
  • 특히, ${\displaystyle P(0)}$이다.

그렇다면, ${\displaystyle \forall \alpha \in \operatorname {Ord} \colon P(\alpha )}$이다.

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

${\displaystyle F\colon X\to X}$

${\displaystyle G\colon \bigsqcup _{\alpha \in \operatorname {Ord} }X^{\alpha }\to X}$

에 대하여, 다음 두 조건을 만족시키는 함수 ${\displaystyle f\colon \operatorname {Ord} \to X}$가 존재한다.

• 임의의 순서수 ${\displaystyle \alpha }$에 대하여, ${\displaystyle f(\alpha +1)=F(f(\alpha ))}$
• 임의의 극한 순서수 ${\displaystyle \lambda }$에 대하여, ${\displaystyle f(\lambda )=G(f\upharpoonright \lambda )}$
  • 특히, ${\displaystyle f(0)=G(\varnothing \to X)}$

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

각주

1. Kunen, Kenneth (1980). 《Set theory: an introduction to independence proofs》. Studies in Logic and the Foundations of Mathematics (영어) 102. North-Holland. ISBN 978-0-444-86839-8. MR 597342. Zbl 0534.03026. 2016년 9월 11일에 원본 문서에서 보존된 문서. 2016년 8월 23일에 확인함.
2. Kechris, Alexander Sotirios (1995). 《Classical descriptive set theory》. Graduate Texts in Mathematics (영어) 156. New York, NY: Springer. doi:10.1007/978-1-4612-4190-4. ISBN 978-0-387-94374-9. ISSN 0072-5285. MR 1321597. Zbl 0819.04002.
3. Forster, Thomas (2003). “Better-quasi-orderings and coinduction”. 《Theoretical Computer Science》 (영어) 309 (1–3): 111–123. doi:10.1016/S0304-3975(03)00131-2. ISSN 0304-3975.

외부 링크

• “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.
• “Transfinite recursion”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
• Weisstein, Eric Wolfgang. “Transfinite induction”. 《Wolfram MathWorld》 (영어). Wolfram Research.
• “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》 (영어).^{[깨진 링크(과거 내용 찾기)]}
• Hamkins, Joel David (2014년 10월 20일). “Transfinite recursion as a fundamental principle in set theory” (영어). 2014년 12월 23일에 원본 문서에서 보존된 문서. 2015년 1월 4일에 확인함.