규칙을 계속 적용하면, 더는 바뀌지 않는 상태가 반드시 있을까요?

A·B·C 각각에 대해 표에 들어 있거나 들어 있지 않거나 두 가지를 정합니다. 따라서 가능한 표는 2³=8개입니다. 아무 표시도 없는 ∅, 한 표시만 있는 {A}·{B}·{C}, 두 표시가 있는 {A,B}·{A,C}·{B,C}, 그리고 세 표시가 모두 있는 {A,B,C}입니다.

이 여덟 집합을 한꺼번에 모은 것이 {A,B,C}의 멱집합입니다. 실험의 함수는 여덟 상태 가운데 하나를 입력받아 다시 여덟 상태 가운데 하나를 출력합니다. 함수의 값이 이 목록 밖으로 나가면 같은 정리의 가정을 그대로 적용할 수 없습니다.

고정점이란 특별한 모양의 표가 아니라 F(S)=S를 만족하는 표입니다. 규칙 F를 바꾸면 같은 표가 고정점이 되기도 하고 아니기도 합니다. 그래서 결과 화면에는 입력 S와 출력 F(S)를 함께 적어 직접 비교하도록 하겠습니다.

이 글에서 크고 작음은 표시 수가 아니라 포함 관계로 정합니다. S에 있는 모든 표시가 T에도 있으면 S⊆T라고 씁니다. 예를 들어 {A}⊆{A,B}이지만 {A}⊆{B}는 아닙니다. A는 {B} 안에 없기 때문입니다.

{A}와 {B}는 어느 쪽도 다른 쪽을 포함하지 않습니다. 원소 수가 같다는 이유로 같은 상태도 아닙니다. 이런 식으로 비교할 수 없는 원소를 허용하는 순서를 부분순서라고 합니다. 모두 한 줄로 늘어세우는 크기 비교와 다릅니다.

이 구별은 곧 중요해집니다. 단조 함수는 서로 비교 가능한 두 입력의 순서를 지키지만, 비교 불가능한 두 입력 사이의 이동을 모두 금지하지는 않습니다. 따라서 단조라는 말만 듣고 모든 시작점의 반복이 한 방향으로 움직일 것이라고 생각하면 안 됩니다.

두 집합 {A}와 {B}를 모두 포함하는 집합은 여러 개일 수 있습니다. 그중 가장 작은 집합은 {A,B}이고, 이것이 두 집합의 최소 상한입니다. 두 집합에 공통으로 포함되는 집합 중 가장 큰 것은 ∅이며, 이것이 최대 하한입니다. 멱집합에서는 합집합과 교집합이 이 역할을 합니다.

완비 격자는 상태들의 어떤 모음을 골라도 그 모음의 최소 상한과 최대 하한이 존재하는 부분순서입니다. 여기에는 무한한 모음과 빈 모음도 포함됩니다. 이번 여덟 상태에서는 모든 합집합과 교집합이 다시 여덟 상태 안에 있습니다. 맨 아래는 ∅, 맨 위는 {A,B,C}입니다.

이 조건이 있으면 필요한 경계 상태를 상태 공간 안에서 취할 수 있습니다. 예를 들어 자연수 0,1,2,…만을 보통 순서로 놓으면 전체 집합의 상한인 자연수가 없습니다. F(n)=n+1은 순서를 지키지만 고정점이 없으므로, 단조성만으로 고정점 존재를 말할 수 없음을 보여 줍니다.

단조성은 서로 다른 두 입력을 비교하는 조건입니다. S⊆T이면 F(S)⊆F(T)여야 합니다. 작은 입력의 결과에 있던 표시가 큰 입력의 결과에서는 없어지면 이 조건을 어깁니다. 우리 준비표 규칙은 입력 표시를 늘려도 이전에 성립하던 A→B와 B→C 조건을 무효로 만들지 않으므로 단조입니다.

반면 S⊆F(S)는 한 입력과 그 출력을 비교하는 별도 조건입니다. 이를 여기서는 확장성이라고 부르겠습니다. 단조인 함수라고 반드시 확장적인 것은 아닙니다. 시작 표시를 아무것도 넣지 않고 A→B만 켜면 F({A})={B}가 됩니다. 이 함수는 단조지만 A를 출력에 보존하지 않습니다.

