Functional completeness and primitive positive decomposition of relations on finite domains

기술 요약: 유한 도메인 상의 관계에 대한 기능적 완전성과 원시 긍정적 분해

문제 정의
본 논문은 고차수(higher-arity) 관계를 원시 긍정 공식(primitive positive formulas, ppfs)을 사용하여 저차수 관계, 특히 이항 관계(binary relations)로 분해하는 문제를 다룬다. 원시 긍정 공식은 술어(predicate)에 결합(conjunction)과 존재 양화사(existential quantifier)를 적용한 것이다. 이 문제로 알려진 관계적 축소 정리(Relational Reduction Thesis, RRT)는 $n$-항 관계($n \ge 2$)가 이항 관계로 축소될 수 있다고 상정하지만, 모든 이항 관계가 단항 관계로 축소되는 것은 아니다.

기능적 유사체인 기능적 축소 정리(Functional Reduction Thesis, FRT)—즉, $n$-입력 함수가 2-입력 함수로 축소된다는 정리—는 다가 논리(many-valued logic)에 관한 포스트(Post)의 연구와 셰퍼 함수(Sheffer functions)를 통해 잘 확립되어 있으나, 유한 도메인에서의 관계적 사례는 그동안 명확하지 않았다. 기존의 결과들은 파편적이거나 비구성적이었으며, 도메인을 확장(hypostatic abstraction)하는 방식에 의존했다. 그러나 이는 새로운 원소를 추가하지 않고는 유한 도메인에서 실행 불가능하다. 또한, 불리언 도메인(Boolean domains)에서는 (기약 불가능한 삼항 관계가 존재하기 때문에) RRT가 실패한다는 것이 알려져 있는데, 이러한 실패의 구조적 이유와 일반적인 유한 도메인에서의 성공 조건에 대한 통일되고 기초적인 설명이 필요했다.

방법론
저자는 관계를 "다치 부분 정의 함수(multivalued partially defined functions, relatives)"로 해석함으로써 기능적 완전성과 관계적 분해 사이를 잇는 구성적 접근 방식을 채택한다. 방법론은 다음 세 단계로 진행된다:

1. 상대적 축소 (관계에서 삼항 관계로):
   본 논문은 $n$-항 관계 $R$을 구별된 출력 인자를 가진 'relative'로 취급한다. $R$을 다치 함수(multifunction)와 도메인 관계로 분해한다. 값 선택자(value selectors, 다치 함수의 이미지에서 값을 선택하는 함수)를 활용하여, 저자는 다치 함수를 일반 함수 $f(t, x_1, \dots, x_{n-1})$로 축소한다. 다가 논리의 포스트 정형 디스정규형(canonical disjunctive normal forms)을 통해 알려진 $n$-입력 함수의 2-입력 함수로의 기능적 축소를 활용함으로써, 본 논문은 임의의 관계가 삼항 관계(2-입력 함수의 그래프)와 저차수 관계들의 합성으로 분해될 수 있음을 입증한다.

2. 논리합의 존재 양화화 (삼항에서 이항으로):
   삼항 관계를 이항 관계로 축소하기 위해, 저자는 공여한계(cofinite) 관계(여집합이 유한한 관계)를 위한 구성을 도입한다. 이 방법은 hypostatic abstraction의 대칭적 개념이다. 새로운 원소로 튜플을 인코딩하는 대신, 공여한계 관계의 보집합 논리합 정규형(Complement Conjunctive Normal Form, CCNF)에 내재된 논리합을 존재 양화로 변환한다. 이는 인덱싱 변수를 도입하고 단항 'coliterals'의 논리합을 모사하는 특정 이항 술어를 정의함으로써 달성된다. 이 단계는 $n$의 차수가 도메인 크기 $|D|$를 초과하지 않을 때만 유효하며, 이는 인덱스를 도메인으로의 단사 함수로 삽입할 수 있게 한다.

