정초 관계: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 봇: 문단 이름 변경 (바깥 고리 → 외부 링크) |
|||
20번째 줄: | 20번째 줄: | ||
집합 <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>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>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(x)</math>라면, <math>P(x)</math>이다. |
* 임의의 <math>x\in X</math>에 대하여, 만약 <math>\forall y\in X\colon y\sim_Rx\implies P(x)</math>라면, <math>P(x)</math>이다. |
||
그렇다면, <math>\forall x\in X\colon P(x)</math>가 성립한다. |
그렇다면, <math>\forall x\in X\colon P(x)</math>가 성립한다. |
2017년 8월 30일 (수) 09:14 판
집합론에서, 정초 관계(整礎關係, 영어: well founded relation)는 (무한히 재귀적이지 않은) 집합의 원소 관계로서 나타낼 수 있는 이항 관계이다. 이 경우 초한 귀납법을 적용할 수 있다.
정의
집합 위의 이항 관계 에 대하여 다음 네 조건이 서로 동치이며, 이를 만족시키는 이항 관계를 정초 관계라고 한다.[1]:98, Definition III.3.1
- 임의의 부분 집합 에 대하여, 인 가 존재한다.
- 다음 조건을 만족시키는 열 이 존재하지 않는다.
- 임의의 에 대하여,
- (모스토프스키 붕괴 정리) 다음 조건을 만족시키는 집합 과 단사 함수 가 존재한다.
- 임의의 에 대하여,
- (모스토프스키 붕괴 정리) 다음 조건을 만족시키는 추이적 집합 과 전단사 함수 가 유일하게 존재한다.
- 임의의 에 대하여,
마지막 두 조건은 체르멜로-프렝켈 집합론의 정칙성 공리를 필요로 한다.
성질
집합 에 대하여, 다음 두 조건이 서로 동치이다.
이는 에 대한 상수열은 이므로 정초 관계의 정의를 위반하기 때문이다.
집합 위의 정초 관계 및 부분 집합 에 대하여, 의 제한 역시 위의 정초 관계이다.
초한귀납법
집합 위의 정초 관계 가 주어졌을 때, 다음과 같은 초한귀납법을 사용할 수 있다. 임의의 술어 에 대하여, 다음 조건이 성립한다고 하자.
- 임의의 에 대하여, 만약 라면, 이다.
그렇다면, 가 성립한다.
예
정초 집합
집합 에서, 원소 관계 가 위의 정초 관계라면, 를 정초 집합(整礎集合, 영어: well-founded set)이라고 한다. 체르멜로-프렝켈 집합론의 정칙성 공리(正則性公理, 영어: axiom of regularity)에 따르면 모든 집합은 정초 집합이다.
정렬 원순서 집합
원순서 집합 에 대하여 다음 두 조건이 서로 동치이다.[2]:116, Remark 5
참고 문헌
- ↑ 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”. 《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》 (영어).
- “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》 (영어).