첫 번째 실험은 ‘기존 표를 무조건 복사한 뒤 표시를 추가’하는 규칙이 아닙니다. 선택한 시작 표시와 현재 입력에서 조건이 맞는 규칙의 결과만 다음 표에 넣습니다. 이렇게 갱신 방식을 명시해야 단조성과 확장성을 실제 계산에서 구별할 수 있습니다.

시작 상태가 맨 아래 ∅이면 ∅⊆F(∅)는 항상 성립합니다. 첫 출력이 어떤 집합이든 빈 집합을 포함하기 때문입니다. 단조성을 이 관계에 적용하면 F(∅)⊆F(F(∅))를 얻습니다. 같은 논증을 계속하면 맨 아래에서 출발한 반복은 포함 관계에 따라 커지는 사슬을 이룹니다.

여기서 모든 S에 대해 S⊆F(S)를 가정하지 않았습니다. 맨 아래라는 특별한 출발점이 첫 비교를 제공하고, 단조성이 다음 비교들을 이어 줍니다. 이것이 단조성과 확장성의 차이를 지키면서도 증가하는 반복을 얻는 이유입니다.

실험에서 시작 표시와 규칙을 바꾸어도 함수가 단조인 이 형식은 유지됩니다. 화면은 여덟 입력의 함숫값과 포함 관계가 성립하는 모든 입력 쌍도 검사합니다. 반복의 모양만 눈으로 보고 단조라고 추측하는 것과 정의에 따라 검사하는 것을 구별해 보세요.

꼭 여덟 번을 계산하는 것은 아닙니다. 증가하는 사슬에서는 한 번 들어온 표시가 나중에 사라지지 않습니다. A·B·C 세 표시만 있으므로 엄격히 커지는 변화는 최대 세 번입니다. 그다음 계산에서 상태가 같아지면 고정점임을 확인할 수 있습니다. 실제로는 처음부터 ∅가 고정점일 수도 있습니다.

기본 예에서는 ∅→{A}→{A,B}→{A,B,C}로 세 번 변하고, 다음에 같은 {A,B,C}가 나옵니다. 엄격한 변화 수와 마지막 같음 확인을 포함한 함수 적용 수를 혼동하지 않아야 합니다. 화면의 단계 목록은 마지막 반복 상태도 함께 보여 줍니다.

유한한 상태 공간이라는 조건이 이 종료 설명의 핵심입니다. 일반적인 완비 격자는 무한할 수 있습니다. 고정점 존재 정리는 그런 경우도 다루지만, 지금의 세 표시 계산과 같은 유한 횟수로 언제나 찾을 수 있다고 말하지는 않습니다.

어떤 고정점 T를 하나 잡아 봅시다. 맨 아래 ∅는 T에 포함됩니다. 단조성을 적용하면 F(∅)⊆F(T)=T입니다. 다시 적용해도 F²(∅)⊆T가 유지됩니다. 따라서 맨 아래에서 출발한 모든 반복 상태는 어떤 고정점을 골라도 그 안에 포함됩니다.

유한 반복이 멈춘 상태 L은 F(L)=L이므로 스스로 고정점입니다. 동시에 앞의 논증에 따라 모든 고정점 T에 포함됩니다. 그래서 단지 ‘더 작은 고정점을 못 찾은 상태’가 아니라 모든 고정점보다 아래인 최소 고정점이라고 부를 수 있습니다.

‘극소’와 ‘최소’도 구별할 수 있습니다. 극소는 그보다 엄격히 작은 후보가 없다는 뜻이고, 최소는 모든 후보보다 작거나 같다는 뜻입니다. 부분순서에서는 비교 불가능한 후보들이 있어 두 말이 다를 수 있습니다. 지금의 논증은 모든 고정점과 비교했으므로 최소를 보장합니다.

