정초 관계

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 동치 조건 (체르멜로-프렝켈 집합론의 정칙성 공리 필요)
3. 성질
- 3.1. 초한 귀납법
- 3.2. 초한 재귀
4. 예
5. 반사 관계와 정초성
6. 정초성의 유전
참조

1. 개요

정초 관계는 집합 X 위의 이항 관계 R이 특정 조건을 만족하는 경우를 의미하며, 초한 귀납법과 초한 재귀를 가능하게 한다. 정초 관계는 부분 집합 S에 m이 존재하지 않으며, 가산 무한 강하열이 없고, 정렬 전순서 집합과 단사 함수가 존재하며, 모스토프스키 붕괴 정리를 만족하는 경우 등으로 정의된다. 정초 관계는 정초 반순서, 정렬 순서, 정초적 집합, 역정초 관계 등과 관련되며, 초한 귀납법과 초한 재귀를 사용하여 수학적 증명과 대상 구성을 지원한다. 원소 관계가 정초 관계인 집합은 정초 집합으로 불리며, 정칙성 공리에 따라 모든 집합은 정초 집합이다.

더 읽어볼만한 페이지

집합론 - 퍼지 집합
퍼지 집합은 각 원소가 0과 1 사이의 소속도를 가지며, 소속 함수를 통해 정의되고, 여집합, 합집합, 교집합 등의 연산을 수행하며, 퍼지 논리, 퍼지 수, 엔트로피 등의 개념과 L-퍼지 집합, 직관적 퍼지 집합 등으로 확장된다.
집합론 - 무한 집합
무한 집합은 유한 집합이 아니며, 자연수보다 큰 크기를 가지고 자신의 진부분집합과 일대일 대응을 가지며, 가산 무한 집합과 비가산 무한 집합으로 나뉜다.

정초 관계
수학적 정의
정의	수학에서, 정초 관계(整礎關係, 영어: well-founded relation)는 집합의 모든 공집합이 아닌 부분집합이 그 관계에 대한 최소 원소를 갖는 이항 관계이다.
최소 원소	최소 원소는 부분집합의 다른 모든 원소와 그 관계를 갖는 부분집합의 원소이다.
다른 이름	부분적으로 정렬된 집합에 대한 정초 관계는 때때로 부분적으로 정렬된 집합이 정초되었거나 잘 고정되었다고 한다.
관련 개념	정초 관계는 수학적 귀납법과 초한 귀납법에 중요한 역할을 한다.
형식적 정의
이항 관계	임의의 집합 X에 대한 이항 관계 R은 X × X의 부분집합이다.
정초 관계의 조건	X에 대한 이항 관계 R이 정초 관계라는 것은, X의 모든 비어 있지 않은 부분집합 S에 대해 S의 원소 m이 존재하여 S의 모든 s에 대해 sRm이 성립한다는 것이다.
최소 원소의 존재	위 조건은 각 부분집합 S가 R에 대해 "최소" 원소를 포함한다는 것을 의미한다. 여기서 "최소"는 전순서 관계의 의미로 해석되지 않는다.
다른 정의 방식
무한 감소열의 부재	정초 관계는 무한 감소열을 허용하지 않는다는 점에서 정의될 수도 있다.
무한 감소열의 정의	X의 원소의 무한열 x0, x1, x2, ...이 있고 모든 n에 대해 xn+1Rxn인 경우, 해당 열을 R에 대한 무한 감소열이라고 한다.
정초 관계와 무한 감소열	관계가 정초 관계인 것은 무한 감소열이 없는 것과 같다.
예시
일반적인 예시	자연수에 대한 일반적인 순서 관계 >는 정초 관계이다. 실수에 대한 일반적인 순서 관계 >는 정초 관계가 아니다(예: 음의 정수 집합은 최소 원소를 갖지 않는다).
추가 예시	집합에 대한 포함 관계 ⊃는 정초 관계이다. 모든 집합이 정초 집합인 경우, 집합에 대한 원소 관계 ∈는 정초 관계이다.
정초 집합과의 관계
모든 집합의 정초성 가정	모든 집합이 정초 집합이라는 가정은 ZFC 집합 이론에서 공리(정초성 공리)로 사용될 수 있다.
중요성	이 공리는 거의 모든 수학에 영향을 미치지 않지만, 집합 이론의 특정 연구에서 그 자체로 흥미롭다.
같이 보기
참고 문헌
외부 링크

