정초 관계

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

정의

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

임의의 부분 집합 $\emptyset \neq S \subseteq X$ 에 대하여, $\forall s \in S : (s, m) \in̸ R$ 인 $m \in S$ 가 존재한다.
다음 조건을 만족시키는 열 (xi)i=0∞⊆X이 존재하지 않는다.
- 임의의 $i \in ℕ$ 에 대하여, $(x_{i + 1}, x_{i}) \in R$
다음 조건을 만족시키는 정렬 전순서 집합 (Y,≤)과 단사 함수 f:X→Y가 존재한다.^[2]틀:Rp
- 임의의 $x, y \in X$ 에 대하여, $(x, y) \in R ⟹ f (x) < f (y)$
(모스토프스키 붕괴 정리) 다음 조건을 만족시키는 집합 M과 단사 함수 j:X→M가 존재한다.
- 임의의 $x, y \in X$ 에 대하여, $(x, y) \in R ⟺ j (x) \in j (y)$
(모스토프스키 붕괴 정리) 다음 조건을 만족시키는 추이적 집합 M과 전단사 함수 j:X→M가 유일하게 존재한다.
- 임의의 $x, y \in X$ 에 대하여, $(x, y) \in R ⟺ j (x) \in j (y)$

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

성질

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

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

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

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

초한 귀납법

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

임의의 $x \in X$ 에 대하여, 만약 $\forall y \in X : y \sim_{R} x ⟹ P (y)$ 라면, $P (x)$ 이다.

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

$P (x_{0})$ 은 거짓이다.
$\forall x \in X : \neg P (x) ⟹ \neg (x \sim_{R} x_{0})$

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

$\forall x \in X : x \sim_{R} x_{0} ⟹ P (x)$

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

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

g : X \times ⨆_{S \subseteq X} Y^{S} \to Y

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

\forall x \in X : f (x) = g (x, f ↾ {y \in X : y \sim_{R} x})

여기서 $↾$ 은 함수의 제한이다. 틀:증명 다음 세 조건을 만족시키는 함수 $h : dom h \to Y$ 들의 집합 $ℱ$ 를 생각하자.

$dom h \subseteq X$
임의의 $x \in dom h$ 및 $y \in X$ 에 대하여, $y \sim_{R} x$ 라면, $y \in dom h$
임의의 $x \in dom h$ 에 대하여, $h (x) = g (x, h ↾ {y \in X : y \sim_{R} x})$

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

