보렐 결정성 정리

기술 세트 이론에서 보렐 결정권 정리는 보렐 세트인 게일-스튜와트 경기가 결정된다고 명시하고 있는데, 이는 두 선수 중 한 명이 이 경기의 승리 전략을 갖게 된다는 것을 의미한다.게일-스튜어트 게임은 두 선수 모두 완벽한 정보를 갖고 있고 무작위성이 개입되지 않는 무한 2인승 게임이다.

그 정리는 유한한 게임의 결정성에 관한 제르멜로의 정리를 멀리까지 일반화한 것이다.그것은 도날드 A에 의해 증명되었다. 1975년 마틴, 폴란드 공간의 보렐 세트가 완벽한 세트 속성과 바이얼의 속성과 같은 규칙성 성질을 가지고 있다는 것을 보여주기 위해 기술 세트 이론에 적용되었다.

그 정리는 변태적인 성질로도 알려져 있다.정리가 증명되기 전인 1971년, 하비 프리드먼은 제르멜로-프렌켈 집합 이론에서 정리에 대한 어떤 증거도 대체의 공리를 반복적으로 이용해야 한다는 것을 보여주었다.이후의 결과는 비록 그들이 상대적으로 그것과 일치하지만, 특정한 큰 추기경들이 일치한다면, 더 강한 결정성 이론은 Zermelo-Fraenkel 집합 이론에서 증명될 수 없다는 것을 보여주었다.

배경

게일-스튜어트 경기

게일-스튜어트 게임은 완벽한 정보를 담은 2인용 게임이다.게임은 세트 A를 사용하여 정의되며, G로_A 표시된다.두 선수가 번갈아 돌아가며, 각 선수는 다음 동작을 하기 전에 모든 동작을 인지한다.각 턴마다 각 플레이어는 A의 단일 요소를 선택하여 플레이한다.동일한 요소를 제한 없이 두 번 이상 선택할 수 있다.게임은 다음과 같은 도표를 통해 시각화할 수 있는데, 이 도표는 왼쪽에서 오른쪽으로 움직이며, 위의 I 선수와 아래의 II 선수의 동작으로 볼 수 있다.

${\begin{matrix}\mathrm {I} &a_{1}&\quad &a_{3}&\quad &a}&\cdots \\\mathrm {}II} &\quad &a_{2}&\quad &a_{4}&\quad &a_{6}&\cdots \end{matrix}}}$

플레이는 끝이 없이 계속되기 때문에, 게임의 한 번의 플레이가 A의 $\langle a_{1},a_{2},a_{3}\ldots \rangle$ 의 $\langle a_{1},a_{2},a_{3}\ldots \rangle$ $\langle a_{1},a_{2},a_{3}\ldots \rangle$ , $\langle a_{1},a_{2},a_{3}\ldots \rangle$ , $\langle a_{1},a_{2},a_{3}\ldots \rangle$ … $\langle a_{1},a_{2},a_{3}\ldots \rangle$ ⟩ {\ $displaystyle \langle a_{1},a_{2},a_{3}\ldots \rangle$ }}의 무한 시퀀스를 결정한다.그러한 모든 시퀀스의 집합은 A로^ω 표시된다.선수들은 경기 초반부터 누가 이기느냐를 가를 고정된 페이오프 세트(승부 세트)를 알고 있다.지불 세트는 A의^ω 하위 집합이다.게임 플레이가 만들어낸 무한 시퀀스가 성과급 세트 안에 있다면 내가 이기는 것이다.그렇지 않으면, 2번 선수가 이긴다. 동점이 없다.

이러한 정의는 처음에는 체스와 같은 전통적인 완벽한 정보 게임을 포함하지 않는 것처럼 보인다. 왜냐하면 그러한 게임에서 이용 가능한 일련의 움직임들이 매 턴마다 변화하기 때문이다.그러나 이러한 경우는 불법적인 움직임을 하는 선수가 즉시 패한다고 선언함으로써 처리할 수 있어 게일-스튜어트 개념의 게임이 실제로 게임 트리에 의해 정의되는 게임의 개념을 일반화한다.

승리전략

선수 승리 전략은 선수가 그 기능을 따라간다면 반드시 승리할 수 있도록 게임 내 어떤 위치에서든 어떤 움직임을 보일지를 알려주는 기능이다.구체적으로는 선수 I의 승리전략은 짝수 길이의 A 요소의 입력 시퀀스로 받아들여 A의 요소를 반환하는 기능 f로, 플레이어가 폼의 모든 플레이를 이기도록 한다.

${\begin{matrix}\mathrm {I} &a_{1}=f(\langle \rangle )&\quad &a_{3}=f(\langle a_{1},a_{2}\rangle )&\quad &a_{5}=f(\langle a_{1},a_{2},a_{3},a_{4}\rangle )&\quad &\cdots \\\mathrm {II} &\quad &a_{2}&\quad &a_{4}&\quad &a_{6}&\cdots .\end{matrix}}}}$

