상위 질문
타임라인
채팅
관점

타르스키 고정점 정리

위키백과, 무료 백과사전

Remove ads

순서론에서 타르스키 고정점 정리(영어: Tarski’s fixed point theorem) 또는 크나스터-타르스키 정리(영어: Knaster–Tarski theorem)는 완비 격자에서 자신으로 가는 단조함수고정점이 존재한다는 정리이다.

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

정의

요약
관점

완비 격자 단조함수 가 주어졌다고 하자. 타르스키 고정점 정리에 따르면, 고정점의 집합

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

증명

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

  • (가) 최대 고정점이다.
  • (나) 최소 고정점이다.
  • (다) 완비 격자이다.

명제 (가)의 증명. 라고 하자. 임의의 에 대하여, 이므로, 이다. 따라서 이다. 반대로, 이므로, 의 정의에 따라 이다. 따라서 이다. 따라서, 고정점이다. 모든 고정점은 에 속하므로, 최대 고정점이다.

명제 (나)의 증명. 의 반대 격자 를 생각하자. 역시 완비 격자를 이루며, 위에서도 단조함수이다. 따라서 에 대하여 명제 (가)가 성립한다. 이는 정확히 에 대한 명제 (나)와 일치한다.

명제 (다)의 증명. 의 임의의 부분 집합이라고 하자. 에서 상한이 존재함을 보이면 충분하다. 에서의 상한 를 생각하자. 그렇다면 구간 상계의 집합이며, 완비 격자를 이룬다 (이는 부분 격자이기도 하지만, 부분 완비 격자가 아닐 수 있다). 임의의 에 대하여 이므로, 이다. 에 대하여, 만약 라면, 이다. 따라서, 위의 함수 로 여길 수 있다. 명제 (나)에 따라, 최소 고정점이 존재한다. 이는 의 고정점이며, 의 상계가 되는 가장 작은 의 고정점이다. 다시 말해, 에서의 상한이다.

고정점 집합이 부분 격자가 아닌 경우

고정점 집합은 완비 격자이지만, 부분 격자가 아닐 수 있다. 예를 들어, 다음과 같은 부분 순서 집합을 생각하자.

그렇다면, 완비 격자를 이룬다. 이제 이며

라고 하자. 위의 단조함수이며, 고정점이지만, 고정점이 아니다. (에서의 상한가 아닌 이다.) 따라서, 의 부분 격자가 아니다.

Remove ads

귀결

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

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

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

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

Remove ads

요약
관점

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

역의 증명

격자 완비 격자 위에 항상 고정점이 없는 단조함수 를 구성하면 족하다. 두 부분 집합 에 대하여, 다음 조건들을 생각하자.

  • (라) 정렬 전순서 집합이다.
  • (마) 의 반대 순서 집합 정렬 전순서 집합이다.
  • (바) 임의의 에 대하여,
  • (사) 동시에 상계이자 하계의 원소가 존재하지 않는다.

만약 가 위 조건들을 만족시킨다면, 함수

단조함수이며, 고정점이 존재하지 않는다. 따라서, 조건 (라)~(사)를 만족시키는 를 찾는 것으로 족하다. 모든 부분 집합의 상한이 존재하는 부분 순서 집합완비 격자이므로, 상한이 없는 부분 집합 가 존재한다. 편의상 그 크기 가 최소라고 하자. 격자이므로, 은 0이거나 무한 기수이다. 이제, 임의의 순서수 에 대하여, 의 크기는 미만이므로, 상한

이 존재한다. 는 단조 초한 점렬이지만, 순단조가 아닐 수 있다. 중복된 항을 제거하여 순단조 초한 점렬 로 만들자 (길이가 인 것은 의 최소성을 사용하여 보일 수 있다). 이 경우, 정렬 전순서 집합이다. 만약 상한이 존재한다면, 이는 상한이 되어 모순이 일어난다. 따라서 상한이 존재하지 않는다. 상계들로 구성된 순감소 초한 점렬들의 집합 위에 다음과 같은 부분 순서를 주자.

즉, 끝에 항을 추가하면 더 큰 초한 점렬을 얻는다. 초른 보조정리에 따라, 이 부분 순서에 따른 극대 원소 가 존재한다 (기수일 필요는 없다). 의 반대 순서 집합 정렬 전순서 집합이다. 만약 가 존재한다면, 역시 상계이다. 의 상한이 존재하지 않으므로, 상계 가 존재한다. 이 경우, 의 상계이며, 이다. 이는 의 극대성과 모순이다. 따라서, 하한 역시 존재하지 않는다. 이제, 에 대하여 조건 (사)를 증명하는 일만 남았다. 귀류법을 사용하여, 상계이자 하계라고 하자. 그렇다면, 의 극대성에 따라 이다. 따라서 하한이며, 이는 모순이다.

Remove ads

일반화

요약
관점

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

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

다음이 주어졌다고 하자.

  • 완비 격자
  • 단조함수 . 여기서 의 부분 완비 격자의, 위에서 정의한 순서에 따른 부분 순서 집합이다. (부분 완비 격자는 완비 격자인 부분 격자보다 더 강한 개념이다. 전자는 모든 상한과 하한이 원래 격자와 일치하지만, 후자는 모든 유한 집합의 상한·하한의 일치만을 요구한다.)

그렇다면, 고정점 집합

완비 격자를 이룬다.[2]:297, Theorem 1 또한, 최대·최소 고정점은 다음과 같다.

일반화의 증명

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

  • (아) 에 대하여, 최대 고정점이다.
  • (자) 에 대하여, 최소 고정점이다.
  • (차) 모든 에서의 상한이 존재한다.
  • (카) 모든 에서의 하한이 존재한다.

명제 (아)의 증명. 이므로, 이면 충분하다. 임의의 가 주어졌다고 하자. 의 정의에 따라, 이며 라고 하자. 이며 단조함수이므로, 이며 라고 하자. 이 부분 완비 격자이므로, 이다. 임의의 에 대하여 이므로, 이다. 의 단조성에 따라, 가 존재한다. 즉, 이며, 따라서 이다. 따라서, 고정점이 맞다.

명제 (차)의 증명. 에서의 상한이라고 하자. 그렇다면, 완비 격자를 이룬다. 임의의 에 대하여, 이며 이므로, 가 존재한다. 이 경우, 이며 이다. 따라서, 의 단조성에 의하여, 만약 라면, 공집합이 아니다. 또한, 의 부분 완비 격자이다. 따라서, 의 부분 완비 격자를 이룬다. 즉, 단조함수 를 정의한다. 명제 (자)에 따라, 최소 고정점이 존재하며, 이는 에서의 상한이다.

Remove ads

역사

Thumb
브로니스와프 크나스터 (1893~1980)
Thumb
알프레트 타르스키 (1901~1983)

1927년 브로니스와프 크나스터(폴란드어: Bronisław Knaster)와 알프레트 타르스키멱집합 격자 위 단조함수고정점의 존재를 증명하였다.[3][4]:286, 각주 2 타르스키 고정점 정리의 오늘날 형태는 1939년 타르스키가 도입하였으며, 1939년~1942년 동안 타르스키의 몇몇 공개 강의에서 소개되었다.[4]:286, 각주 2 타르스키 고정점 정리의 역은 앤 모렐(영어: Anne C. Morel)이 증명하였다.[1] 타르스키 고정점 정리의 다중 값 일반화는 저우린(중국어: 周林)이 초모듈러 게임(영어: supermodular game)의 내시 균형의 존재를 보이기 위하여 증명 및 사용하였다.[2]

같이 보기

참고 문헌

외부 링크

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads