🔢 mathematics

Functional completeness and primitive positive decomposition of relations on finite domains

本論文は、関数完全性を活用し、特定の選言を存在量化へと変換することによって、有限領域上の高次関係を二項関係へと分解する、新しく初等的かつ計算効率の高い構成法を提示しており、それによってピアースの還元テーゼスの一様な証明を提供し、いかなるシェファー関数のグラフもそのような関係をすべて合成できることを実証している。

原著者： Sergiy Koshkin

公開日 2026-06-19

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Sergiy Koshkin

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

想像してみてください。あなたは、ある機械の巨大で複雑な取扱説明書を持っています。そのマニュアルには、多くの手が同時に動く必要がある作業（例えば、5人でのダンスの動きのようなもの）の手順が書かれています。その紙は、シンプルな問いを投げかけています。「この複雑な多人数による指示を、一連のシンプルな2人用の指示へと分解できるだろうか？」

著者であるセルゲイ・コシュキン（Sergiy Koshkin）は、「はい、できます」と言っています。ただし、その機械が作動する部屋のサイズ（ドメイン）に応じて、いくつかの興味深いひねりが加わります。

以下は、日常的な比喩を用いたこの論文の解説です。

1. 大きなアイデア：複雑さを分解する

複雑な関係（例：「AはBの兄弟であり、BはCの親である」）を、複雑に絡まった結び目だと考えてください。この論文は、その結び目を、より小さくシンプルなループへと解いていくプロセスについてのものです。

数学やコンピュータサイエンスでは、しばしば「関係（リレーション）」を扱います。

単項（Unary）： 1つのもの（例：「赤い」）。
二項（Binary）： 2つのもの（例：「〜より高い」）。
三項（Ternary）： 3つのもの（例：「〜の間にある」）。
n項（N-ary）： 多くのもの。

目標は、5人が理解する必要があるルールを、2人または3人だけで理解できるルールを連鎖させることで構築できることを示すことです。

2. 無限の部屋 vs 有限の部屋

論文では、2種類の世界を区別しています。

無限の世界： 無限の人がいる部屋を想像してください。ここでは、**「仮定的抽象化（Hypostatic Abstraction）」**という魔法のようなトリックが使えます。これは、複雑な5人のダンスを、「このグループ全体を、新しい1人の人物だと見なそう」と言うようなものです。どんなに複雑なルールも、即座にシンプルな2人用のルールに変えることができます。簡単ですが、これにはプレースホルダーとして機能する「新しい人々」を無限に用意する必要があります。
有限の世界： これは私たちの現実の世界であり、人の数は限られています。新しい人を勝手に作り出すことはできません。ここからが、この論文が真に力を発揮する場面です。著者は、たとえ人が密集した狭い部屋であっても、複雑なルールを分解することは可能であり、ただし、特定の巧妙な構成が必要であることを示しています。

3. 主なトリック：ルールを「関数」に変える

著者の秘密兵器は、**「相対者（Relatives）」**という概念です。
通常、「関数」は自動販売機のようなものです。コイン（入力）を入れると、スナック（出力）が出てきます。これは一方通行の道です。
「関係」はもっとグループチャットに似ています。全員がつながっていますが、誰も厳格な「ボス」や「出力」ではありません。

比喩：
グループチャットで全員が会話している状況を想像してください。これを単純化するために、著者はこう言います。「チャット内の誰か一人を『ボス』（出力）とし、他の全員は単にメッセージを送っている状態だと仮定しよう」。
関係を「部分関数」（返信しないこともあるボス）であると見なすことで、著者は関数を分解するためのよく知られた数学的テクニックを利用することができます。

プロセス：

ボスを特定する： 複雑なルールの中の変数のうち、一つを「出力」として選びます。
セレクター（選択器）： もしルールが複数の可能な出力を許容する場合（ボスがテキストを送るかメールを送るか選べる場合など）、著者は一つ特定の経路を選ぶための「セレクター」を使用します。
連鎖： 関数を手に入れたら、それを分解できます。複雑な機械を単純な歯車から組み立てるように、あらゆる複雑な関数を、単純な2入力の歯車（2つのものを受け取って1つのものを作る関数）から構築できます。
結果： これにより、あらゆる複雑なルールが、三項関係（3つのものに関わるルール）から構築できることが証明されます。これは「仲介役」のルールです。*「もしAがBに対してXを行い、BがCに対してYを行うなら、AはCとつながっている」*といった具合です。

