정초 관계 문서 원본 보기

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

== 정의 ==
집합 <math>X</math> 위의 [[이항 관계]] <math>R\subseteq X^2</math>에 대하여 다음 다섯 조건이 서로 [[동치]]이며, 이를 만족시키는 [[이항 관계]]를 '''정초 관계'''라고 한다.<ref>{{서적 인용|title=Set theory: an introduction to independence proofs|성=Kunen|이름=Kenneth|저자링크=케네스 쿠넌|publisher=North-Holland|날짜=1980|isbn=978-0-444-86839-8|url=http://store.elsevier.com/Set-Theory-An-Introduction-To-Independence-Proofs/K_-Kunen/isbn-9780444868398/|총서=Studies in Logic and the Foundations of Mathematics|권=102|zbl=0534.03026|mr=597342|언어=en|확인날짜=2016-08-23|보존url=https://web.archive.org/web/20160911102401/http://store.elsevier.com/Set-Theory-An-Introduction-To-Independence-Proofs/K_-Kunen/isbn-9780444868398/|보존날짜=2016-09-11|url-status=dead}}</ref>{{rp|98, Definition III.3.1}}
* 임의의 부분 집합 <math>\varnothing\ne S\subseteq X</math>에 대하여, <math>\forall s\in S\colon (s,m)\not\in R</math>인 <math>m\in S</math>가 존재한다.
* 다음 조건을 만족시키는 열 <math>(x_i)_{i=0}^\infty\subseteq X</math>이 존재하지 않는다.
** 임의의 <math>i\in\mathbb N</math>에 대하여, <math>(x_{i+1},x_i)\in R</math>
* 다음 조건을 만족시키는 [[정렬 전순서 집합]] <math>(Y,\le)</math>과 [[단사 함수]] <math>f\colon X\to Y</math>가 존재한다.<ref name="Kechris">{{서적 인용
|이름1=Alexander Sotirios
|성1=Kechris
|제목=Classical descriptive set theory
|언어=en
|총서=Graduate Texts in Mathematics
|권=156
|출판사=Springer
|위치=New York, NY
|날짜=1995
|isbn=978-0-387-94374-9
|issn=0072-5285
|doi=10.1007/978-1-4612-4190-4
|mr=1321597
|zbl=0819.04002
}}</ref>{{rp|352, Appendix B}}
** 임의의 <math>x,y\in X</math>에 대하여, <math>(x,y)\in R\implies f(x)<f(y)</math>
* ([[모스토프스키 붕괴 정리]]) 다음 조건을 만족시키는 [[집합]] <math>M</math>과 [[단사 함수]] <math>j\colon X\to M</math>가 존재한다.
** 임의의 <math>x,y\in X</math>에 대하여, <math>(x,y)\in R\iff j(x)\in j(y)</math>
* ([[모스토프스키 붕괴 정리]]) 다음 조건을 만족시키는 [[추이적 집합]] <math>M</math>과 [[전단사 함수]] <Math>j\colon X\to M</math>가 유일하게 존재한다.
** 임의의 <math>x,y\in X</math>에 대하여, <math>(x,y)\in R\iff j(x)\in j(y)</math>
마지막 두 조건은 [[체르멜로-프렝켈 집합론]]의 정칙성 공리를 필요로 한다.

== 성질 ==
집합 <math>X</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* [[공집합]]이다.
* <math>X</math> 위에 [[반사 관계]]인 정초 관계 <math>\sim</math>가 존재한다.
이는 <math>x\in X</math>에 대한 [[상수 함수|상수열]]은 <math>x\sim x\sim x\sim\cdots</math>이므로 정초 관계의 정의를 위반하기 때문이다.

집합 <math>X</math> 위의 정초 관계 <math>R</math> 및 [[부분 집합]] <math>S\subseteq X</math>에 대하여, <math>R</math>의 제한 <math>R\restriction S</math> 역시 <math>S</math> 위의 정초 관계이다.

=== 초한 귀납법 ===
집합 <math>X</math> 위의 정초 관계 <math>\sim_R</math>가 주어졌을 때, 다음과 같은 '''초한 귀납법'''을 사용할 수 있다. 임의의 술어 <math>P(-)</math>에 대하여, 다음 조건이 성립한다고 하자.
* 임의의 <math>x\in X</math>에 대하여, 만약 <math>\forall y\in X\colon y\sim_Rx\implies P(y)</math>라면, <math>P(x)</math>이다.
그렇다면, <math>\forall x\in X\colon P(x)</math>가 성립한다.
{{증명}}
[[귀류법]]을 사용하여, <math>\{x\in X\colon\lnot P(x)\}</math>가 [[공집합]]이 아니라고 가정하자. 그렇다면, <math>\sim_R</math>의 정초성에 따라 다음 두 조건을 만족시키는 <math>x_0\in X</math>가 존재한다.
* <math>P(x_0)</math>은 거짓이다.
* <math>\forall x\in X\colon \lnot P(x)\implies\lnot(x\sim_Rx_0)</math>
두 번째 조건에 대우를 취하면 다음과 같다.
* <math>\forall x\in X\colon x\sim_Rx_0\implies P(x)</math>
따라서, <math>P(-)</math>가 만족시켜야 한다고 가정한 조건에 의하여 <math>P(x_0)</math>은 참이 되는데, 이는 모순이다. 
{{증명 끝}}

집합 <math>X</math> 위의 정초 관계 <math>\sim_R</math>가 주어졌을 때, <math>X</math>를 정의역으로 하는 함수를 '''초한 재귀'''를 통해 정의할 수 있다. 이는 다음과 같다. 임의의 [[집합]] <math>Y</math> 및 [[함수]]
:<math>g\colon X\times\bigsqcup_{S\subseteq X}Y^S\to Y</math>
에 대하여, 다음 조건을 만족시키는 유일한 함수 <math>f\colon X\to Y</math>가 존재한다.
:<math>\forall x\in X\colon f(x)=g(x,f\restriction\{y\in X\colon y\sim_Rx\})</math>
여기서 <math>\restriction</math>은 [[함수의 제한]]이다.
{{증명}}
다음 세 조건을 만족시키는 함수 <math>h\colon\operatorname{dom}h\to Y</math>들의 집합 <math>\mathcal F</math>를 생각하자.
* <math>\operatorname{dom}h\subseteq X</math>
* 임의의 <math>x\in\operatorname{dom}h</math> 및 <math>y\in X</math>에 대하여, <math>y\sim_Rx</math>라면, <math>y\in\operatorname{dom}h</math>
* 임의의 <math>x\in\operatorname{dom}h</math>에 대하여, <math>h(x)=g(x,h\restriction\{y\in X\colon y\sim_Rx\})</math>
그렇다면, 다음 사실들을 보일 수 있다.
* 임의의 <math>h,h'\in\mathcal F</math>에 대하여, <math>h\restriction\operatorname{dom}h\cap\operatorname{dom}h'=h'\restriction\operatorname{dom}h\cap\operatorname{dom}h'</math>
** 증명: 초한 귀납법을 사용하여, <math>x\in\operatorname{dom}h\cap\operatorname{dom}h'</math>이며, <math>h\restriction\{y\in X\colon y\sim_Rx\}=h'\restriction\{y\in X\colon y\sim_Rx\}</math>라고 가정하자. 그렇다면 <math>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)</math>이다.
* <math>\textstyle\bigcup_{h\in\mathcal F}\operatorname{dom}h=X</math>
** 증명: 초한 귀납법을 사용하여, <math>x\in X</math>이며 <math>\textstyle\{y\in X\colon y\sim_Rx\}\subseteq\bigcup_{h\in\mathcal F}\operatorname{dom}h</math>라고 가정하자. <math>\textstyle\tilde h\colon\{x\}\cup\bigcup_{h\in\mathcal F}\operatorname{dom}h\to Y</math>이며, <math>\forall h\in\mathcal F\colon\tilde h\restriction\operatorname{dom}h=h</math>이며, <math>\tilde h(x)=g(x,\tilde h\restriction\{y\in X\colon y\sim_Rx\})</math>라고 정의하자. 그렇다면, <math>\tilde h\in\mathcal F</math>이며, 따라서 <math>\textstyle x\in\bigcup_{h\in\mathcal F}\operatorname{dom}h</math>이다.
이제,
:<math>f\colon X\to Y</math>
:<math>\forall h\in\mathcal F\colon f\restriction\operatorname{dom}h=h</math>
라고 하자. 그렇다면 <math>f</math>는 원하는 조건을 만족시킨다. 또한, 첫 번째 사실에 따라 이러한 <math>f</math>는 유일하다.
{{증명 끝}}

== 예 ==
=== 정초 집합 ===
집합 <math>X</math>에서, 원소 관계 <math>\in</math>가 <math>X</math> 위의 정초 관계라면, <math>X</math>를 '''정초 집합'''(整礎集合, {{llang|en|well-founded set}})이라고 한다. [[체르멜로-프렝켈 집합론]](ZF)의 '''정칙성 공리'''(正則性公理, {{llang|en|axiom of regularity}})에 따르면 모든 집합은 정초 집합이다.

=== 정초 모임 ===
사실, 정칙성 공리에 따라 모든 [[모임 (집합론)|모임]]은 정초 모임이다 (즉, [[공집합]]이 아닌 모든 부분 모임은 원소 관계에 대한 [[극소 원소]]를 갖는다).
{{증명}}
임의의 [[모임 (집합론)|모임]] <math>X\ne\varnothing</math>에 대하여, <math>Y\cap X=\varnothing</math>인 <math>Y\in X</math>가 존재함을 보이면 충분하다. 임의의 <math>Y\in X</math>를 고르자. 만약 <math>Y\cap X=\varnothing</math>라면 증명은 끝난다. <math>Y\cap X\ne\varnothing</math>라고 가정하자.
:<math>\bar Y=Y\cup\bigcup Y\cup\bigcup\bigcup Y\cup\cdots</math>
가 <math>Y</math>의 [[추이적 폐포]]라고 하자. 그렇다면 <math>Z\cap X\cap\bar Y=\varnothing</math>인 <math>Z\in X\cap\bar Y</math>가 존재한다. <math>\bar Y</math>가 [[추이적 집합]]이므로, <math>Z\subseteq\bar Y</math>이다. 즉, <math>Z\cap X=\varnothing</math>이다.
{{증명 끝}}

보다 일반적으로, [[모임 (집합론)|모임]] <math>X</math> 및 [[이항 관계]] <math>R\subseteq X^2</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* 임의의 부분 집합 <math>\varnothing\ne S\subseteq X</math>에 대하여, <math>\forall s\in S\colon s\not\sim_Rm</math>인 <math>m\in S</math>가 존재한다.
* 임의의 부분 모임 <math>\varnothing\ne S\subseteq X</math>에 대하여, <math>\forall s\in S\colon s\not\sim_Rm</math>인 <math>m\in S</math>가 존재한다.
(물론, 두 번째 조건은 모임에 대하여 전칭을 가하므로 ZF 내에서 형식화할 수 없다.)
{{증명}}
임의의 부분 집합 <math>\varnothing\ne S\subseteq X</math>이 <math>R</math>에 대한 [[극소 원소]]를 갖는다고 가정하고, 임의의 부분 모임 <math>\varnothing\ne Y\subseteq X</math>의 <math>R</math>-[[극소 원소]]를 찾는 것으로 충분하다. 임의의 집합 <math>A\in Y</math>를 고르고,
:<math>Z=\bigcup_{n=0}^\infty Z_n</math>
:<math>Z_0=\{A\}</math>
:<math>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\}\}</math>
라고 하자 (<math>\operatorname{rank}</math>는 [[폰 노이만 전체]]에서의 계수). 그렇다면, <math>\varnothing\ne Z\subseteq Y\subseteq X</math>는 [[집합]]이며, <math>R</math>-[[극소 원소]] <math>B\in Z</math>를 갖는다. 이제, <math>B</math>가 <math>Y</math>의 <math>R</math>-[[극소 원소]]임을 보이면 족하다. 만약 <math>C'\sim_RB</math>인 <math>C'\in Y</math>가 존재한다면, 이들 사이에서 최소의 계수를 갖는 <math>C\in Y</math>를 고를 수 있다. 이 경우, 만약 <math>B\in Z_n</math>이라면 <math>C\in Z_{n+1}</math>이다. 즉, <math>C\in Z</math>이다.
{{증명 끝}}

