크나스터-타르스키 정리

순서론에서, 크나스터-타르스키 정리(Knaster-Tarski theorem) 또는 타르스키 고정점 정리(Tarski's fixed point theorem)는 완비 격자에서 자신으로 가는 순서보존함수를 잡으면 그 함수의 고정점의 집합도 완비 격자가 된다는 정리이다.

1928년 브로니스와프 크나스터(Bronisław Knaster)가 멱집합 격자에 대하여 증명하였고[1], 1955년 알프레트 타르스키가 일반화시켰다.[2]

이는 이론 컴퓨터 과학형식 의미론추상 해석 분야에서 중요한 정리이다.

정리편집

완비 격자  단조함수  를 가정한다. 그렇다면  의 고정점을 모두 모은 집합도 완비 격자  를 이루며, 최대 고정점  과 최소 고정점  를 가진다.

 의 최소 고정점은  가 되는 최소의 원소  를 의미하는데,  라 두어도 동치이다.

증명편집

우선  에 최대 원소와 최소 원소가 있음을 보인다. 고정점의 집합  를 잡고  라 둔다. (적어도  의 최소원소인   에 속함을 알고 있다.) 그러면  가 단조이므로  이고, 따라서  이다.

이제  라 한다. ( 이므로 그러한  는 존재한다.) 그러면 모든  에 대해   가 성립하고, 따라서  이다. 따라서   의 상계인데  는 최소 상계이므로  이며, 즉  이다. 그러면  이므로  이고, 여기서  임이 따라나온다. 모든 고정점이   안에 있으므로   의 최대 고정점임을 얻는다.

함수  는 쌍대의 격자   위에서도 단조인데, 위에서 증명했듯 그 최대 고정점이 존재한다. 이는  에서는 최소이므로  는 최소 및 최대 원소를 가지며 일반화해서 말하면 완비 격자 위의 모든 단조함수는 최소 고정점과 최대 고정점을 가진다.

이제 마지막으로  가 완비 격자임을 증명한다.  ,   일때   라 쓰며, 여기서  이면  는 완비 격자이다.  이라 하고  ,  라 두자. 이제  임을 보일 것이다. 모든  에 대해  인데,   의 최소 상계이기 때문이다. 그러면  로부터  임이 따라나오므로,   이다. 이는  를 완비 격자   위의 함수로서 볼 수 있게 해준다. 그렇다면 그 최소 고정점이 존재하며,  의 최소 상계가 따라나온다. 이로써  의 임의의 부분집합이 상한을 가지므로  가 완비 격자임이 증명되었다.

귀결편집

완비 격자는 공집합일 수 없으므로, 이 정리는 상기한  에 적어도 한개의 고정점이 있음을, 나아가서 최소 고정점이 있음을 보장한다.

조건을 추가하여 임의의 부분 순서 집합에 대하여 유사한 결과를 증명할 수 있다. 이를 동역학계 이론에 적용하여 프랙탈의 일종인 반복함수계(iterated function system) 연구에 사용할 수 있다.

모든 증가수열  에 대해  이면,  의 최소 고정점은  이며, 이는 정리의 구성적 버전(Kleene fixed-point theorem)을 제공한다.

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

같이 보기편집

각주편집

  1. B. Knaster (1928). “Un théorème sur les fonctions d'ensembles”. 《Ann. Soc. Polon. Math.》 6: 133–134.  With A. Tarski.
  2. Alfred Tarski (1955). “A lattice-theoretical fixpoint theorem and its applications”. 《Pacific Journal of Mathematics》 5:2: 285–309. 

참고 문헌편집

  • 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.