타르스키 고정점 정리

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

1. 개요
2. 정의
- 2.1. 최대·최소 고정점
- 2.2. 증명
3. 고정점 집합의 성질
4. 귀결
5. 역
- 5.1. 역의 증명
6. 일반화
- 6.1. 일반화의 증명
7. 약한 버전의 정리
8. 타르스키 고정점 계산
- 8.1. 알고리즘 복잡도
- 8.2. 유일성 판정
9. 게임 이론에서의 응용
10. 역사
참조

1. 개요

타르스키 고정점 정리는 완비 격자 위 단조 함수의 고정점 집합이 완비 격자를 이룬다는 정리이다. 이 정리는 최소 고정점과 최대 고정점의 존재를 보장하며, 이들의 구체적인 형태를 제시한다. 또한, 고정점 집합이 원래 격자의 부분 격자가 아닐 수 있음을 보여주는 예시를 제공한다. 이 정리는 다양한 분야에서 활용되며, 특히 이론 컴퓨터 과학, 게임 이론, 그리고 역학계 이론에서 중요한 역할을 한다.

더 읽어볼만한 페이지

고정점 정리 - 바나흐 고정점 정리
바나흐 고정점 정리는 완비 거리 공간에서 축약 사상이 유일한 고정점을 가짐을 보장하는 정리로, 다양한 수학적 정리 증명 및 문제 해결에 응용되며 역과 일반화가 존재한다.
고정점 정리 - 브라우어르 고정점 정리
브라우어르 고정점 정리는 콤팩트 볼록 집합에서 자기 자신으로 가는 연속 함수는 반드시 고정점을 가진다는 정리로, 다양한 공간에서 여러 형태로 표현되며 함수해석학에서 중요한 역할을 한다.
격자 이론 - 직교 여원 격자
직교 여원 격자는 모든 원소가 여원을 가지는 유계 격자로서, 유계 분배 격자에서 최대 하나의 여원을 가지며 논리 회로 설계, 양자 컴퓨팅, 데이터 분석 등 다양한 분야에 응용된다.
격자 이론 - 완비 격자
완비 격자는 모든 부분 집합이 상한과 하한을 갖는 부분 순서 집합으로, 격자 이론에서 중요한 개념이며 다양한 수학 분야에서 활용된다.

타르스키 고정점 정리
개요
종류	순서 이론, 격자 이론
분야	수학
이름 붙여진 사람	브로니스와프 크나스터, 알프레드 타르스키
설명
내용	완전 격자 L의 완전 격자 L에서 단조 함수 f: L → L은 최소한 하나의 고정점을 가짐
관련된 개념	고정점

2. 정의

완비 격자 $L$ 과 단조함수 $f\colon L\to L$ 가 주어졌다고 하자. '''타르스키 고정점 정리'''에 따르면, $f$ 의 고정점의 집합

: $\operatorname{fix}(f)=\{a\in L\colon f(a)=a\}$

역시 완비 격자를 이룬다. (그러나, $\operatorname{fix}(f)$ 가 $L$ 의 부분 격자일 필요는 없다. 즉, $\operatorname{fix}(f)$ 에서의 상한과 하한은 $L$ 에서와 일치하지 않을 수 있다.) 특히, $f$ 의 최대 고정점과 최소 고정점이 존재하며, 특히 $f$ 는 적어도 하나의 고정점을 갖는다. 또한, $f$ 의 최대·최소 고정점은 각각 다음과 같이 주어진다.

: $\bigvee\operatorname{fix}(f)=\bigvee\{a\in L\colon a\le f(a)\}$

: $\bigwedge\operatorname{fix}(f)=\bigwedge\{a\in L\colon a\ge f(a)\}$

2. 1. 최대·최소 고정점

''f''의 최소 고정점은 ''f''(''x'') = ''x''이거나, 동등하게 ''f''(''x'') ≤ ''x''를 만족하는 최소 원소 ''x''이고, 쌍대는 ''f''(''x'') = ''x''를 만족하는 최대 원소 ''x''인 최대 고정점에 대해 성립한다.^[4] 쌍대 정리는 최대 고정점에 대해 성립한다.^[4] 추상 해석은 크나스터-타르스키 정리를 광범위하게 사용하며, 최소 및 최대 고정점을 제공하는 공식을 활용한다.

2. 2. 증명

타르스키를 따라, 다음 순서대로 증명한다.

(가) $\textstyle\bigvee\{a\in L\colon a\le f(a)\}$ 는 $f$ 의 최대 고정점이다.
(나) $\textstyle\bigwedge\{a\in L\colon a\ge f(a)\}$ 는 $f$ 의 최소 고정점이다.
(다) $\operatorname{fix}(f)$ 는 완비 격자이다.