2. 정의

집합 또는 클래스 ''X'' 위의 이항 관계 ''R''이 '''정초 관계'''라는 것은, ''X''의 공이 아닌 임의의 부분 집합 ''S''가 ''R''에 관한 극소원을 갖는다는 것을 의미한다.^[6] 이는 종속 선택 공리를 가정했을 때, 가산 무한 강하열이 존재하지 않는다는 것과 동치이다.

순서 집합론에서 반순서에 대응하는 참된 순서(strict partial order)가 정초 관계일 때, 그 반순서를 정초(정초 반순서)라고 부른다. 전순서가 이 의미에서 정초일 때, 정렬 순서라고 부른다.

집합 ''x''가 '''정초적 집합'''(well-founded set)이라는 것은, ∈가 ''x''의 추이적 폐포 위에서 정초 관계가 되는 것과 동치이다. 정칙성 공리는 모든 집합이 정초적 집합임을 요구한다.

관계 ''R''이 ''X'' 위에서 '''역정초'''(converse well-founded) 또는 '''상방 정초'''(upwards well-founded)라는 것은, ''R''의 역관계 ''R''⁻¹이 ''X'' 위의 정초 관계일 때를 말한다. 이때 ''R''은 상승 사슬 조건을 만족시킨다고 한다.

2. 1. 동치 조건 (체르멜로-프렝켈 집합론의 정칙성 공리 필요)

모스토프스키 붕괴 정리에 기반한 다음 두 조건은 체르멜로-프렝켈 집합론의 정칙성 공리를 필요로 한다.^[6]

다음 조건을 만족시키는 집합 $M$ 과 단사 함수 $j\colon X\to M$ 가 존재한다.
임의의 $x,y\in X$ 에 대하여, $(x,y)\in R\iff j(x)\in j(y)$
다음 조건을 만족시키는 추이적 집합 $M$ 과 전단사 함수 $j\colon X\to M$ 가 유일하게 존재한다.
임의의 $x,y\in X$ 에 대하여, $(x,y)\in R\iff j(x)\in j(y)$

모스토프스키 붕괴 보조정리는 집합 포함 관계가 외연적인 정초 관계 중에서 보편적임을 의미한다. 즉, 외연적인 클래스

X

에 대한 집합과 유사한 정초 관계

R

에 대해,

(X, R)

가

(C, \in)

와 동형인 클래스

C

가 존재한다.

3. 성질

정초 관계에서는 초한 귀납법(transfinite induction)과 초한 재귀(transfinite recursion)를 사용할 수 있다. 초한 귀납법은 에미 뇌터의 업적을 기려 뇌터 귀납법(Noetherian induction)이라고도 부른다.^[4]^[5]

정초 관계는 수학적 귀납법을 일반화한 것으로 생각할 수 있다. 예를 들어, ('''N''', ''S'')라는 정초 관계를 생각할 수 있는데, 여기서 '''N'''은 모든 자연수의 집합이고, ''S''는 후자 함수 ''x'' → ''x'' + 1의 그래프이다. ''S''에 대한 귀납법은 일반적인 수학적 귀납법이고, ''S''에 대한 재귀는 원시 재귀를 제공한다. 만약 순서 관계 ('''N''', <)를 고려한다면, 완전 귀납법과 값 추이 재귀를 얻게 된다. ('''N''', <)가 잘 정렬되었다는 진술은 정렬 원리라고도 알려져 있다.

3. 1. 초한 귀납법

집합

X

위에 정초 관계

\sim_R

가 주어졌을 때, 임의의 술어

P(-)

에 대해 다음 조건이 성립한다고 가정한다.

임의의 $x\in X$ 에 대하여, 만약 $\forall y\in X\colon y\sim_Rx\implies P(y)$ 라면, $P(x)$ 이다.

그렇다면,

\forall x\in X\colon P(x)

가 성립한다. 이것은 정초 관계에서 사용되는 초한 귀납법이다.^[4]