3. 본드 축소(Bond Reduction)와 피어스의 정리(Peirce's Thesis):
   본 논문은 원시 긍정 합성(primitive positive composition)과 피어스의 원래 "결합(bonding)"(상대적 곱과 변수 식별을 포함하는 제한된 합성) 사이의 관계를 분석한다. $n \ge 4$인 경우, pp-축소 가능성과 본드 축소 가능성이 삼항 'teridentities'($I_3$)를 허용할 때 동치임을 증명한다. 그러나 삼항 관계의 경우, 본드 축소 가능성은 pp-축소 가능성보다 엄격히 약하다.

주요 기여 및 결과

• 정리 2 (상대적 축소): 임의의 도메인에서, 모든 $n$-항 관계는 함수 $f: D^n \to D$와 도메인 관계의 합성으로 분해된다. 결정적으로, 기능적으로 완전한 2-입력 함수 집합이 존재하면, 모든 관계는 해당 집합에 속하는 함수들의 그래프로 분해될 수 있다. 이는 임의의 유한 도메인에서 모든 $n$-항 관계($n \ge 4$)가 삼항 관계로 축소될 수 있음을 의미한다.
• 따름정리 1 (셰퍼 관계): 임의의 유한 도메인에서, 셰퍼 함수들의 그래프인 삼항 관계들이 단독으로 원시 긍정 완전 시스템을 형성할 수 있는 삼항 관계가 존재한다. 이는 비불리언 도메인에 대한 "셰퍼 관계"의 존재를 입증한다.
• 정리 3 (공여한계 관계의 이항 축소): $|D| \ge 3$인 도메인에 대해, 모든 공여한계 $n$-항 관계($3 \le n \le |D|$)는 이항 관계로 축소된다. 이 구성은 coliterals의 논리합을 이항 술어에 대한 존재 양화로 변환하는 것에 기반한다.
• 정리 4 (불리언 도메인에서의 불가약성): 본 논문은 불리언 도메인에서 삼항 관계 $\neg I_3$(삼항 항등 관계의 보집합)가 이항 관계로 축소 불가능함을 보여주는 기초적인 증명을 제공한다. 이는 $\neg I_3$가 "bijunctive"(2CNF로 표현될 수 없음)가 아님을 보임으로써 입증되며, pp-합성은 bijunctivity를 보존하므로, $\neg I_3$는 이항 관계(모두 bijunctive임)로 축소될 수 없다.
• 정리 5 & 6 (본드 vs. pp-축소 가능성): 본 논문은 $n \ge 4$인 경우, pp-축소 가능성이 (teridentities를 사용하는) 본드 축소 가능성과 동치임을 명확히 한다. 그러나 삼항 관계의 경우, 본드 축소 가능성은 엄격히 더 약하다. 구체적으로, 적어도 2개의 원소를 가진 임의의 도메인에서 $I_3$는 본드 불가약(bond irreducible)이다.

의의 및 주장
본 논문은 기능적 축소 정리(FRT)와 관계적 축소 정리(RRT) 사이의 직접적이고 기초적인 연결을 확립함으로써, 유한 도메인에 대한 피어스의 축소 정리에 대한 "통일된 증명"을 제공한다고 주장한다.

• 통합: 관계의 그래프가 기능적 완전 집합의 관계적 pp-완전 시스템을 형성함을 보여줌으로써, 기능적 완전성과 관계적 완전성 사이의 단절을 해결한다.
• 구성적 성격: 갈로아 연결(Galois connections)이나 도메인 확장에 의존하는 기존의 비구성적 증명과 달리, 이 구성은 계산적으로 유효하며 포스트의 논리(Post's logics)와 같은 잘 발달된 기능적 분해 방법을 활용한다.
• 실패의 설명: 본 논문의 구성은 왜 RRT가 불리언 도메인에서 실패하는지를 명확히 설명한다: 즉, 인덱스를 위한 인젝션이 부족하여($n > |D|$) 고차 논리합을 존재 양화로 변환할 수 없기 때문이다.
• 새로운 개념: "셰퍼 관계"라는 개념을 도입하고, hypostatic abstraction을 "논리합의 존재 양화화"의 대칭적 과정으로 바라보는 새로운 관점을 제공한다.

저자는 자신의 구성이 관계를 삼항 및 (공여한계의 경우) 이항 관계로 축소하는 것을 설명하지만, 임의의 유한 도메인에 대한 관계적 완전성에 대한 포스트나 슬루페키(Slupecki)의 기준에 대한 일반적인 유사체를 제공하지는 않으며, 최대 코클론(maximal coclones)을 완전히 특징짓지도 않는다는 점을 겸허하게 언급한다. 본 논문은 비불리언 도메인에서 이항 셰퍼 관계가 존재하는지에 대한 질문을 과제로 남겨둔다.