나스터-타르스키 정리

이 기사는 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수 있습니다. 기술적인 내용은 삭제하지 않고 비전문가도 이해할 수 있도록 개선을 도와주시기 바랍니다. (2023년 2월) (본 템플릿 메시지 삭제 방법 및 시기 알아보기)

질서와 격자 이론의 수학적 영역에서 브로니스와프 크나스터와 알프레드 타르스키의 이름을 딴 크나스터-타르스키 정리는 다음과 같이 말합니다.

(L, ≤)를 완전한 격자라 하고 f : L → L을 순서 보존 ( monot) 함수 w.r.t. ≤라 하자. 그러면 L에서 f 의 고정점들의 집합은 ≤ 아래의 완전한 격자를 형성합니다.

그 결과를 가장 일반적인 형태로 진술한 것은 타르스키였기 때문에,^[1] 그 정리는 종종 타르스키의 고정점 정리로 알려져 있습니다.얼마 전, 크나스터와 타르스키는 L이 집합의 부분집합의 격자인 거듭제곱집합 격자에 대한 결과를 확립했습니다.^[2]

이 정리는 게임 이론뿐만 아니라 프로그래밍 언어와 추상적 해석의 형식적 의미론에 중요한 응용을 가지고 있습니다.

이 정리의 일종의 반전은 앤 C에 의해 증명되었습니다. 데이비스:격자 L 위의 모든 차수 보존 함수 f : L → L이 고정된 점을 갖는다면, L은 완전한 격자입니다.

결과: 최소 및 최대 고정점

완전한 격자는 비어 있을 수 없기 때문에(빈 집합의 최댓값과 최솟값을 포함해야 함), 특히 이 정리는 최소 고정점(또는 최대 고정점)의 존재를 보장합니다.많은 실제적인 경우에, 이것은 그 정리의 가장 중요한 의미입니다.

f 의 최소 고정점은 f(x) = x 또는 f(x) ≤ x와 동등한 최소 요소 x이며, 이중은 최대 고정점을, f(x) = x와 같은 최대 요소 x를 갖습니다.

모든 오름차순 x에 대해 f(림 x) = 림 f(x)이면 f의 최소 고정점은 림 f(0)이고 여기서 0은 L의 최소 요소이므로 더 "construct적"인 버전의 정리를 제공합니다.(참조: Cleene 고정점 정리)보다 일반적으로 f가 단조라면, f의 최소 고정점은 f(0)의 정지 극한으로, α를 서수 위에 가져갑니다. 여기서 f는 트랜스피니트 유도에 의해 정의됩니다: f = f (f), f는 γ보다 작은 모든 β 서수 위에 대한 f의 최소 상한입니다.이중 정리는 최대 고정점을 의미합니다.

예를 들어, 이론 컴퓨터 과학에서 단조 함수의 최소 고정점은 프로그램 의미론을 정의하는 데 사용됩니다. 예를 들어 최소 고정점 § 표시 의미론을 참조하십시오.종종 더 전문화된 버전의 정리가 사용되는데, 여기서 L은 부분집합 포함에 의해 순서화된 특정 집합의 모든 부분집합의 격자로 가정됩니다.이는 많은 애플리케이션에서 그러한 격자만을 고려한다는 사실을 반영합니다.그런 다음 하나는 보통 함수 f의 고정된 점의 속성을 갖는 가장 작은 집합을 찾습니다.추상적 해석은 크나스터-타르스키 정리와 최소 및 최대 고정점을 제공하는 공식을 충분히 활용합니다.

크나스터-타르스키 정리는 칸토어-번스타인-슈뢰더 정리의 간단한 증명을 위해 사용될 수 있습니다.^[5][6]

약한 버전의 정리

약한 버전의 크나스터-타르스키 정리는 순서 집합에 대해 공식화될 수 있지만 더 복잡한 가정을 수반합니다.예를 들어,

L을 최소 원소(아래)를 갖는 부분 순서 집합이라 하고 f: L → L을 단조 함수라 합니다. 또한, f(u) ≤ u인 L에 u가 존재하고 부분 ${\displaystyle \mathrm{집합}}$ $\{$ ${\displaystyle x}$ ${\displaystyle \in }$ ${\displaystyle L}$ ∣ ${\displaystyle x}$ ≤ f ( x ), $x$ ≤ u }${\displaystyle$ \{$x\in L\mid x\$leq f(x)), x\leq u\}에 최댓값이 있는 경우를 가정합니다. 그러면 f는 최소 고정점을 인정합니다.

