순서론 에서 타르스키 고정점 정리 (영어 : Tarski’s fixed point theorem ) 또는 크나스터-타르스키 정리 (영어 : Knaster–Tarski theorem )는 완비 격자 에서 자신으로 가는 단조함수 의 고정점 이 존재한다는 정리이다.
이는 이론 컴퓨터 과학 의 형식 의미론 및 추상 해석 분야에서 중요한 정리이다.
완비 격자
L
{\displaystyle L}
과 단조함수
f
:
L
→
L
{\displaystyle f\colon L\to L}
가 주어졌다고 하자. 타르스키 고정점 정리 에 따르면,
f
{\displaystyle f}
의 고정점 의 집합
fix
(
f
)
=
{
a
∈
L
:
f
(
a
)
=
a
}
{\displaystyle \operatorname {fix} (f)=\{a\in L\colon f(a)=a\}}
역시 완비 격자 를 이룬다. (그러나,
fix
(
f
)
{\displaystyle \operatorname {fix} (f)}
가
L
{\displaystyle L}
의 부분 격자일 필요는 없다. 즉,
fix
(
f
)
{\displaystyle \operatorname {fix} (f)}
에서의 상한 과 하한 은
L
{\displaystyle L}
에서와 일치하지 않을 수 있다.) 특히,
f
{\displaystyle f}
의 최대 고정점 과 최소 고정점 이 존재하며, 특히
f
{\displaystyle f}
는 적어도 하나의 고정점을 갖는다. 또한,
f
{\displaystyle f}
의 최대·최소 고정점은 각각 다음과 같이 주어진다.
⋁
fix
(
f
)
=
⋁
{
a
∈
L
:
a
≤
f
(
a
)
}
{\displaystyle \bigvee \operatorname {fix} (f)=\bigvee \{a\in L\colon a\leq f(a)\}}
⋀
fix
(
f
)
=
⋀
{
a
∈
L
:
a
≥
f
(
a
)
}
{\displaystyle \bigwedge \operatorname {fix} (f)=\bigwedge \{a\in L\colon a\geq f(a)\}}
증명
타르스키를 따라, 다음 순서대로 증명한다.
(가)
⋁
{
a
∈
L
:
a
≤
f
(
a
)
}
{\displaystyle \textstyle \bigvee \{a\in L\colon a\leq f(a)\}}
는
f
{\displaystyle f}
의 최대 고정점 이다.
(나)
⋀
{
a
∈
L
:
a
≥
f
(
a
)
}
{\displaystyle \textstyle \bigwedge \{a\in L\colon a\geq f(a)\}}
는
f
{\displaystyle f}
의 최소 고정점 이다.
(다)
fix
(
f
)
{\displaystyle \operatorname {fix} (f)}
는 완비 격자 이다.
명제 (가)의 증명.
M
=
{
a
∈
L
:
a
≤
f
(
a
)
}
{\displaystyle M=\{a\in L\colon a\leq f(a)\}}
라고 하자. 임의의
a
∈
M
{\displaystyle a\in M}
에 대하여,
a
≤
⋁
M
{\displaystyle \textstyle a\leq \bigvee M}
이므로,
a
≤
f
(
a
)
≤
f
(
⋁
M
)
{\displaystyle \textstyle a\leq f(a)\leq f\left(\bigvee M\right)}
이다. 따라서
⋁
M
≤
f
(
⋁
M
)
{\displaystyle \textstyle \bigvee M\leq f\left(\bigvee M\right)}
이다. 반대로,
f
(
⋁
M
)
≤
f
(
f
(
⋁
M
)
)
{\displaystyle \textstyle f\left(\bigvee M\right)\leq f\left(f\left(\bigvee M\right)\right)}
이므로,
M
{\displaystyle M}
의 정의에 따라
f
(
⋁
M
)
∈
M
{\displaystyle \textstyle f\left(\bigvee M\right)\in M}
이다. 따라서
f
(
⋁
M
)
≤
⋁
M
{\displaystyle \textstyle f\left(\bigvee M\right)\leq \bigvee M}
이다. 따라서,
⋁
M
{\displaystyle \textstyle \bigvee M}
은
f
{\displaystyle f}
의 고정점 이다. 모든 고정점은
M
{\displaystyle M}
에 속하므로,
⋁
M
{\displaystyle \textstyle \bigvee M}
은
f
{\displaystyle f}
의 최대 고정점 이다.
명제 (나)의 증명.
L
{\displaystyle L}
의 반대 격자
L
op
{\displaystyle L^{\operatorname {op} }}
를 생각하자.
L
op
{\displaystyle L^{\operatorname {op} }}
역시 완비 격자 를 이루며,
f
{\displaystyle f}
는
L
op
{\displaystyle L^{\operatorname {op} }}
위에서도 단조함수 이다. 따라서
L
op
{\displaystyle L^{\operatorname {op} }}
에 대하여 명제 (가)가 성립한다. 이는 정확히
L
{\displaystyle L}
에 대한 명제 (나)와 일치한다.
명제 (다)의 증명.
S
{\displaystyle S}
가
fix
(
f
)
{\displaystyle \operatorname {fix} (f)}
의 임의의 부분 집합이라고 하자.
fix
(
f
)
{\displaystyle \operatorname {fix} (f)}
에서
S
{\displaystyle S}
의 상한 이 존재함을 보이면 충분하다.
S
{\displaystyle S}
의
L
{\displaystyle L}
에서의 상한
⋁
S
{\displaystyle \textstyle \bigvee S}
를 생각하자. 그렇다면 구간
[
⋁
S
,
⊤
]
=
{
a
∈
L
:
a
≥
⋁
S
}
{\displaystyle \textstyle \left[\bigvee S,\top \right]=\left\{a\in L\colon a\geq \bigvee S\right\}}
는
S
{\displaystyle S}
의 상계 의 집합이며, 완비 격자 를 이룬다 (이는 부분 격자이기도 하지만, 부분 완비 격자가 아닐 수 있다). 임의의
s
∈
S
{\displaystyle s\in S}
에 대하여
s
=
f
(
s
)
≤
f
(
⋁
S
)
{\displaystyle \textstyle s=f(s)\leq f\left(\bigvee S\right)}
이므로,
⋁
S
≤
f
(
⋁
S
)
{\displaystyle \textstyle \bigvee S\leq f\left(\bigvee S\right)}
이다.
a
∈
L
{\displaystyle a\in L}
에 대하여, 만약
a
≥
⋁
S
{\displaystyle \textstyle a\geq \bigvee S}
라면,
f
(
a
)
≥
f
(
⋁
S
)
≥
⋁
S
{\displaystyle \textstyle f(a)\geq f\left(\bigvee S\right)\geq \bigvee S}
이다. 따라서,
f
{\displaystyle f}
를
[
⋁
S
,
⊤
]
{\displaystyle \textstyle \left[\bigvee S,\top \right]}
위의 함수
f
′
:
[
⋁
S
,
⊤
]
→
[
⋁
S
,
⊤
]
{\displaystyle \textstyle f'\colon \left[\bigvee S,\top \right]\to \left[\bigvee S,\top \right]}
로 여길 수 있다. 명제 (나)에 따라,
f
′
{\displaystyle f'}
의 최소 고정점 이 존재한다. 이는
f
{\displaystyle f}
의 고정점이며,
S
{\displaystyle S}
의 상계가 되는 가장 작은
f
{\displaystyle f}
의 고정점이다. 다시 말해,
S
{\displaystyle S}
의
fix
(
f
)
{\displaystyle \operatorname {fix} (f)}
에서의 상한 이다.
고정점 집합이 부분 격자가 아닌 경우
고정점 집합은 완비 격자이지만, 부분 격자가 아닐 수 있다. 예를 들어, 다음과 같은 부분 순서 집합 을 생각하자.
L
=
{
⊥
,
a
,
a
′
,
b
,
⊤
}
{\displaystyle L=\{\bot ,a,a',b,\top \}}
⊥
<
a
,
a
′
<
b
<
⊤
{\displaystyle \bot <a,a'<b<\top }
그렇다면,
L
{\displaystyle L}
은 완비 격자 를 이룬다. 이제
f
:
L
→
L
{\displaystyle f\colon L\to L}
이며
f
(
x
)
=
x
(
x
=
⊥
,
a
,
a
′
,
⊤
)
{\displaystyle f(x)=x\qquad (x=\bot ,a,a',\top )}
f
(
b
)
=
⊤
{\displaystyle f(b)=\top }
라고 하자.
f
{\displaystyle f}
는
L
{\displaystyle L}
위의 단조함수 이며,
a
{\displaystyle a}
와
a
′
{\displaystyle a'}
은
f
{\displaystyle f}
의 고정점 이지만,
a
∨
a
′
=
b
{\displaystyle a\vee a'=b}
는
f
{\displaystyle f}
의 고정점 이 아니다. (
a
{\displaystyle a}
와
a
′
{\displaystyle a'}
의
fix
(
f
)
{\displaystyle \operatorname {fix} (f)}
에서의 상한 은
b
{\displaystyle b}
가 아닌
⊤
{\displaystyle \top }
이다.) 따라서,
fix
(
f
)
{\displaystyle \operatorname {fix} (f)}
는
L
{\displaystyle L}
의 부분 격자가 아니다.
완비 격자 는 공집합일 수 없으므로, 이 정리는 상기한
f
{\displaystyle f}
에 적어도 한개의 고정점이 있음을, 나아가서 최소 고정점이 있음을 보장한다.
조건을 추가하여 임의의 부분 순서 집합 에 대하여 유사한 결과를 증명할 수 있다. 이를 동역학계 이론에 적용하여 프랙탈 의 일종인 반복함수계 (iterated function system) 연구에 사용할 수 있다.
모든 증가수열
x
n
{\displaystyle x_{n}}
에 대해
f
(
lim
x
n
)
=
lim
f
(
x
n
)
{\displaystyle f(\lim x_{n})=\lim f(x_{n})}
이면,
f
{\displaystyle f}
의 최소 고정점은
lim
f
n
(
0
)
{\displaystyle \lim f_{n}(0)}
이며, 이는 정리의 구성적 버전(Kleene fixed-point theorem)을 제공한다.
이론 컴퓨터 과학에서, 단조함수에 대한 최소 고정점 정리는 프로그램 의미론을 정의하는 데 사용된다. 이 경우 특히 격자 L을 특정 집합의 모든 부분집합들을 모은 것, 즉 멱집합 격자로 가정하는 특수한 케이스에 대하여 집중하는 것이 일반적이다. 그리고 나서 f의 고정점이 되기 위해 필요한 조건을 가지는 최소의 집합을 찾아낸다.
반대로, 모든 단조함수 의 고정점 이 존재하는 격자 는 완비 격자 이다.[1] :313, Theorem 2 즉, 타르스키 고정점 정리는 완비 격자 의 정의로 삼을 수 있다. 그러나 모든 단조함수 가 고정점 이 존재하는 부분 순서 집합 은 완비 격자 일 필요가 없다.
역의 증명
격자
L
{\displaystyle L}
이 완비 격자 위에 항상 고정점 이 없는 단조함수
f
:
L
→
L
{\displaystyle f\colon L\to L}
를 구성하면 족하다. 두 부분 집합
A
,
B
⊆
L
{\displaystyle A,B\subseteq L}
에 대하여, 다음 조건들을 생각하자.
(라)
A
{\displaystyle A}
는 정렬 전순서 집합 이다.
(마)
B
{\displaystyle B}
의 반대 순서 집합
B
op
{\displaystyle B^{\operatorname {op} }}
는 정렬 전순서 집합 이다.
(바) 임의의
a
∈
A
{\displaystyle a\in A}
및
b
∈
B
{\displaystyle b\in B}
에 대하여,
a
<
b
{\displaystyle a<b}
(사) 동시에
A
{\displaystyle A}
의 상계 이자
B
{\displaystyle B}
의 하계 인
L
{\displaystyle L}
의 원소가 존재하지 않는다.
만약
A
{\displaystyle A}
와
B
{\displaystyle B}
가 위 조건들을 만족시킨다면, 함수
f
:
L
→
L
{\displaystyle f\colon L\to L}
f
:
x
↦
{
min
{
a
∈
A
:
a
≰
x
}
∀
b
∈
B
:
x
≤
b
max
{
b
∈
B
:
x
≰
b
}
∃
b
∈
B
:
x
≰
b
{\displaystyle f\colon x\mapsto {\begin{cases}\min\{a\in A\colon a\not \leq x\}&\forall b\in B\colon x\leq b\\\max\{b\in B\colon x\not \leq b\}&\exists b\in B\colon x\not \leq b\end{cases}}}
는 단조함수 이며, 고정점 이 존재하지 않는다. 따라서, 조건 (라)~(사)를 만족시키는
A
{\displaystyle A}
와
B
{\displaystyle B}
를 찾는 것으로 족하다. 모든 부분 집합의 상한 이 존재하는 부분 순서 집합 은 완비 격자 이므로, 상한 이 없는
L
{\displaystyle L}
의 부분 집합
{
a
α
″
:
α
<
κ
}
{\displaystyle \{a''_{\alpha }\colon \alpha <\kappa \}}
가 존재한다. 편의상 그 크기
κ
{\displaystyle \kappa }
가 최소라고 하자.
L
{\displaystyle L}
이 격자 이므로,
κ
{\displaystyle \kappa }
은 0이거나 무한 기수 이다. 이제, 임의의 순서수
α
<
κ
{\displaystyle \alpha <\kappa }
에 대하여,
{
a
β
″
:
β
<
α
}
{\displaystyle \{a''_{\beta }\colon \beta <\alpha \}}
의 크기는
κ
{\displaystyle \kappa }
미만이므로, 상한
a
α
′
=
⋁
β
<
α
a
β
″
{\displaystyle a'_{\alpha }=\bigvee _{\beta <\alpha }a''_{\beta }}
이 존재한다.
(
a
α
′
:
α
<
κ
)
{\displaystyle (a'_{\alpha }\colon \alpha <\kappa )}
는 단조 초한 점렬이지만, 순단조 가 아닐 수 있다. 중복된 항을 제거하여 순단조 초한 점렬
(
a
α
:
α
<
κ
)
{\displaystyle (a_{\alpha }\colon \alpha <\kappa )}
로 만들자 (길이가
κ
{\displaystyle \kappa }
인 것은
κ
{\displaystyle \kappa }
의 최소성을 사용하여 보일 수 있다). 이 경우,
A
=
{
a
α
:
α
<
κ
}
{\displaystyle A=\{a_{\alpha }\colon \alpha <\kappa \}}
는 정렬 전순서 집합 이다. 만약
A
{\displaystyle A}
의 상한 이 존재한다면, 이는
{
a
α
″
:
α
<
κ
}
{\displaystyle \{a''_{\alpha }\colon \alpha <\kappa \}}
의 상한 이 되어 모순이 일어난다. 따라서
A
{\displaystyle A}
의 상한 이 존재하지 않는다.
A
{\displaystyle A}
의 상계 들로 구성된 순감소 초한 점렬들의 집합 위에 다음과 같은 부분 순서 를 주자.
(
x
α
′
:
α
′
<
α
)
⪯
(
y
β
′
:
β
′
<
β
)
⟺
α
≤
β
,
x
=
y
↾
α
{\displaystyle (x_{\alpha }'\colon \alpha '<\alpha )\preceq (y_{\beta }'\colon \beta '<\beta )\iff \alpha \leq \beta ,\;x=y\upharpoonright \alpha }
즉, 끝에 항을 추가하면 더 큰 초한 점렬을 얻는다. 초른 보조정리 에 따라, 이 부분 순서에 따른 극대 원소
(
b
α
:
α
<
λ
)
{\displaystyle (b_{\alpha }\colon \alpha <\lambda )}
가 존재한다 (
λ
{\displaystyle \lambda }
가 기수 일 필요는 없다).
B
=
{
b
α
:
α
<
λ
}
{\displaystyle B=\{b_{\alpha }\colon \alpha <\lambda \}}
의 반대 순서 집합
B
op
{\displaystyle B^{\operatorname {op} }}
은 정렬 전순서 집합 이다. 만약
⋀
B
{\displaystyle \textstyle \bigwedge B}
가 존재한다면,
⋀
B
{\displaystyle \textstyle \bigwedge B}
역시
A
{\displaystyle A}
의 상계 이다.
A
{\displaystyle A}
의 상한이 존재하지 않으므로,
⋀
B
≰
b
{\displaystyle \textstyle \bigwedge B\not \leq b}
인
A
{\displaystyle A}
의 상계
b
∈
L
{\displaystyle b\in L}
가 존재한다. 이 경우,
⋀
B
∧
b
{\displaystyle \textstyle \bigwedge B\wedge b}
는
A
{\displaystyle A}
의 상계이며,
⋀
B
∧
b
<
⋀
B
{\displaystyle \textstyle \bigwedge B\wedge b<\bigwedge B}
이다. 이는
(
b
α
:
α
<
λ
)
{\displaystyle (b_{\alpha }\colon \alpha <\lambda )}
의 극대성과 모순이다. 따라서,
B
{\displaystyle B}
의 하한 역시 존재하지 않는다. 이제,
A
=
{
a
α
:
α
<
κ
}
{\displaystyle A=\{a_{\alpha }\colon \alpha <\kappa \}}
와
B
=
{
b
α
:
α
<
λ
}
{\displaystyle B=\{b_{\alpha }\colon \alpha <\lambda \}}
에 대하여 조건 (사)를 증명하는 일만 남았다. 귀류법 을 사용하여,
b
∈
L
{\displaystyle b\in L}
이
A
{\displaystyle A}
의 상계 이자
B
{\displaystyle B}
의 하계 라고 하자. 그렇다면,
(
b
α
:
α
<
λ
)
{\displaystyle (b_{\alpha }\colon \alpha <\lambda )}
의 극대성에 따라
b
∈
B
{\displaystyle b\in B}
이다. 따라서
b
{\displaystyle b}
는
B
{\displaystyle B}
의 하한 이며, 이는 모순이다.
격자
L
{\displaystyle L}
의, 공집합 이 아닌 두 부분 격자
M
{\displaystyle M}
,
N
{\displaystyle N}
에 대하여, 다음과 같은 이항 관계 를 정의하자.
M
⪯
N
⟺
∀
a
∈
M
∀
b
∈
N
:
a
∧
b
∈
M
,
a
∨
b
∈
N
{\displaystyle M\preceq N\iff \forall a\in M\forall b\in N\colon a\wedge b\in M,\;a\vee b\in N}
특히, 만약
M
⪯
N
{\displaystyle M\preceq N}
이라면, 임의의
a
∈
M
{\displaystyle a\in M}
에 대하여,
a
≤
b
{\displaystyle a\leq b}
인
b
∈
N
{\displaystyle b\in N}
이 존재하며, 마찬가지로 임의의
b
∈
N
{\displaystyle b\in N}
에 대하여,
a
≤
b
{\displaystyle a\leq b}
인
a
∈
M
{\displaystyle a\in M}
이 존재한다. 즉,
M
⊆
↓
N
{\displaystyle M\subseteq \mathop {\downarrow } N}
이며
N
⊆
↑
M
{\displaystyle N\subseteq \mathop {\uparrow } M}
이다. 이 이항 관계 는 공집합 이 아닌 부분 격자의 집합 위의 부분 순서 를 이룬다.
L
{\displaystyle L}
의 원소는 자연스럽게
L
{\displaystyle L}
의 부분 격자로 여길 수 있다. 이 경우, 부분 격자의 순서는 원소의 순서를 확장한다. 따라서, 아래의 정리는 타르스키 고정점 정리를 일반화한다.
다음이 주어졌다고 하자.
완비 격자
L
{\displaystyle L}
단조함수
f
:
L
→
(
Sub
(
L
)
,
⪯
|
Sub
(
L
)
)
{\displaystyle f\colon L\to (\operatorname {Sub} (L),{\preceq }|_{\operatorname {Sub} (L)})}
. 여기서
(
Sub
(
L
)
,
⪯
|
Sub
(
L
)
)
{\displaystyle (\operatorname {Sub} (L),{\preceq }|_{\operatorname {Sub} (L)})}
은
L
{\displaystyle L}
의 부분 완비 격자의, 위에서 정의한 순서에 따른 부분 순서 집합 이다. (부분 완비 격자는 완비 격자인 부분 격자보다 더 강한 개념이다. 전자는 모든 상한과 하한이 원래 격자와 일치하지만, 후자는 모든 유한 집합의 상한·하한의 일치만을 요구한다.)
그렇다면,
f
{\displaystyle f}
의 고정점 집합
fix
(
f
)
=
{
a
∈
L
:
a
∈
f
(
a
)
}
{\displaystyle \operatorname {fix} (f)=\{a\in L\colon a\in f(a)\}}
은 완비 격자 를 이룬다.[2] :297, Theorem 1 또한,
f
{\displaystyle f}
의 최대 ·최소 고정점 은 다음과 같다.
⋁
fix
(
f
)
=
⋁
{
a
∈
L
:
a
∈
↓
f
(
a
)
}
{\displaystyle \bigvee \operatorname {fix} (f)=\bigvee \{a\in L\colon a\in \mathop {\downarrow } f(a)\}}
⋀
fix
(
f
)
=
⋀
{
a
∈
L
:
a
∈
↑
f
(
a
)
}
{\displaystyle \bigwedge \operatorname {fix} (f)=\bigwedge \{a\in L\colon a\in \mathop {\uparrow } f(a)\}}
일반화의 증명
타르스키 고정점 정리의 증명과 유사하게, 다음 네 명제를 보인다. 이들 가운데 명제 (아)와 (자), 명제 (차)와 (카)는 서로 쌍대이므로 하나씩만 증명하여도 좋다.
(아)
M
=
{
a
∈
L
:
a
∈
↓
f
(
a
)
}
{\displaystyle M=\{a\in L\colon a\in \mathop {\downarrow } f(a)\}}
에 대하여,
⋁
M
{\displaystyle \textstyle \bigvee M}
은
f
{\displaystyle f}
의 최대 고정점 이다.
(자)
N
=
{
a
∈
L
:
a
∈
↑
f
(
a
)
}
{\displaystyle N=\{a\in L\colon a\in \mathop {\uparrow } f(a)\}}
에 대하여,
⋀
N
{\displaystyle \textstyle \bigwedge N}
은
f
{\displaystyle f}
의 최소 고정점 이다.
(차) 모든
S
⊆
fix
(
f
)
{\displaystyle S\subseteq \operatorname {fix} (f)}
의
fix
(
f
)
{\displaystyle \operatorname {fix} (f)}
에서의 상한 이 존재한다.
(카) 모든
S
⊆
fix
(
f
)
{\displaystyle S\subseteq \operatorname {fix} (f)}
의
fix
(
f
)
{\displaystyle \operatorname {fix} (f)}
에서의 하한 이 존재한다.
명제 (아)의 증명.
fix
(
f
)
⊆
M
{\displaystyle \operatorname {fix} (f)\subseteq M}
이므로,
⋁
M
∈
fix
(
f
)
{\displaystyle \textstyle \bigvee M\in \operatorname {fix} (f)}
이면 충분하다. 임의의
a
∈
M
{\displaystyle a\in M}
가 주어졌다고 하자.
M
{\displaystyle M}
의 정의에 따라,
x
a
∈
f
(
a
)
{\displaystyle x_{a}\in f(a)}
이며
a
≤
x
a
{\displaystyle a\leq x_{a}}
라고 하자.
a
≤
⋁
M
{\displaystyle \textstyle a\leq \bigvee M}
이며
f
{\displaystyle f}
가 단조함수 이므로,
y
a
∈
f
(
⋁
M
)
{\displaystyle \textstyle y_{a}\in f\left(\bigvee M\right)}
이며
x
a
≤
y
a
{\displaystyle x_{a}\leq y_{a}}
라고 하자.
f
(
⋁
M
)
{\displaystyle \textstyle f\left(\bigvee M\right)}
이 부분 완비 격자이므로,
⋁
a
∈
M
y
a
∈
f
(
⋁
M
)
{\displaystyle \textstyle \bigvee _{a\in M}y_{a}\in f\left(\bigvee M\right)}
이다. 임의의
a
∈
M
{\displaystyle a\in M}
에 대하여
a
≤
x
a
≤
y
a
{\displaystyle a\leq x_{a}\leq y_{a}}
이므로,
⋁
M
≤
⋁
a
∈
M
y
a
{\displaystyle \textstyle \bigvee M\leq \bigvee _{a\in M}y_{a}}
이다.
f
{\displaystyle f}
의 단조성에 따라,
⋁
a
∈
M
y
a
≤
z
{\displaystyle \textstyle \bigvee _{a\in M}y_{a}\leq z}
인
z
∈
f
(
⋁
a
∈
M
y
a
)
{\displaystyle \textstyle z\in f\left(\bigvee _{a\in M}y_{a}\right)}
가 존재한다. 즉,
⋁
a
∈
M
y
a
∈
M
{\displaystyle \textstyle \bigvee _{a\in M}y_{a}\in M}
이며, 따라서
⋁
a
∈
M
y
a
≤
⋁
M
{\displaystyle \textstyle \bigvee _{a\in M}y_{a}\leq \bigvee M}
이다. 따라서,
⋁
M
=
⋁
a
∈
M
y
a
∈
f
(
⋁
M
)
{\displaystyle \textstyle \bigvee M=\bigvee _{a\in M}y_{a}\in f\left(\bigvee M\right)}
은
f
{\displaystyle f}
의 고정점 이 맞다.
명제 (차)의 증명.
⋁
S
{\displaystyle \textstyle \bigvee S}
가
S
{\displaystyle S}
의
L
{\displaystyle L}
에서의 상한 이라고 하자. 그렇다면,
[
⋁
S
,
⊤
]
{\displaystyle \textstyle \left[\bigvee S,\top \right]}
은 완비 격자 를 이룬다. 임의의
s
∈
S
{\displaystyle s\in S}
에 대하여,
s
∈
f
(
s
)
{\displaystyle s\in f(s)}
이며
s
≤
⋁
S
{\displaystyle \textstyle s\leq \bigvee S}
이므로,
s
≤
x
s
{\displaystyle s\leq x_{s}}
인
x
s
∈
f
(
⋁
S
)
{\displaystyle \textstyle x_{s}\in f\left(\bigvee S\right)}
가 존재한다. 이 경우,
⋁
s
∈
S
x
s
∈
f
(
⋁
S
)
{\displaystyle \textstyle \bigvee _{s\in S}x_{s}\in f\left(\bigvee S\right)}
이며
⋁
S
≤
⋁
s
∈
S
x
s
{\displaystyle \textstyle \bigvee S\leq \bigvee _{s\in S}x_{s}}
이다. 따라서,
f
{\displaystyle f}
의 단조성에 의하여, 만약
a
∈
[
⋁
S
,
⊤
]
{\displaystyle \textstyle a\in \left[\bigvee S,\top \right]}
라면,
g
(
a
)
=
f
(
a
)
∩
[
⋁
S
,
⊤
]
{\displaystyle \textstyle g(a)=f(a)\cap \left[\bigvee S,\top \right]}
은 공집합 이 아니다. 또한,
f
(
a
)
{\displaystyle f(a)}
는
L
{\displaystyle L}
의 부분 완비 격자이다. 따라서,
g
(
a
)
{\displaystyle g(a)}
는
[
⋁
S
,
⊤
]
{\displaystyle \textstyle \left[\bigvee S,\top \right]}
의 부분 완비 격자를 이룬다. 즉,
a
↦
g
(
a
)
{\displaystyle a\mapsto g(a)}
는 단조함수
g
:
[
⋁
S
,
⊤
]
→
(
Sub
(
[
⋁
S
,
⊤
]
)
,
⪯
|
Sub
(
[
⋁
S
,
⊤
]
)
)
{\displaystyle \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
{\displaystyle g}
의 최소 고정점 이 존재하며, 이는
S
{\displaystyle S}
의
fix
(
f
)
{\displaystyle \operatorname {fix} (f)}
에서의 상한 이다.
브로니스와프 크나스터 (1893~1980)
알프레트 타르스키 (1901~1983)
1927년 브로니스와프 크나스터 (폴란드어 : Bronisław Knaster )와 알프레트 타르스키 가 멱집합 격자 위 단조함수 의 고정점 의 존재를 증명하였다.[3] [4] :286, 각주 2 타르스키 고정점 정리의 오늘날 형태는 1939년 타르스키가 도입하였으며, 1939년~1942년 동안 타르스키의 몇몇 공개 강의에서 소개되었다.[4] :286, 각주 2 타르스키 고정점 정리의 역은 앤 모렐(영어 : Anne C. Morel )이 증명하였다.[1] 타르스키 고정점 정리의 다중 값 일반화는 저우린(중국어 : 周林 )이 초모듈러 게임(영어 : supermodular game )의 내시 균형 의 존재를 보이기 위하여 증명 및 사용하였다.[2]
Knaster, Bronisław (1928). “ Un théorème sur les fonctions d’ensembles” . 《 Annales de la Société Polonaise de Mathématique》 (프랑스어) 6 : 133–134. ISSN 0066-2216 . JFM 54.0091.04 . S. Hayashi (1985). “ Self-similar sets as Tarski's fixed points” . 《 Publ. RIMS Kyoto Univ.》 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 .