4. 最終ステップ：3人から2人へ

論文はさらに一歩進みます。それらの3人用のルールを、2人用のルールに分解できるでしょうか？

大きな有限ドメイン（3人以上）の場合： はい！著者は**「選言の存在化（Existentialization of Disjunctions）」**と呼ばれる巧妙なトリックを使用します。
- 比喩： 「帽子、あるいはスカーフ、あるいは手袋を着用していれば入場できる」というルールがあるとします。
- 小さな部屋では、「または（OR）」を単純な連鎖に変えることは容易ではありません。しかし、著者は、もし十分な人数（少なくとも3人）がいれば、その「または」のリストを「チケットを持っている人はいるか？」という問いに変えられることを示しています。一時的な変数（「チケット保持者」）を導入し、「そのルールを成立させるチケットを持っている人が存在する（Exists）か？」と問うのです。
- これにより、複雑な「または（OR）」の論理を、単純な「存在する（Exists）」の論理へと変換し、3人用のルールを完全に2人用のルールから構築できるようにします。
小さな有限ドメイン（ブール値／2人）の場合： いいえ。
- もし世界がたった二人（真/偽、あるいは0/1）だけなら、壁にぶつかります。2人用のルールに分解できない特定の3人用のルールが存在します。
- 比喩： それは、特定の3D形状を、2Dの平面パーツだけで作ろうとするようなものです。いくつかの形状は、どうしてもフィットしません。論文は、2人の世界においては、特定の複雑な関係は「既約（irreducible）」であり、これ以上単純化できない原子的な構成要素であることを証明しています。

5. 「シェファー」の驚き

論文はまた、面白い発見をしています。論理学において、あらゆる論理ゲートを構築できる単一の「魔法のスイッチ」（シェファーの剰余）が存在するように、有限ドメインにおいて他のあらゆる関係を構築できる単一の**「シェファー関係（Sheffer Relation）」**（特定の3人用のルール）が存在します。

それは、もし十分な数があれば、どんな城、車、宇宙船でも作ることができる、特定の「レゴブロック」を見つけたようなものです。

「まとめ」の要点

複雑さは管理可能である： 多くの変数を含むほぼすべての複雑なルールは、わずか2つまたは3つの変数を持つ単純なルールへと分解できます。
「仲介役」は三項である： 最も効率的な分解方法は、通常、3つの変数（三項）で止まります。
サイズが重要である： 世界が十分に大きい（3つ以上のアイテムがある）場合、すべてを2つの変数に分解できます。世界が極めて小さい（2つのアイテムしかない）場合、一部の3変数ルールは行き詰まり、単純化できません。
関数は関係を助ける： 関係を関数（ボスと労働者がいるもの）として扱うことで、関係の問題を解決するための既存の数学ツールを利用できます。

この論文は、本質的に、複雑なデータの関係を解体するための、よりシンプルな「新しい取扱説明書」を提供しており、限られた世界であっても、特定の「ヘルパー」となるルールさえあれば、単純な二人間の相互作用からあらゆるものを構築できることを証明しています。

技術要約：有限ドメインにおける関係の関数的完全性と原始陽的な分解

問題提起
本論文は、原始陽的な論理式（ppf）を用いて、高次（高アリティ）の関係を低次（低アリティ）、特に二項関係へと分解する問題を扱っている。原始陽的な論理式とは、述語に連言（conjunction）と存在量化を適用したものである。この問題は「関係的還元定理（Relational Reduction Thesis, RRT）」として知られており、 $n$ 変数関係（ $n \ge 2$ ）は二項関係へと還元可能であるが、すべての二項関係が単項関係へと還元できるわけではないという命題である。

その関数的な類似物である「関数的還元定理（Functional Reduction Thesis, FRT）」——すなわち、 $n$ 入力関数は2入力関数へと還元可能であるという命題——は、多値論理におけるポスト（Post）の研究やシェファー関数を通じて確立されているが、関係の場合、有限ドメイン上での状況はこれまで不明瞭であった。先行研究は断片的であったり、非構成的であったり、あるいはドメインの拡張（仮説的抽象化）に依存していたりした。しかし、ドメインに要素を追加することなく有限ドメイン上でこれを行うことは不可能である。また、ブール・ドメインにおいては（既約な三項関係が存在するため）RRTが成立しないことが知られているが、その失敗の構造的な理由と、一般的な有限ドメインにおいて成功するための条件を解明するための統一的かつ初等的な説明が必要とされていた。