맨 위 U={A,B,C}에서 시작하면 F(U)⊆U가 항상 성립합니다. 단조성을 적용하면 F(F(U))⊆F(U)이고, 반복은 내려가는 사슬을 이룹니다. 유한한 지금의 상태 공간에서는 어느 순간 같아져 최대 고정점에 도달합니다. 모든 고정점이 각 반복 상태 아래에 있다는 논증은 최소 고정점의 경우와 대칭입니다.

최소와 최대가 같으면 고정점은 하나뿐입니다. 둘이 다르면 그 사이에 여러 고정점이 있을 수 있습니다. 모든 입력을 그대로 돌려주는 항등 함수 F(S)=S라면 여덟 상태가 모두 고정점입니다. 최소는 ∅이고 최대는 U이므로 고정점 존재와 유일성은 다른 결론입니다.

두 번째 실험에서 A와 B의 자리를 바꾸는 함수를 고르면 ∅와 U는 각각 고정점입니다. 맨 아래와 맨 위에서 시작하면 즉시 안정되지만, 다른 상태에서는 다른 일이 생깁니다. 어디에서 출발하는지를 함께 확인해야 반복 결과를 해석할 수 있습니다.

F가 집합 안의 A를 B로, B를 A로 바꾸고 C는 그대로 둔다고 합시다. 입력 S에 포함된 표시를 하나씩 바꾼 결과가 F(S)입니다. S⊆T이면 S의 표시를 바꾼 결과는 T의 표시를 바꾼 결과 안에 있으므로 이 함수는 단조입니다.

그러나 {A}에서 시작하면 {B}, 다음에는 {A}, 그다음에는 다시 {B}가 됩니다. 두 상태는 서로 포함 관계로 비교할 수 없으므로 이 순환이 단조성에 어긋나지 않습니다. ∅, {C}, {A,B}, U는 고정점이지만 {A}에서의 반복은 그곳으로 가지 않습니다.

이 반례는 고정점이 존재한다는 정리와 임의의 시작점에서 반복이 고정점에 도달한다는 주장을 분리합니다. 화면은 반복된 상태를 감지하면 ‘순환’이라고 표시하고 주기를 제시합니다. 같은 상태를 다시 만났다는 이유로 그 상태 자체를 고정점이라고 부르지 않습니다.

전체 집합 U 안에서 들어 있던 표시는 빼고 없던 표시는 넣는 여집합 함수 F(S)=U∖S를 생각해 봅시다. ∅의 출력은 U이고 U의 출력은 ∅입니다. 입력이 커지면 출력은 작아지므로 이 함수는 우리가 요구한 단조성에 맞지 않습니다.

고정점이 있다고 가정하면 A가 그 집합에 들어 있는지 물을 수 있습니다. A가 들어 있으면 출력에서는 빠지고, 들어 있지 않으면 출력에 생깁니다. 어느 경우도 입력과 출력이 같을 수 없습니다. 세 표시 가운데 하나만 보아도 고정점이 없음을 확인합니다.

상태 공간은 여전히 완비 격자인 여덟 상태지만 함수 가정이 실패했습니다. 이것이 고정점 정리의 반례는 아닙니다. 정리는 두 가정이 함께 성립할 때 결론을 보장합니다. 두 번째 실험은 단조성을 어기는 입력 쌍도 제시하여 어느 가정이 깨졌는지 보여 줍니다.

이번에는 F가 기존 표시를 모두 보존하되 A와 B가 둘 다 있으면 C도 추가한다고 합시다. 이 함수는 단조입니다. {A}는 그대로이고 {B}도 그대로이므로 둘 다 고정점입니다. 하지만 둘의 합집합 {A,B}는 C가 추가되어 {A,B,C}가 되므로 고정점이 아닙니다.

타르스키의 정리 1은 모든 고정점의 모임도 원래 순서를 물려받아 완비 격자를 이룬다고 말합니다. 이 말은 고정점 둘의 경계를 원래 격자의 합집합으로 무조건 계산해도 된다는 뜻이 아닙니다. 고정점인 후보들 가운데 두 집합을 모두 포함하는 가장 작은 것을 찾아야 합니다.