임의의 h,h′∈ℱ에 대하여, h↾dom⁡h∩dom⁡h′=h′↾dom⁡h∩dom⁡h′
- 증명: 초한 귀납법을 사용하여, $x \in dom h \cap dom h^{'}$ 이며, $h ↾ {y \in X : y \sim_{R} x} = h^{'} ↾ {y \in X : y \sim_{R} x}$ 라고 가정하자. 그렇다면 $h (x) = g (x, h ↾ {y \in X : y \sim_{R} x}) = g (x, h^{'} ↾ {y \in X : y \sim_{R} x}) = h^{'} (x)$ 이다.
⋃h∈ℱdom⁡h=X
- 증명: 초한 귀납법을 사용하여, $x \in X$ 이며 ${y \in X : y \sim_{R} x} \subseteq ⋃_{h \in ℱ} dom h$ 라고 가정하자. $\tilde{h} : {x} \cup ⋃_{h \in ℱ} dom h \to Y$ 이며, $\forall h \in ℱ : \tilde{h} ↾ dom h = h$ 이며, $\tilde{h} (x) = g (x, \tilde{h} ↾ {y \in X : y \sim_{R} x})$ 라고 정의하자. 그렇다면, $\tilde{h} \in ℱ$ 이며, 따라서 $x \in ⋃_{h \in ℱ} dom h$ 이다.

이제,

f : X \to Y

\forall h \in ℱ : f ↾ dom h = h

라고 하자. 그렇다면 $f$ 는 원하는 조건을 만족시킨다. 또한, 첫 번째 사실에 따라 이러한 $f$ 는 유일하다. 틀:증명 끝

예

정초 집합

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

정초 모임

사실, 정칙성 공리에 따라 모든 모임은 정초 모임이다 (즉, 공집합이 아닌 모든 부분 모임은 원소 관계에 대한 극소 원소를 갖는다). 틀:증명 임의의 모임 $X \neq \emptyset$ 에 대하여, $Y \cap X = \emptyset$ 인 $Y \in X$ 가 존재함을 보이면 충분하다. 임의의 $Y \in X$ 를 고르자. 만약 $Y \cap X = \emptyset$ 라면 증명은 끝난다. $Y \cap X \neq \emptyset$ 라고 가정하자.

\bar{Y} = Y \cup ⋃ Y \cup ⋃ ⋃ Y \cup \dots

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

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

임의의 부분 집합 $\emptyset \neq S \subseteq X$ 에 대하여, $\forall s \in S : s \sim_{R} m$ 인 $m \in S$ 가 존재한다.
임의의 부분 모임 $\emptyset \neq S \subseteq X$ 에 대하여, $\forall s \in S : s \sim_{R} m$ 인 $m \in S$ 가 존재한다.

(물론, 두 번째 조건은 모임에 대하여 전칭을 가하므로 ZF 내에서 형식화할 수 없다.) 틀:증명 임의의 부분 집합 $\emptyset \neq S \subseteq X$ 이 $R$ 에 대한 극소 원소를 갖는다고 가정하고, 임의의 부분 모임 $\emptyset \neq Y \subseteq X$ 의 $R$ -극소 원소를 찾는 것으로 충분하다. 임의의 집합 $A \in Y$ 를 고르고,

Z = ⋃_{n = 0}^{\infty} Z_{n}

Z_{0} = {A}

Z_{n + 1} = {B \in Y | \exists C \in Z_{n} : B \sim_{R} C \land rank B = \min {rank B^{'} | \exists C \in Z_{n} : B^{'} \sim_{R} C}}

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

정렬 원순서 집합

틀:본문 원순서 집합 $(X, ≲)$ 에 대하여 다음 두 조건이 서로 동치이다.^[3]틀:Rp

$(X, ≲)$ 는 정렬 원순서 집합이다.
$𝒫 (X)$ 위의 원순서 $S ≲^{⋆} T ⟺ S \subseteq ↓ T$ 를 정의하였을 때, 이항 관계 $S ≺^{⋆} T ⟺ S ≲^{⋆} T {≴}^{⋆̸} S$ 는 정초 관계이다. (여기서 $↓$ 는 하폐포를 뜻한다.)

순서수

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

만약 $P (α)$ 라면, $P (α + 1)$ 이다.
극한 순서수 λ에 대하여, 만약 ∀α<λ:P(α)라면, P(λ)이다.
- 특히, $P (0)$ 이다.

그렇다면, $\forall α \in Ord : P (α)$ 이다.

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

F : X \to X

G : ⨆_{α \in Ord} X^{α} \to X

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

임의의 순서수 $α$ 에 대하여, $f (α + 1) = F (f (α))$
임의의 극한 순서수 λ에 대하여, f(λ)=G(f↾λ)
- 특히, $f (0) = G (\emptyset \to X)$

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

각주

틀:각주

외부 링크

[1] 틀:서적 인용

[Kechris-2] 틀:서적 인용

[3] 틀:저널 인용

[1]

[2]

[3]

정초 관계

목차

정의

성질

초한 귀납법

예

정초 집합

정초 모임

정렬 원순서 집합

순서수

각주

외부 링크

둘러보기 메뉴

정초 관계

정의

성질

초한 귀납법

예

정초 집합

정초 모임

정렬 원순서 집합

순서수

각주

외부 링크

둘러보기 메뉴

검색