手法
著者は、関係を「多価な部分定義関数（relative）」として解釈することにより、関数的完全性と関係的分解の架け橋となる構成的なアプローチを採用している。その手法は以下の3段階で進行する。

相対的還元（関係から三項へ）：
本論文では、 $n$ 項関係 $R$ を、特定の出力引数を持つ「relative」として扱う。これにより、 $R$ を多価関数とドメイン関係へと分解する。値選択関数（多価関数の像から値を選択する関数）を利用することで、著者は多価関数を通常の関数 $f(t, x_1, \dots, x_{n-1})$ へと還元する。多値論理におけるポストの標準的な選言標準形（disjunctive normal forms）を利用した、 $n$ 入力関数から2入力関数への既知の関数的還元を活用することで、任意の関係が三項関係（2入力関数のグラフ）と低次関係の合成として分解できることを示している。
選言の存在量化（三項から二項へ）：
三項関係を二項関係へと還元するために、本論文は「余有限（cofinite）」な関係（補集合が有限である関係）のための構成法を導入している。この手法は、仮説的抽象化の双対である。新しい要素にタプルをエンコードする代わりに、余有限な関係の補集合選言標準形（CCNF）に含まれる選言を、存在量化へと変換する。これは、インデックス変数（indexing variable）を導入し、単項の「coliterals（補リテラル）」の選言を模倣する特定の二項述語を定義することによって達成される。このステップは、アリティ $n$ がドメインのサイズ $|D|$ を超えない場合にのみ有効であり、これはインデックスをドメインへ注入（injection）できることを意味する。
ボンド（結合）の還元とパースの定理：
本論文は、原始陽的な合成と、パース（Peirce）のオリジナルの「ボンド（結合）」（相対積と変数の同一視を含む制限された合成）との関係を分析している。 $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（二値的/bijunctive）」ではない（2CNFとして表現できない）ことを示すことで証明される。pp-合成はbijunctivityを保存するため、 $\neg I_3$ は二項関係（すべてがbijunctiveである）へと還元できない。
定理5および6（ボンド対pp-還元可能性）： 本論文は、 $n \ge 4$ において、pp-還元可能性が（teridentitiesを用いた）ボンド還元可能性と等価であることを明らかにしている。しかし、三項関係については、ボンド還元可能性は厳密に弱く、具体的には、 $I_3$ は少なくとも2つの要素を持つ任意のドメインにおいてボンド既約である。

意義と主張
本論文は、有限ドメインにおけるパースの還元定理の直接的かつ初等的な、関数的還元定理（FRT）と関係的還元定理（RRT）の間の接続を確立することにより、パースの還元定理の「統一的な証明」を提供すると主張している。

統一： 関数的完全性と関係的完全性の間の断絶を、関数的に完全な集合のグラフが関係的にpp完全なシステムを形成することを示すことで解消している。
構成的： ガロア接続やドメイン拡張に依存する従来の非構成的な証明とは異なり、この構成は計算量的に有効であり、関数の分解（ポストの論理）の確立された手法に基づいている。
失敗の説明： この構成は、なぜRRTがブール・ドメインで失敗するのかを解明している。それは、インデックスの注入（ $n > |D|$ の場合）が不可能なために、高次の選言を存在量化へと変換できないためである。
新しい概念： 「シェファー関係」という概念を導入し、「仮説的抽象化」を「選言の存在量化」の双対プロセスとして捉える新しい視点を提供している。

著者は謙虚に、この構成は関係を三項関係へ、そして（余有限の場合には）二項関係へと還元することを説明するものではあるが、任意の有限ドメインにおける関係的完全性のためのポストやスレプッキー（Slupecki）の基準の一般的な類似物を提供するものではなく、また極大コクローン（maximal coclones）を完全に特徴付けるものでもないと述べている。また、非ブール・ドメインにおいて二項シェファー関係が存在するかどうかという問いは、今後の課題として残されている。