이것은 불변 집합에 대한 다양한 정리를 구하는 데 적용될 수 있습니다. 예를 들어, Ok의 정리:

X의 (닫혀 있는) 비어 있지 않은 부분집합들의 (닫혀 있는) 단조 맵 F : P(X) → P(X)에 대하여, 다음은 동치입니다: (o) F는 P(X) s.t.에서 A를 허용합니다. ⊆ F $(A$) ${\displaystyle$ A$\subseteq$ F(A)}, (i) F는 P(X)에서 불변 집합 A를 허용합니다. 즉, ${\displaystyle }{\displaystyle A}$ = ${\displaystyle F}$(A$)$ {\displaysty${\displaystyle l}$e A = F(A)}, (ii) F는 최대 불변 집합 A를 인정하고, (iii) F는 최대 불변 집합 A를 인정합니다.

특히, Knaster-Tarski 원리를 사용하면 비압축적 불연속(다중값) 반복 함수 시스템에 대한 글로벌 어트랙터 이론을 개발할 수 있습니다.약한 수축 반복 함수 시스템의 경우 칸토로비치 고정점 정리(타르스키-칸토로비치 고정점 원리라고도 함)로 충분합니다.

순서 집합에 대한 고정점 원리의 다른 적용은 미분, 적분 및 연산자 방정식 이론에서 비롯됩니다.

증명

그 정리를 다시 설명해 보겠습니다.

L 위의 $완전$한 $격자$⟩ L, ≤$$lang {\displaystyle \colonle L,\leq \rangle } 및 모노톤 함수 f : L → L {\displaystyle f\lang L\right arrow L}의 경우, f 의 모든 고정점 집합도 완전한 격자 ⟨ P, ≤ ⟩ {\displaystyle \⟨le P,\leq \rangle }이며, 다음과 같습니다.

• ${\displaystyle \bigvee }{\displaystyle P}$ ${\displaystyle =}$⋁${\displaystyle }${x ${\displaystyle \in }$ L ∣ x ≤ f ( x ) } {\displaystyle \big${\displaystyle v}$e P=\bigve \{x\in L\mid x\leq f (x))\}를 최대 고정점 off로 합니다.
• ${\displaystyle \bigwedge }{\displaystyle P}$ ${\displaystyle =}$ ⋀ $x$ ${\displaystyle \in }$ L ${\displaystyle \mid }$ x ≥ f ( x ) } {\displaystyle \bigwed${\displaystyle g}$e P=\bigwedge \{x\in L\mid x\geq f (x))\}를 최소 고정점 off로 합니다.

증명. P가 최소 원소와 최대 원소를 모두 가지고 있음을 보여 주는 것으로 시작합니다.D = {x x ≤ f(x)}, x ∈ D라고 하자 (적어도 0은 D에 속함).그렇다면 f는 단조이므로 f(x) ≤ f(x), 즉 f(x) ∈ D를 갖습니다.

$이제$ = ⋁$$D {\$displaystyle$ u=\bigve D}(D ⊆ L과 L이 완전한 격자이기 때문에 u가 존재함)라고 합니다.그렇다면 모든 x ∈ D에 대하여 x ≤ u이고 f(x) ≤ f(u)이므로 x ≤ f(x) ≤ f(u)인 것이 사실입니다.따라서 f(u)는 D의 상한이지만 u는 최소 상한이므로 u ≤ f(u), 즉 u ∈ D.그러면 f(u) ∈ D(f(u) ≤ f(u))이고 f(u) ≤ u이므로 f(u) = u를 따릅니다. 모든 고정점이 D에 있으므로 u가 f의 가장 큰 고정점이 됩니다.

함수 f는 이중 (완전) ${\displaystyle {\mathrm{격자}}^{}}$ ⟨$Lop$, ≥ ⟩ ${\displaystyle$ \langle L^{op},\geq \rangle }에서 단조입니다. 우리가 방금 증명했듯이, 그것의 가장 큰 고정점이 존재합니다.L의 최소 고정점이므로 P는 최소 및 최대 요소를 갖는데, 보다 일반적으로 완전한 격자 위의 모든 단조 함수는 최소 고정점 및 최대 고정점을 갖습니다.