간단히 설명하면, 정초 관계가 주어진 집합 위에서 특정 술어가 모든 원소에 대해 성립함을 증명하는 방법이다.

이 방법은 에미 뇌터의 이름을 따서 뇌터 귀납법이라고도 부른다.^[5]

3. 2. 초한 재귀

집합

X

위의 정초 관계

\sim_R

가 주어졌을 때,

X

를 정의역으로 하는 함수를 정의할 수 있다. 이를 초한 재귀라고 한다. 임의의 집합

Y

및 함수

:

g\colon X\times\bigsqcup_{S\subseteq X}Y^S\to Y

에 대하여, 다음 조건을 만족시키는 유일한 함수

f\colon X\to Y

가 존재한다.

:

\forall x\in X\colon f(x)=g(x,f\restriction\{y\in X\colon y\sim_Rx\})

여기서

\restriction

은 함수의 제한이다.

다른 정의 방법으로는,

(X, R)

을 집합과 같은 잘 정렬된 관계라고 하고,

F

를 각 쌍의 원소

x \in X

와

X

의 초기 구간

\{y : y R x\}

에 대한 함수

g

에 객체

F(x, g)

를 할당하는 함수라고 할 때, 모든

x \in X

에 대해 다음이 성립하는 고유한 함수

G

가 존재한다.

:

G(x) = F\left(x, G\vert_{\left\{y:\, y\mathrel{R}x\right\}}\right)

즉,

X

에 대한 함수

G

를 구성하려는 경우,

y R x

에 대해

G(y)

의 값을 사용하여

G(x)

를 정의할 수 있다.

정초 관계

( \mathbb{N}, S)

를 예로 들 수 있다. 여기서

\mathbb{N}

은 자연수 전체의 집합이고,

S

는 후자 함수

x \to x+1

의 그래프이다.

S

상의 재귀는 원시 재귀를 제공한다.

4. 예

정초 관계의 예시는 다음과 같다.

양의 정수 집합에, ''a'' < ''b'' ⇔ [''a''는 ''b''를 나누고 ''a'' ≠ ''b''] 가 되는 순서를 넣은 것.
고정된 문자 집합 위의 유한 문자열 전체에 ''s'' < ''t'' ⇔ ''s''는 ''t''의 진부분 문자열이다,로 정해지는 순서.
자연수의 순서쌍 전체의 집합 '''N''' × '''N''' 위에, (''n''₁, ''n''₂) < (''m''₁, ''m''₂) ⇔ ''n''₁ < ''m''₁ 이고 ''n''₂ < ''m''₂가 되는 순서.
정칙성 공리에 따르면, 집합을 요소로 하는 임의의 클래스에 대한 집합 요소 관계 ∈.
임의의 유한 유향 비순환 그래프의 노드 전체에, ''a R b'' ⇔ ''a''에서 ''b''로 가는 변이 있다로 정의되는 관계.

정초 관계가 아닌 예시는 다음과 같다.

음의 정수 전체 {−1, −2, −3, …} 의 통상적인 순서. 임의의 비유계 부분 집합이 최소 원소를 가지지 않는다.
유한 문자 집합 위의 문자열 전체로 이루어진 집합에서의, 통상적인 순서 관계(사전식 순서). 열 "B" > "AB" > "AAB" > "AAAB" > … 는 무한 강하 사슬이 된다. 이 관계는 전체 집합이 최소 원소(즉, 빈 문자열)를 갖더라도 정초가 아니다.
유리수 전체 (또는 실수 전체) 의 표준적인 순서 (대소 관계). 예를 들어, 양의 유리수 (또는 양의 실수) 전체는 최소 원소를 갖지 않는다.

4. 1. 정초 집합

집합

X

에서, 원소 관계

\in

가

X

위의 정초 관계라면,

X

를 '''정초 집합'''(well-founded set|웰 파운디드 셋^영어)이라고 한다. 체르멜로-프렝켈 집합론(ZF)의 '''정칙성 공리'''(axiom of regularity|액시엄 오브 레귤러리티^영어)에 따르면 모든 집합은 정초 집합이다.

만약

(X,<)

가 정초 관계이고

x

가

X

의 원소라면,

x