선수 II의 승리 전략은 선수 II가 폼의 모든 플레이를 이길 수 있도록 A의 요소의 홀수 길이의 시퀀스를 취하고 A의 요소를 반환하는 함수 g이다.

${\begin{matrix}\mathrm {I} &a_{1}&\quad &a_{3}&\quad &a}&\cdots \\\mathrm {}II} &\quad &a_{2}=g(\langle a_{1}\rangle )&\quad &a_{4}=g(\langle a_{1},a_{2},a_{3}\rangle )&\quad &a_{6}=g(\langle a_{1},a_{2},a_{3},a_{4},a_{5}\rangle )&\cdots .\end{matrix}}$

두 선수 모두 승리 전략을 가지고 있고, 서로 상대적인 전략을 구사했다면, 두 선수 중 한 명만이 승리할 수 있을 것이다.선수 중 한 명이 특정 세트에서 승리 전략을 구사할 경우 해당 세트가 결정된다고 한다.

위상

주어진 집합 A의 경우 A의^ω 부분집합이 결정될지는 위상 구조에 따라 어느 정도 달라진다.Gale-Stewart 게임의 목적상, 세트 A는 이산 토폴로지를 부여받고^ω, 결과 제품 토폴로지를 부여받으며, 여기서 A는^ω A의 무한한 토폴로지 제품으로 간주된다.특히 A가 세트 {0,1}일 때 A에^ω 정의된 위상은 정확히 칸토어 공간의 일반 위상이고, A가 자연수 집합일 때는 베이어 공간의 일반 위상이다.

A^ω 집합은 특정 트리를 통과하는 경로 집합으로 볼 수 있으며, 이는 위상의 두 번째 특성화로 이어진다.트리는 A 원소의 모든 유한 염기서열로 구성되며, 트리의 특정 노드 σ의 자녀는 정확히 하나의 원소 σ을 확장하는 염기서열이다.따라서 A = { 0, 1 }인 경우 트리의 첫 번째 레벨은 sequences 0, 0 and, 1 0, ⟨ 0, 1 ⟩, ⟨ 등 4개의 시퀀스로 구성된다.나무의 각 유한 시퀀스 σ에 대해, σ으로 시작하는 A의^ω 모든 원소의 집합은 A의 위상에 있는 기본 오픈 세트다.A의^ω 오픈 세트는 이 기본 오픈 세트의 조합으로서 정확하게 표현할 수 있는 세트들이다.닫힌 세트는 평소와 마찬가지로 보어가 열린 세트다.

A의^ω 보렐 세트는 오픈 세트를 포함하는 A의^ω 가장 작은 하위 세트 등급이며, 보완 및 계수 가능한 조합으로 폐쇄된다.즉, 보렐 세트는 모든 오픈 세트를 포함하는 A의^ω 하위 세트 중에서 가장 작은 smallest-알지브라이다.보렐 세트는 개방형 세트에서 그것들을 생산하기 위해 얼마나 많은 보완 및 계수 가능한 유니언의 작업이 필요한지에 기초하여 보렐 계층 구조로 분류된다.

이전 결과

Gale과 Stewart(1953)는 만약 지불 세트가 A의^ω 공개 또는 폐쇄 서브셋이라면, 그 지불 세트를 가진 Gale-Stewart 경기는 항상 결정된다는 것을 증명했다.그 후 20년 동안, 이것은 보다 복잡한 증거를 통해 보렐 계급의 약간 더 높은 수준으로 확대되었다.이로 인해 유료 세트가 A의^ω 보렐 서브셋일 때마다 게임이 결정되어야 하는지에 대한 의문이 제기되었다.선택 공리를 사용하여 결정되지 않은 {0,^ω1}의 부분집합을 구성할 수 있는 것으로 알려졌다(Kechris 1995, 페이지 139).

하비 프리드먼(1971)은 칸토어 공간({0,1}^ω )의 모든 보렐 하위 집합이 결정되었다는 어떠한 증거도 칸토어 공간과 같은 "작은" 물체에 대한 이론의 입증에 일반적으로 필요하지 않은 공리인 교체 공리를 반복적으로 사용해야 한다는 것을 증명했다.

보렐 결정성

도널드 A. 마틴(1975)은 어떤 세트 A에 대해서도 A의^ω 모든 보렐 하위 집합이 결정된다는 것을 증명했다.원본 증명서는 상당히 복잡했기 때문에 마틴은 1982년에 기술기계가 그만큼 필요하지 않은 짧은 증명서를 발표했다.드레이크는 마틴의 논문에 대한 리뷰에서 두 번째 증거를 "놀라울 정도로 직설적인" 것으로 묘사하고 있다.

