결정 집합

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

1. 개요
2. 정의
- 2.1. 결정 집합
- 2.2. 결정 공리
3. 성질
4. 무한 논리와 결정 공리
5. 역사
- 5.1. 실수 정의 가능 결정 공리의 허용
6. 비판적 관점
참조

1. 개요

결정 집합은 특정 조건을 만족하는 게임에서 한 플레이어가 필승 전략을 갖는 집합을 의미한다. 결정 공리는 이러한 게임이 모두 결정적이라는 주장을 담고 있으며, 모든 집합 X가 결정 집합이라는 주장을 의미하는 AD, 실수 정의 가능 결정 공리 AD^L(R), 사영 결정 공리 PD 등이 존재한다. 결정 공리는 선택 공리를 부정하며, 큰 기수의 존재와 밀접한 관련이 있다. ZFC에서 보렐 집합은 결정 집합이며, 결정 공리는 무한 논리와도 관련이 있다. 이 개념은 1935년 스타니스와프 울람에 의해 도입되었고, 1962년 얀 미치엘스키와 후고 스테인하우스에 의해 결정 공리가 도입되었다.

더 읽어볼만한 페이지

집합론 공리 - 선택 공리
선택 공리는 공집합을 원소로 갖지 않는 집합족에서 각 집합의 원소를 하나씩 선택하여 새로운 집합을 만들 수 있다는 공리이며, 선택 함수 존재성과 동치이고, ZF와 독립적이면서 다양한 수학적 명제와 동치인 중요한 역할을 한다.
집합론 공리 - 큰 기수
큰 기수는 특정 성질을 만족하는 기수의 존재를 가정하는 공리들로 정의되며, 체르멜로-프렠켈 집합론의 일관성을 증명하고 집합론적 우주 이해에 기여하며 수학 철학적 논의 대상이 된다.
집합론 - 퍼지 집합
퍼지 집합은 각 원소가 0과 1 사이의 소속도를 가지며, 소속 함수를 통해 정의되고, 여집합, 합집합, 교집합 등의 연산을 수행하며, 퍼지 논리, 퍼지 수, 엔트로피 등의 개념과 L-퍼지 집합, 직관적 퍼지 집합 등으로 확장된다.
집합론 - 무한 집합
무한 집합은 유한 집합이 아니며, 자연수보다 큰 크기를 가지고 자신의 진부분집합과 일대일 대응을 가지며, 가산 무한 집합과 비가산 무한 집합으로 나뉜다.
일반위상수학 - 극한
극한은 수학에서 함수의 값이나 수열의 항이 특정 값에 가까워지는 현상을 기술하는 개념으로, ε-δ 논법으로 엄밀하게 정의되며 수렴, 연속성, 미적분학 등 다양한 분야에서 활용되고, 고대 그리스에서 시작하여 19세기에 현대적 정의가 완성되었다.
일반위상수학 - 스콧 위상
스콧 위상은 부분 순서 집합 위에 정의되는 위상으로, 하향 집합과 directed set의 상한에 대해 닫혀있는 집합을 닫힌 집합으로 정의하며, 컴퓨터 과학, 특히 프로그램 의미론에서 연속 함수의 개념을 일반화하고 프로그램의 계산 과정을 모델링하는 데 사용된다.

결정 집합
개요
유형	집합론의 공리 후보
제안자	미첼스키와 유고 스타인하우스
특징	선택 공리와 모순됨
내용	모든 집합은 결정적이다
관련 개념	위상적인 완전 정보 게임, 완전 집합성

2. 정의

결정 공리는 특정한 형태의 2인 무한 게임을 통해 정의된다. 이 게임은 다음과 같이 구성된다.