명제 (가)의 증명.

M=\{a\in L\colon a\le f(a)\}

라고 하자. 임의의

a\in M

에 대하여,

\textstyle a\le\bigvee M

이므로,

\textstyle a\le f(a)\le f\left(\bigvee M\right)

이다. 따라서

\textstyle\bigvee M\le f\left(\bigvee M\right)

이다.

\textstyle f\left(\bigvee M\right)\le f\left(f\left(\bigvee M\right)\right)

이므로,

M

의 정의에 따라

\textstyle f\left(\bigvee M\right)\in M

이다. 따라서

\textstyle f\left(\bigvee M\right)\le\bigvee M

이다. 따라서,

\textstyle\bigvee M

은

f

의 고정점이다. 모든 고정점은

M

에 속하므로,

\textstyle\bigvee M

은

f

의 최대 고정점이다.

명제 (나)의 증명.

L

의 반대 격자

L^{\operatorname{op}}

를 생각하자.

L^{\operatorname{op}}

역시 완비 격자를 이루며,

f

는

L^{\operatorname{op}}

위에서도 단조함수이다. 따라서

L^{\operatorname{op}}

에 대하여 명제 (가)가 성립한다. 이는 정확히

L

에 대한 명제 (나)와 일치한다.

명제 (다)의 증명.

S

가

\operatorname{fix}(f)

의 임의의 부분 집합이라고 하자.

\operatorname{fix}(f)

에서

S

의 상한이 존재함을 보이면 충분하다.

S

의

L

에서의 상한

\textstyle\bigvee S

를 생각하자. 그렇다면 구간

\textstyle\left[\bigvee S,\top\right]=\left\{a\in L\colon a\ge\bigvee S\right\}

는

S

의 상계의 집합이며, 완비 격자를 이룬다. 임의의

s\in S

에 대하여

\textstyle s=f(s)\le f\left(\bigvee S\right)

이므로,

\textstyle\bigvee S\le f\left(\bigvee S\right)

이다.

a\in L

에 대하여, 만약

\textstyle a\ge\bigvee S

라면,

\textstyle f(a)\ge f\left(\bigvee S\right)\ge\bigvee S

이다. 따라서,

f

를

\textstyle\left[\bigvee S,\top\right]

위의 함수

\textstyle f'\colon\left[\bigvee S,\top\right]\to\left[\bigvee S,\top\right]

로 여길 수 있다. 명제 (나)에 따라,

f'

의 최소 고정점이 존재한다. 이는

f

의 고정점이며,

S

의 상계가 되는 가장 작은

f

의 고정점이다. 다시 말해,

S

의

\operatorname{fix}(f)

에서의 상한이다.

3. 고정점 집합의 성질

