정초 관계: 두 판 사이의 차이

내용 삭제됨 내용 추가됨

인라인

2016년 8월 24일 (수) 05:36 판

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

정의

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

임의의 부분 집합 $S\subseteq X$ 에 대하여, $\forall s\in S\colon (s,m)\not \in R$ 인 $m\in S$ 가 존재한다.
다음 조건을 만족시키는 열 $(x_{i})_{i=0}^{\infty }\subseteq X$ $(x_{i})_{i=0}^{\infty }\subseteq X$ 이 존재하지 않는다.
- 임의의 $i\in \mathbb {N}$ 에 대하여, $(x_{i+1},x_{i})\in R$
(모스토프스키 붕괴 정리) 다음 조건을 만족시키는 집합 $M$ $M$ 과 단사 함수 $j\colon X\to M$ $j\colon X\to M$ 가 존재한다.
- 임의의 $x,y\in X$ 에 대하여, $(x,y)\in R\iff j(x)\in j(y)$
(모스토프스키 붕괴 정리) 다음 조건을 만족시키는 추이적 집합 $M$ $M$ 과 전단사 함수 $j\colon X\to 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 )$ 에 대하여 다음 두 조건이 서로 동치이다.^[2]^{: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$ 는 하폐포를 뜻한다.)

참고 문헌

↑ 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.
↑ 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”. 《nLab》 (영어).
“Definition: foundational relation”. 《ProofWiki》 (영어).
“Definition: well-founded”. 《ProofWiki》 (영어).
“Definition: strongly well-founded relation”. 《ProofWiki》 (영어).
“Condition for well-foundedness”. 《ProofWiki》 (영어).
“Definition: well-founded set”. 《ProofWiki》 (영어).
“Well-founded recursion”. 《ProofWiki》 (영어).
“Well-founded induction”. 《ProofWiki》 (영어).
“Well-founded relation determines minimal elements”. 《ProofWiki》 (영어).
“Restriction of foundational relation is foundational”. 《ProofWiki》 (영어).

[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.

[2] 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.

[1]

[2]

@@ 2번째 줄: / 2번째 줄: @@
 == 정의 ==
-집합 <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|issn=0304-3975|언어=en}}</ref>{{rp|98, Definition III.3.1}}
+집합 <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}}</ref>{{rp|98, Definition III.3.1}}
 * 임의의 부분 집합 <math>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>이 존재하지 않는다.
@@ 32번째 줄: / 32번째 줄: @@
 === 정렬 원순서 집합 ===
 {{본문|정렬 원순서 집합}}
-[[원순서 집합]] <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|언어=en}}</ref>{{rp|116, Remark 5}}
+[[원순서 집합]] <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>는 [[하집합|하폐포]]를 뜻한다.)