집합 $A$ 가 주어진다.
$A$ 의 원소들로 이루어진 무한 수열들의 집합 $X \subseteq A^\omega$ 가 주어진다. 이를 '''승패 집합'''이라고 한다.
$A$ 에 이산 위상을 부여하고, $A^\omega$ 에 곱위상을 부여했을 때, 공집합이 아닌 닫힌집합 $\varnothing \ne [T] \subseteq A^\omega$ 가 주어진다. 이는 나무 $T = \textstyle\bigcup_{n<\omega}\{t\restriction n\colon t\in T\} \subseteq A^{<\omega}$ 로 나타낼 수 있다. 나무 $T$ 를 '''허용된 수의 나무'''라고 한다.

이러한 데이터를 바탕으로 두 선수 갑(甲)과 을(乙)이 참여하는 게임을 정의한다. 갑과 을은 번갈아 가면서

A

의 원소를 선택한다. 갑이 먼저 시작하며, 각 선수는 이전에 놓인 모든 수를 알고 있다. 선택된 수들은

k=(k_0, k_1, k_2, \dots)

로 표현된다. 갑은

k_0, k_2, k_4, \dots

를, 을은

k_1, k_3, k_5, \dots

를 선택한다. 이때, 각

i<\omega

에 대하여

(k_0, k_1, \dots, k_{i-1}) \in T

를 만족해야 한다.

만약 최종적으로 만들어진 수열

(k)_{i<\omega}

가 승패 집합

X

에 속하면 갑이 승리하고, 그렇지 않으면 을이 승리한다.

2. 1. 결정 집합

결정 집합(決定集合, determined set^영어)은 특정 조건을 만족하는 게임에서 한 플레이어가 필승 전략을 갖는 집합을 의미한다.

다음과 같은 2인(人) 게임을 생각해보자.^[4]^[5]

두 선수 갑(甲)과 을(乙)이 있다.
갑과 을은 차례대로 수(手)를 둔다. 여기서 수를 둔다는 것은 주어진 집합 $A$ 의 원소를 하나 고르는 것이다. 갑이 먼저 시작한다.
각 선수는 이전에 놓인 모든 수를 알고 있다.
이렇게 선택된 수들을 $k=(k_0, k_1, k_2, \dots)$ 라고 하자. 갑은 $k_0, k_2, k_4, \dots$ 를, 을은 $k_1, k_3, k_5, \dots$ 를 둔다.
미리 정의된 승패 집합 $X$ 가 존재한다. $X$ 는 $A$ 의 원소들의 무한열로 이루어진 집합이다.
또한, 허용된 수의 나무 $T$ 가 존재한다. 각 $i<\omega$ 에 대하여 $(k_0,k_1,\dots,k_{i-1})\in T$ 이어야만 한다.
최종적으로 만들어진 수열 $(k)_{i<\omega}$ 가 $X$ 에 속하면 갑이 이기고, 그렇지 않으면 을이 이긴다.

여기서 전략(戰略, strategy^영어)은

A^{<\omega}

에서

A

로 가는 함수이다.

A^{<\omega}

는

A

의 원소들로 이루어진 유한열들의 집합이다.

갑의 필승 전략: 갑의 필승 전략은 어떤 전략 $\sigma$ 에 대해, 을이 어떤 수열 $(t_i)$ 를 선택하더라도 갑이 $\sigma$ 를 따라 수를 두면 항상 이기는 경우를 말한다. 즉, $(\sigma(), t_0, \sigma(t_0), t_1, \sigma(t_0, t_1), t_2, \sigma(t_0, t_1, t_2), \ldots) \in X$ 가 성립한다.
을의 필승 전략: 을의 필승 전략은 어떤 전략 $\sigma$ 에 대해, 갑이 어떤 수열 $(s_i)$ 를 선택하더라도 을이 $\sigma$ 를 따라 수를 두면 항상 이기는 경우를 말한다. 즉, $(s_0, \sigma(s_0), s_1, \sigma(s_0, s_1), s_2, \sigma(s_0, s_1, s_2), \ldots) \not\in X$ 가 성립한다.

X\subseteq A^\omega

에 대하여, 만약 위 게임에서 갑과 을 가운데 하나가 필승 전략을 갖는다면,

X

가

T