타르스키 고정점 정리에 따르면, 고정점 집합은 완비 격자를 이룬다. 하지만, 이 고정점 집합이 원래 격자의 부분 격자일 필요는 없다. 예를 들어, 다음과 같은 부분 순서 집합 $L=\{\bot,a,a',b,\top\}$ 을 생각해보자.

: $\bot$

이 경우 $L$ 은 완비 격자를 이룬다. 이제 함수 $f\colon L\to L$ 를 다음과 같이 정의하자.

: $f(x)=x\qquad(x=\bot,a,a',\top)$

: $f(b)=\top$

이 함수 $f$ 는 $L$ 위의 단조함수이며, $a$ 와 $a'$ 은 $f$ 의 고정점이다. 하지만, $a\vee a'=b$ 는 $f$ 의 고정점이 아니다. 왜냐하면 $a$ 와 $a'$ 의 $\operatorname{fix}(f)$ 에서의 상한은 $b$ 가 아닌 $\top$ 이기 때문이다. 따라서, $\operatorname{fix}(f)$ 는 $L$ 의 부분 격자가 아니다.

4. 귀결

완비 격자는 공집합일 수 없으므로, 타르스키 고정점 정리는 단조 함수 f에 적어도 하나의 고정점이 있음을, 나아가서 최소 고정점이 있음을 보장한다. 임의의 부분 순서 집합에 대하여 유사한 결과를 증명할 수 있으며, 이를 동역학계 이론에 적용하여 프랙탈의 일종인 반복함수계(iterated function system) 연구에 사용할 수 있다.

모든 증가수열 x_n에 대해 f(lim x_n) = lim f(x_n)이면, f의 최소 고정점은 lim f_n(0)이며, 이는 클레이니 고정점 정리의 구성적 버전을 제공한다.

이론 컴퓨터 과학에서 단조 함수의 최소 고정점은 프로그램 의미론을 정의하는 데 사용된다. 이 경우 특히 격자 L을 특정 집합의 모든 부분집합들을 모은 것, 즉 멱집합 격자로 가정하는 특수한 케이스에 대하여 집중하는 것이 일반적이다. 그리고 나서 f의 고정점이 되기 위해 필요한 조건을 가지는 최소의 집합을 찾아낸다.

5. 역

반대로, 모든 단조함수의 고정점이 존재하는 격자는 완비 격자이다.^[15] 즉, 타르스키 고정점 정리는 완비 격자의 정의로 삼을 수 있다. 그러나 모든 단조함수가 고정점이 존재하는 부분 순서 집합은 완비 격자일 필요가 없다.

==== 역의 증명 ====

완비 격자가 아닌 격자 위에는 항상 고정점이 없는 단조함수를 구성할 수 있음을 보인다.

격자 $L$ 이 완비 격자가 아닐 때, 고정점이 없는 단조함수 $f\colon L\to L$ 를 구성한다. 두 부분 집합 $A,B\subseteq L$ 에 대하여, 다음 조건들을 고려한다.

(라) $A$ 는 정렬 전순서 집합이다.
(마) $B$ 의 반대 순서 집합 $B^{\operatorname{op}}$ 는 정렬 전순서 집합이다.
(바) 임의의 $a\in A$ 및 $b\in B$ 에 대하여, $a 이다.$
(사) 동시에 $A$ 의 상계이자 $B$ 의 하계인 $L$ 의 원소가 존재하지 않는다.

만약

A

와

B

가 위 조건들을 만족시킨다면, 다음과 같이 정의된 함수는 단조함수이며 고정점이 존재하지 않는다.

:

f\colon L\to L

:

f\colon x\mapsto\begin{cases}\min\{a\in A\colon a\not\le x\}&\forall b\in B\colon x\le b\\\max\{b\in B\colon x\not\le b\}&\exist b\in B\colon x\not\le b\end{cases}

따라서, 조건 (라)~(사)를 만족시키는

A

와

B

를 찾으면 된다. 모든 부분 집합의 상한이 존재하는 부분 순서 집합은 완비 격자이므로, 상한이 없는

L

의 부분 집합

\{a''_\alpha\colon\alpha<\kappa\}

가 존재한다. 편의상 그 크기

\kappa

가 최소라고 가정한다.

L

이 격자이므로,

\kappa

은 0이거나 무한 기수이다.

임의의 순서수

\alpha<\kappa

에 대하여,

\{a''_\beta\colon\beta<\alpha\}

의 크기는

\kappa

미만이므로, 상한

:

a'_\alpha=\bigvee_{\beta<\alpha}a''_\beta

이 존재한다.

(a'_\alpha\colon\alpha<\kappa)

는 단조 초한 점렬이지만, 순단조가 아닐 수 있다. 중복된 항을 제거하여 순단조 초한 점렬

(a_\alpha\colon\alpha<\kappa)

로 만든다 (길이가

\kappa

인 것은

\kappa

의 최소성을 사용하여 보일 수 있다). 이 경우,

A=\{a_\alpha\colon\alpha<\kappa\}

는 정렬 전순서 집합이다. 만약

A

의 상한이 존재한다면, 이는

\{a''_\alpha\colon\alpha<\kappa\}

의 상한이 되어 모순이다. 따라서

A

의 상한이 존재하지 않는다.

A

의 상계들로 구성된 순감소 초한 점렬들의 집합 위에 다음과 같은 부분 순서를 정의한다.

:

(x_\alpha'\colon\alpha'<\alpha)\preceq(y_\beta'\colon\beta'<\beta)\iff\alpha\le\beta,\;x=y\restriction\alpha

즉, 끝에 항을 추가하면 더 큰 초한 점렬을 얻는다. 초른 보조정리에 따라, 이 부분 순서에 따른 극대 원소

(b_\alpha\colon\alpha<\lambda)

가 존재한다 (

\lambda

가 기수일 필요는 없다).

B=\{b_\alpha\colon\alpha<\lambda\}

의 반대 순서 집합

B^{\operatorname{op}}

은 정렬 전순서 집합이다.

만약

\textstyle\bigwedge B

가 존재한다면,

\textstyle\bigwedge B

역시

A

의 상계이다.

A

의 상한이 존재하지 않으므로,

\textstyle\bigwedge B\not\le b

인

A

의 상계

b\in L

가 존재한다. 이 경우,

\textstyle\bigwedge B\wedge b

는

A

의 상계이며,

\textstyle\bigwedge B\wedge b<\bigwedge B

이다. 이는

(b_\alpha\colon\alpha<\lambda)

의 극대성과 모순이다. 따라서,

B

의 하한 역시 존재하지 않는다.

이제,

A=\{a_\alpha\colon\alpha<\kappa\}

와

B=\{b_\alpha\colon\alpha<\lambda\}

에 대하여 조건 (사)를 증명하는 일만 남았다. 귀류법을 사용하여,

b\in L

이

A

의 상계이자

B

의 하계라고 가정한다. 그렇다면,

(b_\alpha\colon\alpha<\lambda)

의 극대성에 따라

b\in B

이다. 따라서

b

는

B

의 하한이며, 이는 모순이다.

5. 1. 역의 증명

완비 격자가 아닌 격자 위에는 항상 고정점이 없는 단조함수를 구성할 수 있음을 보인다.

격자

L

이 완비 격자가 아닐 때, 고정점이 없는 단조함수

f\colon L\to L

를 구성한다. 두 부분 집합

A,B\subseteq L

에 대하여, 다음 조건들을 고려한다.

(라) $A$ 는 정렬 전순서 집합이다.
(마) $B$ 의 반대 순서 집합 $B^{\operatorname{op}}$ 는 정렬 전순서 집합이다.
(바) 임의의 $a\in A$ 및 $b\in B$ 에 대하여, $a 이다.$
(사) 동시에 $A$ 의 상계이자 $B$ 의 하계인 $L$ 의 원소가 존재하지 않는다.

만약

A

와

B

가 위 조건들을 만족시킨다면, 다음과 같이 정의된 함수는 단조함수이며 고정점이 존재하지 않는다.

:

f\colon L\to L

:

f\colon x\mapsto\begin{cases}\min\{a\in A\colon a\not\le x\}&\forall b\in B\colon x\le b\\\max\{b\in B\colon x\not\le b\}&\exist b\in B\colon x\not\le b\end{cases}

따라서, 조건 (라)~(사)를 만족시키는

A

와

B

를 찾으면 된다. 모든 부분 집합의 상한이 존재하는 부분 순서 집합은 완비 격자이므로, 상한이 없는

L

의 부분 집합

\{a''_\alpha\colon\alpha<\kappa\}

가 존재한다. 편의상 그 크기

\kappa

가 최소라고 가정한다.

L

이 격자이므로,

\kappa

은 0이거나 무한 기수이다.

임의의 순서수

\alpha<\kappa

에 대하여,

\{a''_\beta\colon\beta<\alpha\}

의 크기는

\kappa

미만이므로, 상한

:

a'_\alpha=\bigvee_{\beta<\alpha}a''_\beta

이 존재한다.

(a'_\alpha\colon\alpha<\kappa)

는 단조 초한 점렬이지만, 순단조가 아닐 수 있다. 중복된 항을 제거하여 순단조 초한 점렬

(a_\alpha\colon\alpha<\kappa)

로 만든다 (길이가

\kappa

인 것은

\kappa

의 최소성을 사용하여 보일 수 있다). 이 경우,

A=\{a_\alpha\colon\alpha<\kappa\}

는 정렬 전순서 집합이다. 만약

A

의 상한이 존재한다면, 이는

\{a''_\alpha\colon\alpha<\kappa\}

의 상한이 되어 모순이다. 따라서

A

의 상한이 존재하지 않는다.

A

의 상계들로 구성된 순감소 초한 점렬들의 집합 위에 다음과 같은 부분 순서를 정의한다.

:

(x_\alpha'\colon\alpha'<\alpha)\preceq(y_\beta'\colon\beta'<\beta)\iff\alpha\le\beta,\;x=y\restriction\alpha

즉, 끝에 항을 추가하면 더 큰 초한 점렬을 얻는다. 초른 보조정리에 따라, 이 부분 순서에 따른 극대 원소

(b_\alpha\colon\alpha<\lambda)

가 존재한다 (

\lambda

가 기수일 필요는 없다).

B=\{b_\alpha\colon\alpha<\lambda\}

의 반대 순서 집합

B^{\operatorname{op}}

은 정렬 전순서 집합이다.

만약

\textstyle\bigwedge B

가 존재한다면,

\textstyle\bigwedge B

역시

A

의 상계이다.

A

의 상한이 존재하지 않으므로,

\textstyle\bigwedge B\not\le b

인

A

의 상계

b\in L

가 존재한다. 이 경우,

\textstyle\bigwedge B\wedge b

는

A

의 상계이며,

\textstyle\bigwedge B\wedge b<\bigwedge B

이다. 이는

(b_\alpha\colon\alpha<\lambda)

의 극대성과 모순이다. 따라서,

B

의 하한 역시 존재하지 않는다.

이제,

A=\{a_\alpha\colon\alpha<\kappa\}

와

B=\{b_\alpha\colon\alpha<\lambda\}

에 대하여 조건 (사)를 증명하는 일만 남았다. 귀류법을 사용하여,

b\in L

이

A

의 상계이자

B

의 하계라고 가정한다. 그렇다면,

(b_\alpha\colon\alpha<\lambda)

의 극대성에 따라

b\in B

이다. 따라서

b

는

B

의 하한이며, 이는 모순이다.

6. 일반화

격자 $L$ 의, 공집합이 아닌 두 부분 격자 $M$ , $N$ 에 대하여, 다음과 같은 이항 관계를 정의하자.

: $M\preceq N\iff\forall a\in M\forall b\in N\colon a\wedge b\in M,\;a\vee b\in N$

특히, 만약 $M\preceq N$ 이라면, 임의의 $a\in M$ 에 대하여, $a\le b$ 인 $b\in N$ 이 존재하며, 마찬가지로 임의의 $b\in N$ 에 대하여, $a\le b$ 인 $a\in M$ 이 존재한다. 즉, $M\subseteq\mathop\downarrow N$ 이며 $N\subseteq\mathop\uparrow M$ 이다. 이 이항 관계는 공집합이 아닌 부분 격자의 집합 위의 부분 순서를 이룬다. $L$ 의 원소는 자연스럽게 $L$ 의 부분 격자로 여길 수 있다. 이 경우, 부분 격자의 순서는 원소의 순서를 확장한다. 따라서, 아래의 정리는 타르스키 고정점 정리를 일반화한다.

다음이 주어졌다고 하자.

완비 격자 $L$
단조함수 $f\colon L\to(\operatorname{Sub}(L),{\preceq}|_{\operatorname{Sub}(L)})$ . 여기서 $(\operatorname{Sub}(L),{\preceq}|_{\operatorname{Sub}(L)})$ 은 $L$ 의 부분 완비 격자의, 위에서 정의한 순서에 따른 부분 순서 집합이다. (부분 완비 격자는 완비 격자인 부분 격자보다 더 강한 개념이다. 전자는 모든 상한과 하한이 원래 격자와 일치하지만, 후자는 모든 유한 집합의 상한·하한의 일치만을 요구한다.)

그렇다면,

f

의 고정점 집합

:

\operatorname{fix}(f)=\{a\in L\colon a\in f(a)\}

은 완비 격자를 이룬다.^[16] 또한,

f

의 최대·최소 고정점은 다음과 같다.

:

\bigvee\operatorname{fix}(f)=\bigvee\{a\in L\colon a\in\mathop\downarrow f(a)\}

:

\bigwedge\operatorname{fix}(f)=\bigwedge\{a\in L\colon a\in\mathop\uparrow f(a)\}

6. 1. 일반화의 증명

타르스키 고정점 정리의 증명과 유사하게, 다음 네 명제를 보인다. 이들 가운데 명제 (아)와 (자), 명제 (차)와 (카)는 서로 쌍대이므로 하나씩만 증명하여도 좋다.

(아) $M=\{a\in L\colon a\in\mathop\downarrow f(a)\}$ 에 대하여, $\textstyle\bigvee M$ 은 $f$ 의 최대 고정점이다.
(자) $N=\{a\in L\colon a\in\mathop\uparrow f(a)\}$ 에 대하여, $\textstyle\bigwedge N$ 은 $f$ 의 최소 고정점이다.
(차) 모든 $S\subseteq\operatorname{fix}(f)$ 의 $\operatorname{fix}(f)$ 에서의 상한이 존재한다.
(카) 모든 $S\subseteq\operatorname{fix}(f)$ 의 $\operatorname{fix}(f)$ 에서의 하한이 존재한다.

명제 (아)의 증명.

\operatorname{fix}(f)\subseteq M

이므로,

\textstyle\bigvee M\in\operatorname{fix}(f)

이면 충분하다. 임의의

a\in M

가 주어졌다고 하자.

M

의 정의에 따라,

x_a\in f(a)

이며

a\le x_a

라고 하자.

\textstyle a\le\bigvee M

이며

f

가 단조함수이므로,

\textstyle y_a\in f\left(\bigvee M\right)

이며

x_a\le y_a

라고 하자.

\textstyle f\left(\bigvee M\right)

이 부분 완비 격자이므로,

\textstyle\bigvee_{a\in M}y_a\in f\left(\bigvee M\right)

이다. 임의의

a\in M

에 대하여

a\le x_a\le y_a

이므로,

\textstyle\bigvee M\le\bigvee_{a\in M}y_a

이다.

f

의 단조성에 따라,

\textstyle\bigvee_{a\in M}y_a\le z

인

\textstyle z\in f\left(\bigvee_{a\in M}y_a\right)

가 존재한다. 즉,

\textstyle\bigvee_{a\in M}y_a\in M

이며, 따라서

\textstyle\bigvee_{a\in M}y_a\le\bigvee M

이다. 따라서,

\textstyle\bigvee M=\bigvee_{a\in M}y_a\in f\left(\bigvee M\right)

은

f

의 고정점이 맞다.

명제 (차)의 증명.

\textstyle\bigvee S

가

S

의

L

에서의 상한이라고 하자. 그렇다면,

\textstyle\left[\bigvee S,\top\right]

은 완비 격자를 이룬다. 임의의

s\in S

에 대하여,

s\in f(s)

이며

\textstyle s\le\bigvee S

이므로,

s\le x_s

인

\textstyle x_s\in f\left(\bigvee S\right)

가 존재한다. 이 경우,

\textstyle\bigvee_{s\in S}x_s\in f\left(\bigvee S\right)

이며

\textstyle\bigvee S\le\bigvee_{s\in S}x_s

이다. 따라서,

f

의 단조성에 의하여, 만약

\textstyle a\in\left[\bigvee S,\top\right]

라면,

\textstyle g(a)=f(a)\cap\left[\bigvee S,\top\right]

은 공집합이 아니다. 또한,

f(a)

는

L

의 부분 완비 격자이다. 따라서,

g(a)

는

\textstyle\left[\bigvee S,\top\right]

의 부분 완비 격자를 이룬다. 즉,

a\mapsto g(a)

는 단조함수

\textstyle g\colon\left[\bigvee S,\top\right]\to(\operatorname{Sub}(\left[\bigvee S,\top\right]),{\preceq}|_{\operatorname{Sub}(\left[\bigvee S,\top\right])})

를 정의한다. 명제 (자)에 따라,

g

의 최소 고정점이 존재하며, 이는

S

의

\operatorname{fix}(f)

에서의 상한이다.

7. 약한 버전의 정리

크나스터-타르스키 정리의 약한 버전은 순서 집합에 대해 공식화될 수 있지만, 더 복잡한 가정을 포함한다.

:'L'을 부분 순서 집합으로 최소 원소(바닥)를 가지고, 'f' : 'L' → 'L'을 단조 함수라고 하자. 또한 'L'에 'u'가 존재하여 'f'('u') ≤ 'u'이고, $\{x \in L \mid x \leq f(x), x \leq u\}$ 의 부분 집합에서 임의의 전순서 집합이 상한을 가진다고 가정하자. 그러면 'f'는 최소 고정점을 허용한다.

이는 다양한 불변 집합에 대한 정리를 얻는 데 적용될 수 있다. 예를들어, 단조 사상 F : P('X') → P('X') 가 (닫힌) X의 빈 집합이 아닌 부분 집합의 족에 대해, (o) F는 $A \subseteq F(A)$ 인 P''(''X'' )''에서 A를 허용하고, (i) F는 P''(''X'' )''에서 불변 집합 A를 허용한다. 즉, $A = F(A)$ , (ii) F는 최대 불변 집합 A를 허용하고, (iii) F는 최대 불변 집합 A를 허용하는 명제는 모두 동등하다.

특히 크나스터-타르스키 원리를 사용하여 비축약 불연속 (다중값) 반복 함수 시스템에 대한 전역 어트랙터 이론을 개발할 수 있다. 약한 축약 반복 함수 시스템의 경우 칸토로비치 정리 (타르스키-칸토로비치 고정점 원리로도 알려짐)가 충분하다.

순서 집합에 대한 고정점 원리의 다른 응용 분야는 미분 방정식, 적분 방정식 및 연산자 방정식 이론에서 나온다.

8. 타르스키 고정점 계산

창, 류, 티^[7]는 전순서 격자에서 순서를 보존하는 함수가 값 오라클로 주어질 때, 타르스키 고정점을 찾는 알고리즘을 제시했으며, 이 알고리즘은 O(log L)번의 질의가 필요하다(L은 격자의 원소 수). 일반적인 격자(오라클로 주어짐)의 경우에는 Ω(L)번의 질의라는 하한을 증명했다.

덩, 치, 예^[11]는 타르스키 고정점을 찾는 여러 알고리즘을 제시했다. 이들은 성분별 순서와 사전식 순서 두 종류의 격자를 고려하고, 함수 ''f''에 대한 값 오라클 또는 다항식 함수 두 종류의 입력을 고려했다. 이 알고리즘은 다음과 같은 런타임 복잡성을 가진다(''d''는 차원 수, ''N_i''는 차원 ''i''의 원소 수):

	다항식 함수	값 오라클
성분별	O(poly(log L) ⋅ log N₁ ... log N_d)	O(log N₁ ... log N_d) ≈ O(log^d L)
사전식	O(poly(log L) ⋅ log L)	O(log L)

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

	다항식 함수	값 오라클
성분별	coNP-완전	Θ(N₁+...+N_d)
사전식	coNP-완전	Θ(L)

''d''=2인 경우, 성분별 격자와 값 오라클에 대해 O(log² L)의 복잡성은 최적이다.^[8] 하지만 ''d''>2인 경우, 더 빠른 알고리즘이 존재한다.

펀리, 팔볼기, 사바니^[9]는 O(log^2⌈d/3⌉ L)번의 질의만 사용하는 알고리즘을 제시했다. 특히, ''d''=3인 경우, O(log² L)번의 질의만 필요하다.
첸과 리^[10]는 O(log^{⌈(d+1)/2⌉} L)번의 질의만 사용하는 알고리즘을 제시했다.

8. 1. 알고리즘 복잡도

창, 류, 티^[7]는 전순서 격자에서 순서를 보존하는 함수가 값 오라클로 주어질 때, 타르스키 고정점을 찾는 알고리즘을 제시했으며, 이 알고리즘은 O(log L)번의 질의가 필요하다(L은 격자의 원소 수). 일반적인 격자(오라클로 주어짐)의 경우에는 Ω(L)번의 질의라는 하한을 증명했다.

덩, 치, 예^[11]는 타르스키 고정점을 찾는 여러 알고리즘을 제시했다. 이들은 성분별 순서와 사전식 순서 두 종류의 격자를 고려하고, 함수 ''f''에 대한 값 오라클 또는 다항식 함수 두 종류의 입력을 고려했다. 이 알고리즘은 다음과 같은 런타임 복잡성을 가진다(''d''는 차원 수, ''N_i''는 차원 ''i''의 원소 수):

	다항식 함수	값 오라클
성분별	O(poly(log L) ⋅ log N₁ ... log N_d)	O(log N₁ ... log N_d) ≈ O(log^d L)
사전식	O(poly(log L) ⋅ log L)	O(log L)

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

	다항식 함수	값 오라클
성분별	coNP-완전	Θ(N₁+...+N_d)
사전식	coNP-완전	Θ(L)

''d''=2인 경우, 성분별 격자와 값 오라클에 대해 O(log² L)의 복잡성은 최적이다.^[8] 하지만 ''d''>2인 경우, 더 빠른 알고리즘이 존재한다.

펀리, 팔볼기, 사바니^[9]는 O(log^2⌈d/3⌉ L)번의 질의만 사용하는 알고리즘을 제시했다. 특히, ''d''=3인 경우, O(log² L)번의 질의만 필요하다.
첸과 리^[10]는 O(log^{⌈(d+1)/2⌉} L)번의 질의만 사용하는 알고리즘을 제시했다.

8. 2. 유일성 판정

창, 류, 티^[7]는 전순서 격자에서 타르스키 고정점을 찾는 알고리즘을 제시했으며, 이때 순서를 보존하는 함수는 값 오라클로 주어졌다. 그들의 알고리즘은

O(\log L)

번의 질의가 필요하며, 여기서 ''L''은 격자의 원소 수이다. 반면, 일반적인 격자(오라클로 주어짐)의 경우, 그들은

\Omega(L)

번의 질의라는 하한을 증명했다.

덩, 치, 예^[11]는 타르스키 고정점을 찾는 여러 알고리즘을 제시했다. 그들은 두 종류의 격자를 고려했다. 성분별 순서와 사전식 순서이다. 그들은 함수 ''f''에 대한 두 종류의 입력을 고려했다. 값 오라클 또는 다항식 함수이다.

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

''d''=2인 경우, 성분별 격자와 값 오라클에 대해

O(\log^2 L)

의 복잡성은 최적이다.^[8] 하지만 ''d''>2인 경우, 더 빠른 알고리즘이 있다.

펀리, 팔볼기, 사바니^[9]는 $O(\log^{2\lceil d/3 \rceil} L)$ 번의 질의만 사용하는 알고리즘을 제시했다. 특히, ''d''=3인 경우, $O(\log^2 L)$ 번의 질의만 필요하다.
첸과 리^[10]는 $O(\log^{\lceil (d+1)/2 \rceil} L)$ 번의 질의만 사용하는 알고리즘을 제시했다.

9. 게임 이론에서의 응용

타르스키 고정점 정리는 초가법 게임(전략적 보완 게임^[12]이라고도 함)에 적용된다.^[11] 초가법 게임은 각 플레이어의 효용 함수가 증가하는 차이를 갖는 게임으로, 플레이어의 최적 반응은 다른 플레이어의 전략에 대한 약하게 증가하는 함수이다. 예를 들어, 연구에 투자하는 두 회사의 경쟁과 같이, 한 회사가 연구에 더 많은 투자를 하면 다른 회사의 최적 반응도 연구에 더 많은 투자를 하는 경우가 이에 해당한다. 쿠르노 경쟁, 베르트랑 경쟁, 투자 게임 등이 초가법 게임으로 모델링될 수 있다.

최적 반응 함수는 단조 함수이므로 타르스키 고정점 정리를 사용하여 초가법 게임에서 순수 전략 내쉬 균형의 존재를 증명할 수 있다. Topkis^[13]는 초가법 게임의 내쉬 균형 집합이 완비 격자이므로 이 게임에는 "가장 작은" 내쉬 균형과 "가장 큰" 내쉬 균형이 있음을 보여주었다.

Echenique^[14]는 초가법 게임에서 모든 내쉬 균형을 찾는 알고리즘을 제시했다. Deng, Qi 및 Ye^[11]는 게임과 관련된 순서를 보존하는 매핑의 타르스키 고정점을 찾음으로써 내쉬 균형을 효율적으로 계산할 수 있음을 보여준다.

10. 역사

1927년 브로니스와프 크나스터(Bronisław Knaster^pl)와 알프레트 타르스키가 멱집합 격자 위 단조함수의 고정점의 존재를 증명하였다.^[17]^[18] 1939년에 타르스키가 오늘날 사용되는 형태의 정리를 완비 격자에 대한 내용으로 일반화했으며, 이는 1939년~1942년 동안 타르스키의 몇몇 공개 강의에서 소개되었다.^[18] 앤 모렐(周林/Anne C. Morel}})은 타르스키 고정점 정리의 역을 증명하였다.^[15] 저우린({{zh^영어)은 다중 값 함수에 대한 일반화를 제시하고 초모듈러 게임(supermodular game^영어)의 내시 균형 존재성을 보이는 데 사용했다.^[16]

참조

_[1] 논문 A lattice-theoretical fixpoint theorem and its applications https://www.projecte[...]
_[2] 논문 Un théorème sur les fonctions d'ensembles
_[3] 논문 A characterization of complete lattices https://www.projecte[...]
_[4] 논문 Constructive versions of tarski's fixed point theorems
_[5] MathWorld Tarski's Fixed Point Theorem
_[6] 서적 Introduction to Lattices and Order Cambridge University Press
_[7] 논문 The complexity of Tarski's fixed point theorem https://www.scienced[...] 2008-07-23
_[8] 논문 Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria https://drops.dagstu[...] Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik 2020
_[9] 논문 A Faster Algorithm for Finding Tarski Fixed Points https://doi.org/10.1[...] 2022-10-11
_[10] 서적 Proceedings of the 23rd ACM Conference on Economics and Computation Association for Computing Machinery 2022-07-13
_[11] 보고서 Computations and Complexities of Tarski's Fixed Points and Supermodular Games https://econpapers.r[...] arXiv.org 2020-05-01
_[12] 논문 Nash equilibrium with strategic complementarities https://dx.doi.org/1[...] 1990-01-01
_[13] 논문 Equilibrium Points in Nonzero-Sum n -Person Submodular Games http://epubs.siam.or[...] 1979-11-01
_[14] 논문 Finding all equilibria in games of strategic complements https://www.scienced[...] 2007-07-01
_[15] 논문 A characterization of complete lattices 1955
_[16] 논문 The set of Nash equilibria of a supermodular game is a complete lattice 1994
_[17] 논문 Un théorème sur les fonctions d’ensembles 1928
_[18] 논문 A lattice-theoretical fixpoint theorem and its applications 1955

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

문의하기 : help@durumis.com