기술 집합 이론 분야는 폴란드 공간(본질적으로 완전한 분리 가능한 메트릭 공간)의 속성을 연구한다.보렐 결정성 정리는 이러한 공간의 보렐 하위 집합의 많은^{[citation needed]} 특성을 확립하기 위해 사용되어 왔다.예를 들어, 폴란드 공간의 모든 보렐 하위 집합은 완벽한 세트 속성과 바이어의 속성을 가지고 있다.

세트이론적 측면

보렐 결정성 정리는 기술 집합 이론에서의 결과뿐만 아니라 그것의 변성 특성에도 관심이 있다.

임의 A에 대한 폐쇄형 A^ω 집합의 결정성은 ZF에 대한 선택 공리와 동일하다(Kechris 1995, 페이지 139).선택 공리가 가정되지 않는 설정 이론 시스템에서 작업할 때, 이는 quasistategatees로 알려진 일반화된 전략(Kechris 1995, 페이지 139)을 고려하거나 결정성의 공리처럼 A가 자연수의 집합인 게임만 고려함으로써 우회될 수 있다.

제르멜로 집합론(Z)은 대체의 공리가 없는 제르멜로-프라엔켈 집합론이다.Z가 임의의 세트로 시작하여 전력 세트 작동이 헤아릴 수 없이 여러 번 반복될 수 있다는 것을 증명하지 못한다는 점에서 ZF와 다르다.특히, 누계 계층의 특정한 계수 가능한 수준인 V는_{ω + ω} 제르멜로 집합 이론의 모델이다.반면 교체의 공리는 by이 강하게 접근하기 어려운 추기경일 때와 같이 κ의 훨씬 큰 값에 대해서만 V가_κ 만족한다.프리드먼의 1971년의 정리는 보렐 결정성이 실패하는 (선택의 공리를 가진) 제르멜로 집합 이론의 모델이 있음을 보여주었고, 따라서 제르멜로 집합 이론은 보렐 결정성 정리를 증명할 수 없다.

모든 bets number of countable index의 존재는 보렐 결정성 정리를 입증하기에 충분하다.^[1]

더 강력한 결정성 형태

보렐 결정성보다 강한 결정성에 대한 몇 가지 설정 이론은 기술 집합 이론에서 연구된다.그들은 큰 추기경 공리와 밀접한 관련이 있다.

투사적 결정성의 공리는 폴란드 공간의 모든 투사적 하위 집합이 결정된다고 말한다.그것은 ZFC에서는 검증할 수 없는 것으로 알려져 있지만 그것과 비교적 일치하며 특정한 큰 기형적 공리에 의해 암시된다.측정 가능한 추기경의 존재는 폴란드 공간의 모든 분석적 하위 집합이 결정된다는 것을 ZFC에 암시하기에 충분하다.

결정성의 공리는 모든 폴란드 공간의 모든 하위 집합이 결정된다고 말한다.ZFC와 일치하지 않지만 ZF + DC(Zermelo-Fraenkel set 이론 + 종속 선택의 공리)에서는 특정 큰 기본 공리와 동일하다.

참조

^ Leinster, Tom (23 July 2021). "Borel Determinacy Does Not Require Replacement". The n-Category Café. The University of Texas at Austin. Retrieved 25 August 2021.

Friedman, Harvey (1971). "Higher set theory and mathematical practice". Annals of Mathematical Logic. 2 (3): 325–357. doi:10.1016/0003-4843(71)90018-0.
- L. Bukovský, Reviewer, MR284327 .
Gale, D. and F. M. Stewart (1953). "Infinite games with perfect information". Contributions to the theory of games, vol. 2. Annals of Mathematical Studies, vol. 28. Vol. 28. Princeton University Press. pp. 245–266.
- S. 셔먼, 수리 검토, MR54922 .
Alexander Kechris (1995). Classical descriptive set theory. Graduate Texts in Mathematics. Vol. 156. ISBN 0-387-94374-9.
Martin, Donald A. (1975). "Borel determinacy". Annals of Mathematics. Second Series. 102 (2): 363–371. doi:10.2307/1971035.
- 존 버지스, 리뷰어Mathemical Reviews, MR403976 .
Martin, Donald A. (1982). "A purely inductive proof of Borel determinacy". Recursion theory. Proc. Sympos. Pure Math (Proceedings of the AMS–ASL summer institute held in Ithaca, New York ed.). pp. 303–308.
- F. R. 드레이크, 리뷰어, MR791065 .

외부 링크

보렐 결정성과 변성학.로스 브라이언트2001년 노스 텍사스 대학교 석사 논문.
스탠포드 철학 백과사전의 "대 추기경들과 결정력"

[1] Leinster, Tom (23 July 2021). "Borel Determinacy Does Not Require Replacement". The n-Category Café. The University of Texas at Austin. Retrieved 25 August 2021.

[1]

Search