로 정의되는 게임에 대한 '''결정 집합'''이라고 한다.^[5] 만약

T

가 명시되지 않았다면,

T=A^{<\omega}

이다.

2. 2. 결정 공리

'''결정 공리'''(決定公理, axiom of determinacy^영어) $\mathsf{AD}$ 는 모든 집합 $X\subseteq\mathbb N^\omega$ 이 결정 집합이라는 주장이다.^[1]
'''실수 정의 가능 결정 공리'''(實數定義可能決定公理, axiom of real-definable determinacy^영어) $\mathsf{AD}^{L(\mathbb R)}$ 는 실수 구성 가능 집합들의 누적 위계인 $L(\mathbb R)$ 에 속하는 모든 집합 $X\subseteq \mathbb N^\omega\cap L(\mathbb R)$ 이 결정 집합이라는 주장이다.^[1]
'''사영 결정 공리'''(射影決定公理, axiom of projective determinacy^영어) $\mathsf{PD}$ 는 모든 사영 집합 $X\subseteq \mathbb N^\omega$ 에 대해 선수 1이 필승 전략을 갖거나, 선수 2가 필승 전략을 갖는다는 주장이다.^[1]

결정 공리는 자연수의 모든 무한 수열인 ω^ω의 베르 공간의 부분 집합 ''A''를 이용한 특정 형태의 게임을 지칭한다. 두 명의 플레이어가 자연수를 번갈아 선택하여 무한히 많은 움직임 후에 수열 ⟨''n''_''i''⟩_''i''∈ω를 생성한다. 처음 선택하는 플레이어는 생성된 수열이 ''A''의 요소인 경우에만 게임에서 승리한다. 결정 공리는 모든 그러한 게임이 결정된다는 진술이다.^[1]

결정 공리는 실수의 모든 부분 공간 ''X''에 대해 바나흐-마주르 게임 BM(''X'')이 결정되며, 결과적으로 모든 실수 집합이 베어 성질을 갖는다는 것을 의미한다. 선택 공리를 가정하면 결정 공리에 대한 반례를 구성할 수 있으므로, 결정 공리와 선택 공리는 양립할 수 없다.^[1]

결정 공리의 무모순성은 거대 기수 공리의 무모순성 문제와 밀접하게 관련되어 있다. 우딘의 정리에 따르면, ZF와 결정 공리의 무모순성은 ZFC와 무한히 많은 우딘 기수의 존재의 무모순성과 동등하다. 우딘 기수는 강하게 도달 불가능하므로, AD가 무모순적이면, 무한히 많은 도달 불가능 기수도 무모순적이다.^[1]

3. 성질

선택 공리를 가정하면, 결정 공리에 대한 반례를 구성할 수 있다. 따라서 결정 공리와 선택 공리는 양립할 수 없다.

ω-game (길이 ω 의 게임) ''G''에서 전략이란, 「구성되어 있는 유한 열에 대해 다음 차례에 무엇을 계속할지」라는 움직임의 규칙을 말한다. 전략의 개념은 winning set이 무엇인지와 관계없이 정의할 수 있다. 선택 공리 하에서, 전략 전체의 집합은 연속체 농도를 가진다.

플레이어 I가 채택할 수 있는 모든 전략의 집합 S1 = {s1(α) : α < 2^ω }와 플레이어 II가 채택할 수 있는 모든 전략의 집합 S2 = {s2(α) : α < 2^ω }를 정의한다.

여기에서 초한 재귀를 통해 결정적이지 않은 집합 A = {A(α) : α < 2^ω }를 구성해 나간다. 즉, A를 플레이어 I의 winning set으로 하는 게임을 생각하면 필승 전략이 없도록 하려는 것이다. 동시에, A의 구성을 돕기 위해 B = {B(α) : α < 2^ω }를 A와 교차하지 않도록 구성해 나간다.

# α < 2^ω로 하고, {A(β) : β < α}와 {B(β) : β < α}까지 구성되어 있다고 한다.