a, l의 b에 대해서는 경계 a 및 b가 있는 닫힌 구간에 대해 [a, b]라고 씁니다: {x ∈ La ≤ x ≤ b}.$a$ ≤ b이면 ⟨ {\$displaystyle$\langle$\}$ [$a$ b$],$ ≤ ⟩ ${\displaystyle$ \rangle}은(는) 완전한 격자입니다.

P가 완전한 격자라는 것은 증명되어야 합니다.$1$ ${\displaystyle L_{}}$ = ⋁ L ${\displaystyle$ 1_{$L}$=$\$bigve L}, W ⊆ P 및 w = ⋁ W {\displaystyle w=\bigve W}라고 합니다. f([w, 1]) ⊆ [w, 1]임을 보여줍니다.실제로 모든 x ∈ W에 대해 x = f(x)를 가지며, w는 W의 최소 상한이므로 x ≤ f(w)입니다.특히 w ≤ f(w).그런 다음 y ∈ [w, 1]에서 w ≤ f(w) ≤ f(y) ≤ f(y) ∈ [w, 1] 또는 단순히 f([w, 1]) ⊆ [w, 1]을 제공하는 것입니다.이를 통해 f를 완전한 격자 위의 함수로_L 볼 수 있습니다 [w, 1].그러면 최소 고정점을 가지며, W의 최소 상한을 제공합니다. P의 임의의 부분 집합이 우월함, 즉 P가 완전한 격자라는 것을 보여주었습니다.

타르스키 고정점 계산

Chang, Lyuu, Ti는^[7] 순서 보존 함수가 값 오라클에 의해 주어졌을 때, 전체 순서 격자에서 타르스키 고정점을 찾는 알고리즘을 제시합니다.알고리즘에는 $O{\displaystyle (\log }$ ⁡ L) {\$displaystyle O(\$log L)}개의 쿼리가 필요하며, 여기서 L은 격자에 있는 요소의 개수입니다.반면, 일반 격자(오라클로 주어짐)의 경우$$ω(L) ${\displaystyle \Omega($L)} 쿼리의 하한을 증명합니다.

덩, 치, 예는^[8] 타르스키 고정점을 찾기 위한 몇 가지 알고리즘을 제시합니다.이들은 성분별 순서 지정과 사전식 순서 지정의 두 가지 유형의 격자를 고려합니다.이들은 함수 f에 대한 두 가지 종류의 입력, 즉 값 오라클 또는 다항 함수를 고려합니다.그들의 알고리즘은 다음과 같은 런타임 복잡도를 갖습니다(여기서 d는 차원의 수이고 N은_i 차원 i의 요소의 수임).

격자v입력 >	다항 함수	가치오라클
구성요소별	${\displaystyle O(poly(\log L))\cdot \log N_{1}\cdots \log N_{d}}$	${\displaystyle O(\log N_{1})\cdots \log N_{d})\대략 O(\log ^{d}L)}$
사전법	${\displaystyle O(poly(\log L)\cdot \log L)}$	${\displaystyle O(\log L)}$

알고리즘은 이진 탐색을 기반으로 합니다.반면, 주어진 고정점이 고유한지 여부를 결정하는 것은 계산적으로 어렵습니다.

격자v입력 >	다항 함수	가치오라클
구성요소별	coNP-완전한	${\displaystyle \Theta(N_{1}+\cdots +N_{d})}$
사전법	coNP-완전한	${\displaystyle \Theta (L)}$

d=2의 경우 성분별 격자와 값 oracle의 경우 O${\displaystyle ({로그}^{}}$ 2${\displaystyle {}^{}}$⁡ ${\displaystyle L}$) ${\displaystyle O(\$log ^{2}L)}의 복잡도가 최적입니다.그러나 d>2의 경우 더 빠른 알고리즘이 있습니다.

• Fearnley, Palvolgyi 및 Savani는 $O{\displaystyle ({log}^{}}$ ${\displaystyle 2^{}}$ ⌈$d$ / ${\displaystyle 3}$⌉ ⁡ $L){\displaystyle$O(\log ^{2\lceil/3\rceil }L)}개의 쿼리만을 사용하는 알고리즘을 제시했습니다.특히 d=3의 경우 O$log$ ${\displaystyle 2^{}}$ ⁡ L) {\$displaystyle O(\log$^{2}L)}개의 쿼리만 필요합니다.
• Chen과 Li은 $O{\displaystyle }$(${\displaystyle {\mathrm{로그}}^{}}$ ⌈${\displaystyle {}^{}}$(${\displaystyle {}^{}}$d + ${\displaystyle 1^{}}$ ) / $2$⌉ ⁡ L ) {\$displaystyle$ O $(\log ^{\lceil (d$+ 1 ) / 2\rceil }L)}개의 쿼리만을 사용하는 알고리즘을 제시했습니다.