이 예에서 {A}와 {B}를 모두 포함하는 고정점은 U뿐입니다. 따라서 고정점들의 격자 안에서 구한 최소 상한은 U이고, 원래 멱집합에서 구한 최소 상한은 {A,B}입니다. 세 번째 실험은 같은 두 집합에 대해 이 두 계산 결과를 나란히 표시합니다.

일반 정리의 한 논증은 반복 횟수 대신 경계를 이용합니다. F(x)≤x인 상태를 모두 모아 보겠습니다. 맨 위 상태는 여기에 속하므로 모임이 비어 있지 않습니다. 완비성 덕분에 이 모임의 최대 하한 m을 상태 공간 안에서 취할 수 있습니다.

모임의 각 x에 대해 m≤x이므로 단조성으로 F(m)≤F(x)≤x입니다. 따라서 F(m)은 그 모임의 하한이고 F(m)≤m입니다. 다시 단조성을 쓰면 F(F(m))≤F(m)이므로 F(m) 자신도 처음 모은 상태들 가운데 하나입니다. m은 그 모임의 하한이므로 m≤F(m)도 얻습니다. 두 방향을 합치면 F(m)=m입니다.

모든 고정점 x는 F(x)≤x인 모임에 속합니다. 그러므로 m은 모든 고정점 아래에 있으며 최소 고정점입니다. 원전은 반대 방향의 집합과 최소 상한으로 최대 고정점을 증명하고 순서를 뒤집는 쌍대성으로 최소의 경우도 얻습니다. 여기서는 최소 쪽을 직접 풀어 썼습니다.

항상 그렇지는 않습니다. 자연수 표시 0,1,2,…와 특별 표시 ★가 있는 무한 집합을 생각해 봅시다. 함수는 0을 항상 넣고, 입력에 자연수 n이 있으면 n+1을 넣으며, 입력에 모든 자연수가 있을 때에만 ★를 넣습니다. 입력이 커져도 만족하던 조건이 깨지지 않으므로 이 함수는 단조입니다.

빈 집합에서 유한 번 반복하면 {0}, {0,1}, {0,1,2}, …처럼 자연수가 하나씩 늘어납니다. 이 모든 유한 단계의 합집합은 자연수 전체이지만 ★는 없습니다. 그런데 그 합집합에 함수를 한 번 적용하면 이제 모든 자연수가 입력에 있으므로 ★가 추가됩니다. 유한 단계들을 모은 결과가 아직 고정점이 아니었던 것입니다.

이 사례의 최소 고정점은 자연수 전체와 ★가 함께 있는 집합입니다. 유한 반복의 합집합에서 바로 고정점에 도달하려면 증가 사슬의 상한을 함수가 보존하는 등의 추가 조건이 필요합니다. 이번 화면의 여덟 상태 실험은 무한 사슬이나 이 추가 조건을 계산하는 도구가 아닙니다.

먼저 상태를 어떻게 비교하는지 적습니다. 이번에는 표시 집합의 포함 관계였고, 서로 비교할 수 없는 상태도 있었습니다. 상태 공간 안에서 필요한 상한과 하한을 구할 수 있는지, 함수가 같은 공간으로 결과를 돌려주는지도 확인했습니다.

다음으로 함수가 단조인지 정의대로 검사합니다. 입력 하나의 결과가 커지는 모습을 보는 것으로 대신할 수 없습니다. 최소 고정점을 유한 반복으로 찾으려면 맨 아래에서 시작한 이유와 상태가 유한하다는 근거도 남겨야 합니다. 임의 시작점의 순환, 단조성을 어긴 여집합 함수, 고정점 합집합의 실패는 각각 다른 경고를 줍니다.

마지막으로 고정점의 의미를 응용 문제에 맞춰 해석합니다. 표시가 더 바뀌지 않는다는 사실만으로 현실의 준비가 완벽하다고 말할 수는 없습니다. 우리가 확인한 것은 명시한 규칙에 대한 안정성과 최소·최대 관계입니다. 규칙이나 관찰할 표시를 바꾸면 새 함수에 대해 다시 계산할 수 있습니다.