# B(α)를 플레이어 I가 s1(α)에 따라 게임에서 구성할 수 있는 열 중, {A(β) : β < α}에 속하지 않는 것으로 한다. 이는 가능하다. 왜냐하면, 플레이어 II의 움직임 선택의 농도는 연속체 농도이며, 이 시점까지 만들어진 A의 농도보다 크기 때문이다.

# A(α)를 플레이어 II가 s2(α)에 따라 게임에서 구성할 수 있는 열 중, {B(β) : β ≤ α}에 속하지 않는 것으로 한다. 이는 가능하다. 왜냐하면, 플레이어 I의 움직임 선택의 농도는 연속체 농도이며, 이 시점까지 만들어진 B의 농도보다 크기 때문이다.

# 이상의 프로세스를 S1과 S2의 모든 전략에 대해 순서대로 실행을 완료했다고 한다. 이때, A와 B 어느 쪽에도 들어 있지 않은 자연수열이 존재한다면, 그 전체에 의한 집합을 C로 한다. 이로 인해, B ∪ C는 A의 여집합이 된다.

A의 구성이 끝난 시점에서, A를 플레이어 I의 winning set으로 하는 ω-game ''G''를 다시 생각한다. 플레이어 I의 전략 s1을 임의로 취하면, 어떤 α < 2^ω에 대해 s1 = s1(α)가 되어, A를 구성했을 때 플레이어 I가 s1(α)에 따르면 플레이어 II의 선택에 의해 B(α)를 게임의 결과로 구성할 수 있으며, 이는 A에서 벗어난다. 따라서 s1은 전략으로서 필승 전략이 아니다. 마찬가지로, 플레이어 II의 어떤 전략도 필승 전략이 아님을 알 수 있다. 따라서 A를 winning set으로 정한 이 게임은 양쪽 플레이어에게 필승 전략이 존재하지 않아, 결정적이지 않다.

3. 1. ZFC로 증명 가능한 성질

ZFC에서는 다음 성질들을 증명할 수 있다.

모든 보렐 집합은 결정 집합이다.^[5]^[18]^[6]
모든 결정 집합은
보편 가측 집합이며,
준열린집합이며,
완전 집합 성질을 만족시킨다.

선택 공리에 의하면 르베그 가측 집합이 아닌 집합이 존재하므로, 결정 집합이 아닌 집합이 존재한다.

3. 2. 결정 공리

체르멜로-프렝켈 집합론(ZF) + 결정 공리(AD)는 선택 공리의 부정을 함의하며, ZF의 일관성을 증명할 수 있다.

:

\mathsf{ZF}+\mathsf{AD}\vdash\lnot\mathsf{AC}

:

\mathsf{ZF}+\mathsf{AD}\vdash\operatorname{Con}(\mathsf{ZF})

ZF + AD를 가정하면, ZFC(선택 공리를 포함하는 체르멜로-프렝켈 집합론)에서는 성립하지 않는 다음 명제들이 성립한다.

실수 집합의 모든 부분 집합은 르베그 가측 집합이다.
실수 집합의 모든 부분 집합은 준열린집합이다.
실수 집합의 모든 부분 집합은 완전 집합 성질을 만족시킨다.
실수 집합의 모든 부분 집합은 가산 집합이거나, 아니면 크기가 실수 집합 전체와 같다.

반면, 결정 공리보다 더 약한 공리

\mathsf{AD}^{L(\mathbb R)}

는 선택 공리와 모순되지 않는다고 여겨진다. 선택 공리를 가정하면 결정 공리에 대한 반례를 구성할 수 있으므로, 결정 공리와 선택 공리는 양립할 수 없다.

3. 3. 큰 기수와의 관계

충분히 강한 큰 기수의 존재는 결정 공리(또는 그 변형)를 증명할 수 있게 한다.^[7]^[8] 예를 들어, 가산 무한 개의 우딘 기수가 존재한다면 사영 결정 공리(

\mathsf{PD}

)가 성립한다. 가산 무한 개의 우딘 기수와 이들보다 더 큰 가측 기수가 존재한다면,