=== 정렬 원순서 집합 ===
{{본문|정렬 원순서 집합}}
[[원순서 집합]] <math>(X,\lesssim)</math>에 대하여 다음 두 조건이 서로 [[동치]]이다.<ref>{{저널 인용|성=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|언어=en}}</ref>{{rp|116, Remark 5}}
* <math>(X,\lesssim)</math>는 [[정렬 원순서 집합]]이다.
* <math>\mathcal P(X)</math> 위의 [[원순서]] <math>S\lesssim^\star T\iff S\subseteq\downarrow T</math>를 정의하였을 때, [[이항 관계]] <math>S\prec^\star T\iff S\lesssim^\star T\not\lesssim^\star S</math>는 정초 관계이다. (여기서 <math>\downarrow</math>는 [[하폐포]]를 뜻한다.)

=== 순서수 ===
[[순서수]]의 [[정렬 전순서 집합|정렬 전순서 모임]] <math>\operatorname{Ord}</math> 위에서는 흔히 다음과 같은 (조금 더 약한) 초한 귀납법이 사용된다. 임의의 술어 <math>P(-)</math>가 다음 두 조건을 만족시킨다고 하자.
* 만약 <math>P(\alpha)</math>라면, <math>P(\alpha+1)</math>이다.
* [[극한 순서수]] <math>\lambda</math>에 대하여, 만약 <math>\forall\alpha<\lambda\colon P(\alpha)</math>라면, <math>P(\lambda)</math>이다.
** 특히, <math>P(0)</math>이다.
그렇다면, <math>\forall\alpha\in\operatorname{Ord}\colon P(\alpha)</math>이다.