에서 시작하는 내림차순 사슬은 모두 유한하지만, 그 길이들이 반드시 제한된다는 의미는 아니다. 다음 예시를 고려해보자.

X

를 모든 정수보다 큰 새로운 원소

\omega

와 양의 정수의 합집합이라고 하자. 그러면

X

는 정초 집합이지만,

\omega

에서 시작하는 임의로 큰 (유한) 길이의 내림차순 사슬이 존재한다.

사슬

\omega, n-1, n-2, \dots, 2, 1

의 길이는 임의의

n

에 대해

n

이다.

모스토스키 붕괴 보조정리는 집합 포함 관계가 외연적인 정초 관계 중에서 보편적임을 의미한다. 즉, 외연적인 클래스

X

에 대한 집합과 유사한 정초 관계

R

에 대해,

(X, R)

가

(C, \in)

와 동형인 클래스

C

가 존재한다.

4. 2. 정렬 원순서 집합

원순서 집합

(X,\lesssim)

에 대하여 다음 두 조건은 서로 동치이다.^[8]

$(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$ 는 하폐포를 뜻한다.)

4. 3. 순서수

순서수의 정렬 전순서 모임

\operatorname{Ord}

위에서는 흔히 다음과 같은 (조금 더 약한) 초한 귀납법이 사용된다. 임의의 술어

P(-)

가 다음 두 조건을 만족시킨다고 하자.

만약 $P(\alpha)$ 라면, $P(\alpha+1)$ 이다.
극한 순서수 $\lambda$ 에 대하여, 만약 $\forall\alpha<\lambda\colon P(\alpha)$ 라면, $P(\lambda)$ 이다.
특히, $P(0)$ 이다.

그렇다면,

\forall\alpha\in\operatorname{Ord}\colon P(\alpha)

이다.

순서수의 정렬 전순서 모임

\operatorname{Ord}

위에서는 흔히 다음과 같은 특수한 꼴의 초한 재귀가 사용된다. 임의의 집합

X

및 함수

:

F\colon X\to X

:

G\colon\bigsqcup_{\alpha\in\operatorname{Ord}}X^\alpha\to X

에 대하여, 다음 두 조건을 만족시키는 함수

f\colon\operatorname{Ord}\to X

가 존재한다.

임의의 순서수 $\alpha$ 에 대하여, $f(\alpha+1)=F(f(\alpha))$
임의의 극한 순서수 $\lambda$ 에 대하여, $f(\lambda)=G(f\restriction\lambda)$
특히, $f(0)=G(\varnothing\to X)$

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

5. 반사 관계와 정초성

반사 관계는 무한 강하 사슬을 가질 수 있으므로, 정초 관계를 정의할 때 주의가 필요하다. 일반적으로 반사 관계를 다룰 때는, 반사적이지 않은 관계를 대신 사용하는 경우가 많다. 예를 들어, 자연수의 전순서 ≤를 사용할 때는, ''a'' ≤ ''b'' 이고 ''a'' ≠ ''b'' 인 경우에만 ''a'' < ''b''로 정의되는 관계 <을 사용하는 것이 일반적이다.

6. 정초성의 유전

어떤 집합이 정초 집합이라면 해당 집합의 각 원소도 정초 집합이며, 각 원소의 또 다른 원소도 정초 집합이고, 그 또 다른 원소도 정초 집합이며... 와 같이 계속 이어진다. 이를 정초 집합은 '''유전적 정초'''(hereditarily well-founded)라고 한다.

참조

_[1] 서적 Introduction to axiomatic set theory Springer-Verlag 1971
_[2] 웹사이트 Infinite Sequence Property of Strictly Well-Founded Relation https://proofwiki.or[...] 2021-05-10
_[3] 서적 Theory of Relations, Volume 145 - 1st Edition https://www.elsevier[...] Elsevier 2019-02-20
_[4] 간행물 Elements of mathematics. Commutative algebra Addison-Wesley 1972
_[5] 간행물 Elements of mathematics. Commutative algebra Addison-Wesley 1972
_[6] 서적 Set theory: an introduction to independence proofs http://store.elsevie[...] North-Holland 2016-08-23
_[7] 서적 1995
_[8] 저널 2003

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com