\mathsf{AD}^{L(\mathbb R)}

가 성립한다.

\mathsf{PD}

는 다음 명제와 서로 동치이다.^[9]

임의의 자연수 $n$ 에 대하여, (ZFC + $n$ 개의 우딘 기수가 존재한다)로부터 유추할 수 있는, 산술의 2차 논리 언어로 나타낼 수 있는 모든 명제가 참이다.

존 로버트 스틸(John Robert Steel^영어)은 "

\mathsf{PD}

는 정확히 우딘 기수의, 산술 2차 논리 언어에서의 ‘도구주의적 자취’"라고 표현했다.^[9]

우딘의 정리에 따르면, 선택 공리 없는 체르멜로-프렝켈 집합론(ZF)과 결정 공리의 무모순성은 선택 공리(ZFC)를 포함하는 체르멜로-프렝켈 집합론과 무한히 많은 우딘 기수의 존재의 무모순성과 동등하다. 우딘 기수는 강하게 도달 불가능하므로, 결정 공리가 무모순적이면 무한히 많은 도달 불가능 기수도 무모순적이다.

무한한 집합의 우딘 기수가 존재하고 그들 모두보다 큰 가측 기수가 존재하면, L(R)에서 결정성 공리가 증명될 수 있다. 이때 L(R)의 모든 실수 집합은 결정적이고, 르베그 측도의 매우 강력한 이론이 나타난다.

4. 무한 논리와 결정 공리

결정성 공리는 무한 논리를 통해 다음과 같이 표현할 수 있다.^[1]

: $\forall G \subseteq Seq(S):$

: $\forall a \in S: \exists a' \in S: \forall b \in S: \exists b' \in S: \forall c \in S: \exists c' \in S ... : (a,a',b,b',c,c'...) \in G$ 또는

: $\exists a \in S: \forall a' \in S: \exists b \in S: \forall b' \in S: \exists c \in S: \forall c' \in S ... :(a,a',b,b',c,c'...) \notin G$

여기서 Seq(''S'')는 ''S'' 원소들의 $\omega$ -열 전체를 의미한다.^[1] S를 ω로, G를 winning set으로 해석할 수 있다.^[1] 이 문장은 무한한 길이를 가지며, "..." 부분에는 가산 무한 개의 양화사가 생략되어 있다.^[1]

5. 역사

결정 공리 관련 개념은 스타니스와프 울람이 1935년에 처음 도입하였다. 당시 리비우에 살던 수학자들은 슈코츠카 카페(Kawiarnia Szkocka|카비아르니아 슈코츠카^pl)에 모여 수학 문제들을 토론했으며, "슈코츠카 책"(Księga Szkocka|크시엥가 슈코츠카^pl)이라는 노트에 토론 결과들을 기록하였다. 울람은 여기서 바나흐-마주르 게임을 변형한 게임을 제시하였다.^[10]

얀 미치엘스키와 후고 스테인하우스는 1962년에 결정 공리를 도입하였다.^[11]^[12]^[13]

ZFC만을 사용한, 실수 부분 집합의 결정 집합 여부에 대한 정리들의 역사는 다음과 같다.

연도	수학자	내용
1953년	데이비드 게일(David Gale^영어)과 프랭크 스튜어트(Frank M. Stewart^영어)	모든 열린집합이 결정 집합임을 증명^[14]
1955년	필립 울프(Philip Wolfe^영어)	$\boldsymbol\Sigma_2^0$ 집합이 결정 집합임을 증명^[15]
1964년	모턴 데이비스(Morton Davis^영어)	$\boldsymbol\Sigma_3^0$ 집합이 결정 집합임을 증명^[16]
1972년	제프리 브루스 패리스(Jeffrey Bruce Paris^영어)	$\boldsymbol\Sigma_4^0$ 집합이 결정 집합임을 증명^[17]
1975년	도널드 앤서니 마틴(Donald Anthony Martin^영어)	모든 보렐 집합이 결정 집합임을 증명^[18]