[[순서수]]의 [[정렬 전순서 집합|정렬 전순서 모임]] <math>\operatorname{Ord}</math> 위에서는 흔히 다음과 같은 특수한 꼴의 초한 재귀가 사용된다. 임의의 [[집합]] <math>X</math> 및 [[함수]]
:<math>F\colon X\to X</math>
:<math>G\colon\bigsqcup_{\alpha\in\operatorname{Ord}}X^\alpha\to X</math>
에 대하여, 다음 두 조건을 만족시키는 함수 <math>f\colon\operatorname{Ord}\to X</math>가 존재한다.
* 임의의 [[순서수]] <math>\alpha</math>에 대하여, <math>f(\alpha+1)=F(f(\alpha))</math>
* 임의의 [[극한 순서수]] <math>\lambda</math>에 대하여, <math>f(\lambda)=G(f\restriction\lambda)</math>
** 특히, <math>f(0)=G(\varnothing\to X)</math>

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

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Well-founded relation}}
* {{eom|title=Noetherian induction}}
* {{eom|title=Transfinite recursion}}
* {{매스월드|id=TransfiniteInduction|title=Transfinite induction}}
* {{nlab|id=well-founded relation|title=Well-founded relation}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Foundational_Relation|제목=Definition: foundational relation|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Well-Founded|제목=Definition: well-founded|웹사이트=ProofWiki|언어=en|확인날짜=2016-08-23|archive-date=2015-06-19|archive-url=https://web.archive.org/web/20150619163918/https://proofwiki.org/wiki/Definition:Well-Founded}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Strongly_Well-Founded_Relation|제목=Definition: strongly well-founded relation|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Condition_for_Well-Foundedness|제목=Condition for well-foundedness|웹사이트=ProofWiki|언어=en|확인날짜=2016-08-23|archive-date=2019-02-20|archive-url=https://web.archive.org/web/20190220181521/https://proofwiki.org/wiki/Condition_for_Well-Foundedness}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Well-Founded_Set|제목=Definition: well-founded set|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Well-Founded_Recursion|제목=Well-founded recursion|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Well-Founded_Induction|제목=Well-founded induction|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Well-Founded_Relation_Determines_Minimal_Elements|제목=Well-founded relation determines minimal elements|웹사이트=ProofWiki|언어=en|확인날짜=2016-08-23|archive-date=2013-03-25|archive-url=https://web.archive.org/web/20130325182612/http://www.proofwiki.org/wiki/Well-Founded_Relation_Determines_Minimal_Elements}}
* {{웹 인용|url=https://proofwiki.org/wiki/Restriction_of_Foundational_Relation_is_Foundational|제목=Restriction of foundational relation is foundational|웹사이트=ProofWiki|언어=en}}{{깨진 링크|url=https://proofwiki.org/wiki/Restriction_of_Foundational_Relation_is_Foundational }}
* {{웹 인용|url=http://jdh.hamkins.org/transfinite-recursion-as-a-fundamental-principle-in-set-theory/|제목=Transfinite recursion as a fundamental principle in set theory|이름=Joel David|성=Hamkins|날짜=2014-10-20|언어=en|확인날짜=2015-01-04|보존url=https://web.archive.org/web/20141223185054/http://jdh.hamkins.org/transfinite-recursion-as-a-fundamental-principle-in-set-theory/|보존날짜=2014-12-23|url-status=dead}}

[[분류:집합론]]