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

입체적으로 역사 찾아보기

← 이전 편집 다음 편집 →

내용 삭제됨 내용 추가됨

시각위키텍스트

인라인

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

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

정의

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

임의의 부분 집합 $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 )$ 에 대하여 다음 두 조건이 서로 동치이다.^[1]^{: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$ 는 하폐포를 뜻한다.)

참고 문헌

↑ Forster, Thomas (2003). “Better-quasi-orderings and coinduction”. 《Theoretical Computer Science》 (영어) 309 (1–3): 111–123. doi:10.1016/S0304-3975(03)00131-2.

바깥 고리

“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] Forster, Thomas (2003). “Better-quasi-orderings and coinduction”. 《Theoretical Computer Science》 (영어) 309 (1–3): 111–123. doi:10.1016/S0304-3975(03)00131-2.

[1]

@@ 6번째 줄: / 6번째 줄: @@
 * 다음 조건을 만족시키는 열 <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>M</math>과 [[전단사 함수]] <math>j\colon X\to M</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>가 유일하게 존재한다.