게임이론의 응용

타르스키의 고정점 정리는 슈퍼모듈러 게임에 적용됩니다.^[8]슈퍼모듈러^[12] 게임(supermodular game)은 각 플레이어의 효용 함수에 차이가 증가하는 게임이기 때문에 플레이어의 가장 좋은 반응은 다른 플레이어의 전략의 함수가 약하게 증가하는 것입니다.예를 들어, 두 회사 간의 경쟁 게임을 생각해 보십시오.각 회사는 연구에 얼마나 많은 돈을 쓸지 결정해야 합니다.일반적으로, 한 기업이 연구에 더 많은 돈을 쓴다면, 다른 기업의 가장 좋은 반응은 역시 연구에 더 많은 돈을 쓰는 것입니다.일부 일반적인 게임은 Cournot 경쟁, Bertrand 경쟁 및 Investment 게임과 같이 슈퍼모듈형 게임으로 모델링될 수 있습니다.

최상의 반응 함수는 단조롭기 때문에 타르스키의 고정점 정리는 초모듈형 게임에서 순수 전략 내쉬 평형(PNE)의 존재를 증명하는 데 사용될 수 있습니다.게다가, Topkis는^[13] 슈퍼모듈러 게임의 PNE 세트가 완전한 격자이므로, 게임은 "가장 작은" PNE와 "가장 큰" PNE를 가지고 있음을 보여주었습니다.

Echenique는^[14] 초모듈형 게임에서 모든 PNE를 찾는 알고리즘을 제시합니다.그의 알고리즘은 먼저 가장 작은 PNE와 가장 큰 PNE를 찾기 위해 가장 좋은 반응 시퀀스를 사용합니다. 그런 다음, 그는 몇 가지 전략을 제거하고 모든 PNE를 찾을 때까지 반복합니다.그의 알고리즘은 최악의 경우 기하급수적이지만 실제로는 빠르게 실행됩니다.덩, 치, 예는^[8] 게임과 관련된 질서 보존 매핑의 타르스키 고정점을 찾음으로써 PNE를 효율적으로 계산할 수 있음을 보여줍니다.

참고 항목

• 모달 μ-계산기

메모들

참고문헌

• Andrzej Granas and James Dugundji (2003). Fixed Point Theory. Springer-Verlag, New York. ISBN 978-0-387-00173-9.
• Forster, T. (2003-07-21). Logic, Induction and Sets. ISBN 978-0-521-53361-4.

추가열람

• S. Hayashi (1985). "Self-similar sets as Tarski's fixed points". Publications of the Research Institute for Mathematical Sciences. 21 (5): 1059–1066. doi:10.2977/prims/1195178796.
• J. Jachymski; L. Gajek; K. Pokarowski (2000). "The Tarski-Kantorovitch principle and the theory of iterated function systems". Bull. Austral. Math. Soc. 61 (2): 247–261. doi:10.1017/S0004972700022243.
• E.A. Ok (2004). "Fixed set theory for closed correspondences with applications to self-similarity and games". Nonlinear Anal. 56 (3): 309–330. CiteSeerX 10.1.1.561.4581. doi:10.1016/j.na.2003.08.001.
• B.S.W. Schröder (1999). "Algorithms for the fixed point property". Theoret. Comput. Sci. 217 (2): 301–358. doi:10.1016/S0304-3975(98)00273-4.
• S. Heikkilä (1990). "On fixed points through a generalized iteration method with applications to differential and integral equations involving discontinuities". Nonlinear Anal. 14 (5): 413–426. doi:10.1016/0362-546X(90)90082-R.
• R. Uhl (2003). "Smallest and greatest fixed points of quasimonotone increasing mappings". Mathematische Nachrichten. 248–249: 204–210. doi:10.1002/mana.200310016.

외부 링크

• J. B. 네이션, 격자 이론에 관한 주석.
• 기본 조합 문제에 대한 응용 프로그램:100페이지와 100개의 레마로 구성된 책이 주어지면, 색인과 같은 페이지에 어떤 레마가 적혀있는지 증명해보세요.