타르스키 고정점 정리

순서론에서 타르스키 고정점 정리() 또는 크나스터-타르스키 정리()는 완비 격자에서 자신으로 가는 단조함수의 고정점이 존재한다는 정리이다.
이는 이론 컴퓨터 과학의 형식 의미론 및 추상 해석 분야에서 중요한 정리이다.
정의.
완비 격자 formula_1과 단조함수 formula_2가 주어졌다고 하자. 타르스키 고정점 정리에 따르면, formula_3의 고정점의 집합
역시 완비 격자를 이룬다. (그러나, formula_5가 formula_1의 부분 격자일 필요는 없다. 즉, formula_5에서의 상한과 하한은 formula_1에서와 일치하지 않을 수 있다.) 특히, formula_3의 최대 고정점과 최소 고정점이 존재하며, 특히 formula_3는 적어도 하나의 고정점을 갖는다. 또한, formula_3의 최대·최소 고정점은 각각 다음과 같이 주어진다.
증명.
타르스키를 따라, 다음 순서대로 증명한다.
명제 (가)의 증명. formula_19라고 하자. 임의의 formula_20에 대하여, formula_21이므로, formula_22이다. 따라서 formula_23이다. 반대로, formula_24이므로, formula_25의 정의에 따라 formula_26이다. 따라서 formula_27이다. 따라서, formula_28은 formula_3의 고정점이다. 모든 고정점은 formula_25에 속하므로, formula_28은 formula_3의 최대 고정점이다.
명제 (나)의 증명. formula_1의 반대 격자 formula_34를 생각하자. formula_34 역시 완비 격자를 이루며, formula_3는 formula_34 위에서도 단조함수이다. 따라서 formula_34에 대하여 명제 (가)가 성립한다. 이는 정확히 formula_1에 대한 명제 (나)와 일치한다.
명제 (다)의 증명. formula_40가 formula_5의 임의의 부분 집합이라고 하자. formula_5에서 formula_40의 상한이 존재함을 보이면 충분하다. formula_40의 formula_1에서의 상한 formula_46를 생각하자. 그렇다면 구간 formula_47는 formula_40의 상계의 집합이며, 완비 격자를 이룬다 (이는 부분 격자이기도 하지만, 부분 완비 격자가 아닐 수 있다). 임의의 formula_49에 대하여 formula_50이므로, formula_51이다. formula_52에 대하여, 만약 formula_53라면, formula_54이다. 따라서, formula_3를 formula_56 위의 함수 formula_57로 여길 수 있다. 명제 (나)에 따라, formula_58의 최소 고정점이 존재한다. 이는 formula_3의 고정점이며, formula_40의 상계가 되는 가장 작은 formula_3의 고정점이다. 다시 말해, formula_40의 formula_5에서의 상한이다.
고정점 집합이 부분 격자가 아닌 경우.
고정점 집합은 완비 격자이지만, 부분 격자가 아닐 수 있다. 예를 들어, 다음과 같은 부분 순서 집합을 생각하자.
그렇다면, formula_1은 완비 격자를 이룬다. 이제 formula_2이며
라고 하자. formula_3는 formula_1 위의 단조함수이며, formula_71와 formula_72은 formula_3의 고정점이지만, formula_74는 formula_3의 고정점이 아니다. (formula_71와 formula_72의 formula_5에서의 상한은 formula_79가 아닌 formula_80이다.) 따라서, formula_5는 formula_1의 부분 격자가 아니다.
귀결.
완비 격자는 공집합일 수 없으므로, 이 정리는 상기한 formula_3에 적어도 한개의 고정점이 있음을, 나아가서 최소 고정점이 있음을 보장한다.
조건을 추가하여 임의의 부분 순서 집합에 대하여 유사한 결과를 증명할 수 있다. 이를 동역학계 이론에 적용하여 프랙탈의 일종인 반복함수계(iterated function system) 연구에 사용할 수 있다.
모든 증가수열 formula_84에 대해 formula_85이면, formula_3의 최소 고정점은 formula_87이며, 이는 정리의 구성적 버전(Kleene fixed-point theorem)을 제공한다.
이론 컴퓨터 과학에서, 단조함수에 대한 최소 고정점 정리는 프로그램 의미론을 정의하는 데 사용된다. 이 경우 특히 격자 L을 특정 집합의 모든 부분집합들을 모은 것, 즉 멱집합 격자로 가정하는 특수한 케이스에 대하여 집중하는 것이 일반적이다. 그리고 나서 f의 고정점이 되기 위해 필요한 조건을 가지는 최소의 집합을 찾아낸다.
역.
반대로, 모든 단조함수의 고정점이 존재하는 격자는 완비 격자이다. 즉, 타르스키 고정점 정리는 완비 격자의 정의로 삼을 수 있다. 그러나 모든 단조함수가 고정점이 존재하는 부분 순서 집합은 완비 격자일 필요가 없다.
역의 증명.
격자 formula_1이 완비 격자 위에 항상 고정점이 없는 단조함수 formula_2를 구성하면 족하다. 두 부분 집합 formula_90에 대하여, 다음 조건들을 생각하자.
만약 formula_91와 formula_92가 위 조건들을 만족시킨다면, 함수
는 단조함수이며, 고정점이 존재하지 않는다. 따라서, 조건 (라)~(사)를 만족시키는 formula_91와 formula_92를 찾는 것으로 족하다. 모든 부분 집합의 상한이 존재하는 부분 순서 집합은 완비 격자이므로, 상한이 없는 formula_1의 부분 집합 formula_106가 존재한다. 편의상 그 크기 formula_107가 최소라고 하자. formula_1이 격자이므로, formula_107은 0이거나 무한 기수이다. 이제, 임의의 순서수 formula_110에 대하여, formula_111의 크기는 formula_107미만이므로, 상한
이 존재한다. formula_114는 단조 초한 점렬이지만, 순단조가 아닐 수 있다. 중복된 항을 제거하여 순단조 초한 점렬 formula_115로 만들자 (길이가 formula_107인 것은 formula_107의 최소성을 사용하여 보일 수 있다). 이 경우, formula_118는 정렬 전순서 집합이다. 만약 formula_91의 상한이 존재한다면, 이는 formula_106의 상한이 되어 모순이 일어난다. 따라서 formula_91의 상한이 존재하지 않는다. formula_91의 상계들로 구성된 순감소 초한 점렬들의 집합 위에 다음과 같은 부분 순서를 주자.
즉, 끝에 항을 추가하면 더 큰 초한 점렬을 얻는다. 초른 보조정리에 따라, 이 부분 순서에 따른 극대 원소 formula_124가 존재한다 (formula_125가 기수일 필요는 없다). formula_126의 반대 순서 집합 formula_93은 정렬 전순서 집합이다. 만약 formula_128가 존재한다면, formula_128 역시 formula_91의 상계이다. formula_91의 상한이 존재하지 않으므로, formula_132인 formula_91의 상계 formula_134가 존재한다. 이 경우, formula_135는 formula_91의 상계이며, formula_137이다. 이는 formula_124의 극대성과 모순이다. 따라서, formula_92의 하한 역시 존재하지 않는다. 이제, formula_118와 formula_126에 대하여 조건 (사)를 증명하는 일만 남았다. 귀류법을 사용하여, formula_134이 formula_91의 상계이자 formula_92의 하계라고 하자. 그렇다면, formula_124의 극대성에 따라 formula_95이다. 따라서 formula_79는 formula_92의 하한이며, 이는 모순이다.
일반화.
격자 formula_1의, 공집합이 아닌 두 부분 격자 formula_25, formula_151에 대하여, 다음과 같은 이항 관계를 정의하자.
특히, 만약 formula_153이라면, 임의의 formula_20에 대하여, formula_155인 formula_156이 존재하며, 마찬가지로 임의의 formula_156에 대하여, formula_155인 formula_20이 존재한다. 즉, formula_160이며 formula_161이다. 이 이항 관계는 공집합이 아닌 부분 격자의 집합 위의 부분 순서를 이룬다. formula_1의 원소는 자연스럽게 formula_1의 부분 격자로 여길 수 있다. 이 경우, 부분 격자의 순서는 원소의 순서를 확장한다. 따라서, 아래의 정리는 타르스키 고정점 정리를 일반화한다.
다음이 주어졌다고 하자.
그렇다면, formula_3의 고정점 집합
은 완비 격자를 이룬다. 또한, formula_3의 최대·최소 고정점은 다음과 같다.
일반화의 증명.
타르스키 고정점 정리의 증명과 유사하게, 다음 네 명제를 보인다. 이들 가운데 명제 (아)와 (자), 명제 (차)와 (카)는 서로 쌍대이므로 하나씩만 증명하여도 좋다.
명제 (아)의 증명. formula_183이므로, formula_184이면 충분하다. 임의의 formula_20가 주어졌다고 하자. formula_25의 정의에 따라, formula_187이며 formula_188라고 하자. formula_21이며 formula_3가 단조함수이므로, formula_191이며 formula_192라고 하자. formula_193이 부분 완비 격자이므로, formula_194이다. 임의의 formula_20에 대하여 formula_196이므로, formula_197이다. formula_3의 단조성에 따라, formula_199인 formula_200가 존재한다. 즉, formula_201이며, 따라서 formula_202이다. 따라서, formula_203은 formula_3의 고정점이 맞다.
명제 (차)의 증명. formula_46가 formula_40의 formula_1에서의 상한이라고 하자. 그렇다면, formula_56은 완비 격자를 이룬다. 임의의 formula_49에 대하여, formula_210이며 formula_211이므로, formula_212인 formula_213가 존재한다. 이 경우, formula_214이며 formula_215이다. 따라서, formula_3의 단조성에 의하여, 만약 formula_217라면, formula_218은 공집합이 아니다. 또한, formula_219는 formula_1의 부분 완비 격자이다. 따라서, formula_221는 formula_56의 부분 완비 격자를 이룬다. 즉, formula_223는 단조함수 formula_224를 정의한다. 명제 (자)에 따라, formula_225의 최소 고정점이 존재하며, 이는 formula_40의 formula_5에서의 상한이다.
역사.
1927년 브로니스와프 크나스터()와 알프레트 타르스키가 멱집합 격자 위 단조함수의 고정점의 존재를 증명하였다. 타르스키 고정점 정리의 오늘날 형태는 1939년 타르스키가 도입하였으며, 1939년~1942년 동안 타르스키의 몇몇 공개 강의에서 소개되었다. 타르스키 고정점 정리의 역은 앤 모렐()이 증명하였다. 타르스키 고정점 정리의 다중 값 일반화는 저우린()이 초모듈러 게임()의 내시 균형의 존재를 보이기 위하여 증명 및 사용하였다.