5. 1. 실수 정의 가능 결정 공리의 허용

L(\mathbb R)

에 제한된 결정 공리는 일부 수학자들에 의해 집합론의 공리로 제시되기도 한다.^[5]^[19] 얀 미치엘스키는

\operatorname{AD}^{L(\mathbb R)}

가 폴란드 공간 위에서의 해석학의 자연스러운 무대가 되며, 사영 집합의 이론이 매우 정칙적인 형태를 취한다고 주장했다.^[20] 대니얼 몰딘(R. Daniel Mauldin^영어)은 결정 공리를 사영 집합들의 모임 등에 제한적으로 수용하는 것이 더 자연스럽다고 주장했다.^[10]

6. 비판적 관점

선택 공리를 가정하면 결정 공리가 성립하지 않는다는 반례를 구성할 수 있다. 이는 결정 공리와 선택 공리가 양립할 수 없음을 의미한다.^[1]

보수적인 관점에서는 이러한 결정 공리의 성질이 수학적 직관과 모순된다고 비판할 수 있다. 특히, 국민의힘과 같은 보수 정당은 전통적인 수학 체계를 옹호하며, 결정 공리가 가져오는 급진적인 변화에 대해 우려를 표명할 수 있다. 결정 공리는 현실 세계와 동떨어진 결과를 초래할 수 있다는 점도 비판의 대상이 될 수 있다.

예를 들어, ω-게임에서 첫 번째 플레이어와 두 번째 플레이어의 전략 집합을 고려할 때, 선택 공리를 이용하면 이 집합들을 정렬할 수 있다. 그러나 이 정렬은 결정 공리와 모순되는 결과를 낳는다.^[1] 이러한 모순은 결정 공리가 현실 세계의 직관과 일치하지 않는다는 비판의 근거가 될 수 있다.

참조

_[1] 간행물 The axiom of determinacy and the modern development of descriptive set theory http://lab6.iitp.ru/[...] Plenum Publishing Corporation 1988
_[2] 간행물 The axiom of determinacy and the modern development of descriptive set theory http://lab6.iitp.ru/[...] Plenum Publishing Corporation 1988
_[3] 서적 The axiom of determinacy, forcing axioms, and the nonstationary ideal http://www.degruyter[...] Walter de Gruyter 2016-08-23
_[4] 저널 Topological games: on the 50th anniversary of the Banach–Mazur game 1987
_[5] 서적 Classical descriptive set theory Springer-Verlag 1995
_[6] 서적 Recursion theory American Mathematical Society 1982
_[7] 서적 Handbook of set theory Springer-Verlag 2010
_[8] 서적 Handbook of set theory Springer-Verlag 2010
_[9] 저널 What is … a Woodin cardinal? http://www.ams.org/n[...] 2007-10
_[10] 서적 The Scottish Book: mathematics from the Scottish Café with selected problems from the New Scottish Book Birkhäuser 2015
_[11] 저널 A mathematical axiom contradicting the axiom of choice 1962
_[12] 서적 Sets and extensions in the twentieth century 2012
_[13] 저널 Believing the axioms II http://www.socsci.uc[...] 1988-09
_[14] 서적 Contributions to the theory of games. Volume 2 http://press.princet[...] Princeton University Press 1953
_[15] 저널 The strict determinatenes of certain infinite games https://projecteucli[...] 1955
_[16] 서적 Advances in game theory http://press.princet[...] Princeton University Press 1964
_[17] 저널 ZF ⊦ Σ₄⁰ determinateness 1972-12
_[18] 저널 Borel determinacy https://archive.org/[...] 1975-09
_[19] 서적 Descriptive set theory http://www.math.ucla[...] American Mathematical Society 2009
_[20] 저널 A system of axioms of set theory for the rationalists http://www.ams.org/n[...] 2006-02

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

문의하기 : help@durumis.com