🔢 mathematics

Functional completeness and primitive positive decomposition of relations on finite domains

Diese Arbeit präsentiert eine neue, elementare und rechnerisch effektive Konstruktion, die höher-arige Relationen auf endlichen Domänen unter Ausnutzung der funktionellen Vollständigkeit und durch Umwandlung spezifischer Disjunktionen in Existenzquantifizierungen in binäre Relationen zerlegt, wodurch ein einheitlicher Beweis für Peirces Reduktionsthese erbracht und demonstriert wird, dass der Graph jeder Sheffer-Funktion alle derartigen Relationen komponieren kann.

Ursprüngliche Autoren: Sergiy Koshkin

Veröffentlicht 2026-06-19

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Sergiy Koshkin

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie haben eine riesige, komplizierte Bedienungsanleitung für eine Maschine. Diese Anleitung beschreibt, wie man Dinge erledigt, die viele Hände erfordern, die gleichzeitig zusammenarbeiten (wie ein Tanzschritt für 5 Personen). Das Papier stellt eine einfache Frage: Können wir diese komplexe, mehrpersonen-basierte Anweisung in eine Serie von einfachen Zwei-Personen-Anweisungen zerlegen?

Der Autor, Sergiy Koshkin, sagt „Ja, das können wir“, jedoch mit ein paar interessanten Wendungen, je nachdem, wie groß der Raum (die „Domäne“) ist, in dem die Maschine arbeitet.

Hier ist die Aufschlüsselung des Papers unter Verwendung alltäglicher Analogien:

1. Die große Idee: Komplexität abbauen

Denken Sie an eine komplexe Beziehung (wie „A ist der Bruder von B, welcher der Elternteil von C ist“) als einen großen, verknoteten Knoten. In diesem Paper geht es darum, diesen Knoten in kleinere, einfachere Schleifen zu entwirren.

In der Mathematik und Informatik haben wir es oft mit „Relationen“ (Regeln, die Dinge verbinden) zu tun.

Unär: Eine Sache (z. B. „Ist rot“).
Binär: Zwei Dinge (z. B. „Ist größer als“).
Ternär: Drei Dinge (z. B. „Liegt zwischen“).
n-är: Viele Dinge.

Das Ziel ist es, eine Regel, die 5 Personen benötigt, um verstanden zu werden, in eine Kette von Regeln zu zerlegen, die tatsächlich nur 2 oder 3 Personen benötigen.

2. Die unendliche Welt vs. Die endliche Welt

Das Paper unterscheidet zwischen zwei Arten von Welten:

Die unendliche Welt: Stellen Sie sich einen Raum mit unendlich vielen Menschen vor. Hier können Sie einen Zaubertrick namens „Hypostatischer Abstraktion“ anwenden. Es ist so, als würde man einen komplexen 5-Personen-Tanz nehmen und sagen: „Lass uns diese ganze Gruppe einfach als eine neue Person betrachten.“ Sie können sofort jede komplexe Regel in eine einfache Zwei-Personen-Regel verwandeln. Es ist einfach, aber es erfordert einen unendlichen Vorrat an „neuen Menschen“, die als Platzhalter fungieren.
Die endliche Welt: Dies ist unsere reale Welt, in der die Anzahl der Menschen begrenzt ist. Sie können nicht einfach neue Menschen erfinden, die Ihnen helfen. Hier leistet das Paper die eigentliche Schwerstarbeit. Der Autor zeigt, dass man selbst in einem kleinen, überfüllten Raum komplexe Regeln immer noch aufbrechen kann, aber man braucht eine spezifische, clevere Konstruktion.

3. Der Haupttrick: Regeln in „Funktionen“ umwandeln

Die Geheimwaffe des Autors ist das Konzept der „Verwandten“ (Relatives).
Normalerweise ist eine „Funktion“ wie ein Verkaufsautomat: Sie werfen eine Münze hinein (Input) und erhalten einen Snack (Output). Es ist eine Einbahnstraße.
Eine „Relation“ ist eher wie ein Gruppenchat: Alle sind miteinander verbunden, aber niemand ist strikt der „Chef“ oder der „Output“.

Die Analogie:
Stellen Sie sich vor, Sie haben einen Gruppenchat, in dem alle miteinander schreiben. Um dies zu vereinfachen, sagt der Autor: „Lassen Sie uns so tun, als wäre eine Person im Chat der ‚Chef‘ (der Output) und alle anderen schicken ihm lediglich Nachrichten.“
Indem man so tut, als wäre die Relation eine „partielle Funktion“ (ein Chef, der manchmal nicht antwortet), kann der Autor die bekannten mathematischen Tricks zur Zerlegung von Funktionen anwenden.

Der Prozess:

Identifizieren Sie den Chef: Wählen Sie eine Variable in Ihrer komplexen Regel, die der „Output“ sein soll.
Der Selektor: Wenn die Regel mehrere mögliche Ausgaben zulässt (wie ein Chef, der entweder eine Textnachricht oder eine E-Mail senden könnte), verwendet der Autor einen „Selektor“, um einen spezifischen Pfad auszuwählen.
Die Kette: Sob'n Sie eine Funktion haben, können Sie diese aufteilen. Genau wie man eine komplexe Maschine aus einfachen Zahnrädern bauen kann, kann man jede komplexe Funktion aus einfachen 2-Eingangs-Zahnrädern (Funktionen, die zwei Dinge nehmen und daraus eines machen) aufbauen.
Das Ergebnis: Dies beweist, dass jede komplexe Regel in ternäre Relationen (Regeln, die 3 Dinge involvieren) zerlegt werden kann. Denken Sie an dies als eine „Mittelsmann“-Regel: Wenn A etwas mit B macht und B etwas mit C macht, dann ist A mit C verbunden.

4. Der letzte Schritt: Von 3 Personen zu 2 Personen

Das Paper geht noch einen Schritt weiter. Kann man diese 3-Personen-Regeln in 2-Personen-Regeln zerlegen?

Auf großen endlichen Domänen (3+ Personen): Ja! Der Autor nutzt einen cleveren Trick namens „Existenzialisierung von Disjunktionen“.
- Die Metapher: Stellen Sie sich vor, Sie haben eine Regel, die besagt: „Sie dürfen eintreten, wenn Sie einen Hut ODER einen Schal ODER Handschuhe tragen.“
- In einem kleinen Raum kann man das „ODER“ nicht einfach in eine einfache Kette umwandeln. Aber der Autor zeigt, dass man – wenn man genug Leute hat (mindestens 3) – dieses „ODER“-Listen-Konzept in eine „Wer hält das Ticket?“-Frage verwandeln kann. Man führt eine temporäre Variable ein (den „Tickethalter“) und fragt: „Gibt es eine Person, die ein Ticket hält, die die Regel wahr macht?“
- Dies wandelt die komplexe „ODER“-Logik in eine einfache „Es existiert“-Logik um, was es ermöglicht, die 3-Personen-Regel vollständig aus 2-Personen-Regeln aufzubauen.
Auf kleinen endlichen Domänen (Boolean/2 Personen): Nein.
- Wenn Sie nur zwei Personen haben (wie Wahr/Falsch oder 0/1), stoßen Sie an eine Grenze. Es gibt einige 3-Personen-Regeln, die schlichtweg nicht in 2-Personen-Regeln zerlegt werden können.
- Die Metapher: Es ist wie der Versuch, eine bestimmte 3D-Form nur mit 2D-Flachstücken zu bauen. Manche Formen lassen sich einfach nicht passend zusammensetzen. Das Paper beweist, dass auf einer 2-Personen-Welt bestimmte komplexe Beziehungen „irreduzibel“ sind – sie sind die atomaren Bausteine, die nicht weiter vereinfacht werden können.

5. Die „Sheffer“-Überrasung

Das Paper entdeckt auch etwas Faszinierendes: Genau wie es in der Logik einen einzigen „magischen Schalter“ (den Sheffer-Strich) gibt, der jedes andere Logikgatter aufbauen kann, gibt es eine einzige „Sheffer-Relation“ (eine spezifische 3-Personen-Regel), die jede andere Beziehung auf einer endlichen Domäne aufbauen kann.

Es ist, als würde man einen ganz bestimmten Lego-Stein finden, mit dem man – wenn man genug davon hat – jedes Schloss, jedes Auto oder jedes Raumschiff bauen kann.

Zusammenfassung des „Kernpunkts“

Komplexität ist beherrschbar: Sie können fast jede komplizierte Regel, die viele Variablen beinhaltet, in einfache Regeln mit nur 2 oder 3 Variablen zerlegen.
Der „Mittelsmann“ ist ternär: Der effizienteste Weg, Dinge aufzubrechen, endet meist bei 3 Variablen (ternär).
Die Größe zählt: Wenn Ihre Welt groß genug ist (3 oder mehr Elemente), können Sie alles auf 2 Variablen herunterbrechen. Wenn Ihre Welt winzig ist (nur 2 Elemente), sind einige 3-Variablen-Regeln „feststeckend“ und können nicht vereinfacht werden.
Funktionen helfen Relationen: Indem man so tut, als wären Relationen wie Funktionen (mit einem Chef und Arbeitern), kann man die mathematischen Werkzeuge für Funktionen nutzen, um Relationsprobleme zu lösen.

Das Paper liefert im Wesentlichen eine neue, einfachere „Bedienungsanleitung“ dafür, wie man komplexe Datenbeziehungen dekonstruiert, und beweist, dass man selbst in einer begrenzten Welt alles aus einfachen Zwei-Personen-Interaktionen aufbauen kann, sofern man ein paar spezifische „Hilfsregeln“ besitzt.

Technische Zusammenfassung: Funktionale Vollständigkeit und primitive positive Dekomposition von Relationen auf endlichen Domänen

Problemstellung
Die Arbeit adressiert das Problem der Dekomposition höherdimensionaler Relationen in Relationen niedrigerer Arität, spezifisch binärer Relationen, unter Verwendung primitiv-positiver Formeln (ppf). Eine primitiv-positive Formel besteht aus Konjunktionen und Existenzquantoren angewandt auf Prädikate. Dieses Problem, bekannt als die Relationale Reduktionsthese (RRT), postuliert, dass $n$ -äre Relationen ( $n \ge 2$ ) auf binäre Relationen reduzierbar sind, wobei jedoch nicht alle binären Relationen auf unäre reduzierbar sind.

Während das funktionale Analogon (Funktionale Reduktionsthese, FRT) – dass $n$ -eingangige Funktionen auf 2-eingangige Funktionen reduzierbar sind – durch Posts Arbeit über die mehrwertige Logik und Sheffer-Funktionen gut etabliert ist, war der relationale Fall auf endlichen Domänen weniger eindeutig. Frühere Ergebnisse waren verstreut, oft nicht konstruktiv oder stützten sich auf die Erweiterung der Domäne (hypostatische Abstraktion), was auf endlichen Domänen ohne Hinzufügen von Elementen nicht realisierbar ist. Zudem ist bekannt, dass die RRT auf booleschen Domänen versagt (wo irreduzible ternäre Relationen existieren), doch die strukturellen Gründe für dieses Versagen und die Bedingungen für den Erfolg auf allgemeinen endlichen Domänen erforderten eine einheitliche, elementare Erklärung.

Methodik
Der Autor verwendet einen konstruktiven Ansatz, der die funktionale Vollständigkeit und die relationale Dekomposition über die Interpretation von Relationen als „mehrwertige partiell definierte Funktionen“ (Relative) überbrückt. Die Methodik verläuft in drei Stufen:

Relative Reduktion (Relationen zu ternär):
Die Arbeit behandelt eine $n$ -äre Relation $R$ als ein Relativ mit einem ausgezeichneten Output-Argument. Sie dekomponiert $R$ in eine Multifunktion und eine Domänenrelation. Durch die Nutzung von Werteselektoren (Funktionen, die einen Wert aus dem Bild der Multifunktion wählen) dekomponiert der Autor die Multifunktion zu einer gewöhnlichen Funktion $f(t, x_1, \dots, x_{n-1})$ . Unter Ausnutzung der bekannten funktionalen Reduktion von $n$ -eingangigen Funktionen auf 2-eingangige Funktionen (via Posts kanonischer disjunktiver Normalformen in mehrwertigen Logiken) zeigt die Arbeit, dass jede Relation in ternäre Relationen (Graphen von 2-eingangigen Funktionen) und Relationen niedrigerer Arität dekomponiert werden kann.
Existenzialisierung von Disjunktionen (Ternär zu binär):
Um ternäre Relationen auf binäre zu reduzieren, führt die Arbeit eine Konstruktion für kofinite Relationen (Relationen, deren Komplemente endlich sind) ein. Diese Methode ist dual zur hypostatischen Abstraktion. Anstatt Tupel in neue Elemente zu kodieren, konvertiert sie die in der komplementären konjunktiven Normalform (CCNF) einer kofiniten Relation enthaltenen Disjunktionen in Existenzquantifizierungen. Dies wird durch Einführung einer Indexvariable und die Definition spezifischer binärer Prädikate erreicht, die die Disjunktion von unären „Kolateralen“ emulieren. Dieser Schritt ist nur gültig, wenn die Arität $n$ die Größe der Domäne $|D|$ nicht überschreitet, was eine Injektion von Indizes in die Domäne ermöglicht.
Bindungsreduktion und Peirce's These:
Die Arbeit analysiert die Beziehung zwischen primitiv-positiver Komposition und der ursprünglichen „Bindung“ nach Peirce (eingeschränkte Komposition unter Verwendung von Relativprodukten und Variablenidentifikation). Es wird bewiesen, dass für Aritäten $n \ge 4$ die pp-Reduzierbarkeit und die Bindungsreduzierbarkeit äquivalent sind, sofern ternäre „Teridentitäten“ ( $I_3$ ) zugelassen werden. Für ternäre Relationen ist die Bindungsreduzierbarkeit jedoch strikt schwächer als die pp-Reduzierbarkeit.

Wesentliche Beiträge und Ergebnisse

Theorem 2 (Relative Reduktion): Auf jeder Domäne lässt sich jede $n$ -äre Relation als Komposition einer Funktion $f: D^n \to D$ und einer Domänenrelation zerlegen. Entscheidend ist: Wenn ein funktional vollständiges System von 2-eingangigen Funktionen existiert, kann jede Relation in die Graphen von Funktionen aus diesem System dekomponiert werden. Dies impliziert, dass auf jeder endlichen Domäne jede $n$ -äre Relation ( $n \ge 4$ ) auf ternäre Relationen reduzierbar ist.
Korollar 1 (Sheffer-Relationen): Auf jeder endlichen Domäne existieren ternäre Relationen (Graphen von Sheffer-Funktionen), die allein ein primitiv-positives vollständiges System bilden. Dies begründet die Existenz von „Sheffer-Relationen“ für nicht-boolesche Domänen.
Theorem 3 (Binäre Reduktion kofiniter Relationen): Für Domänen mit $|D| \ge 3$ reduziert sich jede kofinite $n$ -äre Relation (wobei $3 \le n \le |D|$ ) auf binäre Relationen. Diese Konstruktion beruht auf der Konvertierung von Disjunktionen von Kolateralen in Existenzquantifizierungen über binäre Prädikate.
Theorem 4 (Irreduzibilität auf booleschen Domänen): Die Arbeit liefert einen elementaren Beweis dafür, dass die ternäre Relation $\neg I_3$ (das Komplement der ternären Identität) auf booleschen Domänen irreduzibel gegenüber binären Relationen ist. Dies wird dadurch gezeigt, dass $\neg I_3$ nicht „bijunktiv“ ist (nicht als 2CNF darstellbar) und da die pp-Komposition die Bijunktivität bewahrt, sie nicht auf binäre Relationen reduziert werden kann (da alle binären Relationen bijunktiv sind).
Theorem 5 & 6 (Bindung vs. pp-Reduzierbarkeit): Die Arbeit klärt, dass für $n \ge 4$ die pp-Reduzierbarkeit äquivalent zur Bindungsreduzierbarkeit (unter Verwendung von Teridentitäten) ist. Für ternäre Relationen ist die Bindungsreduzierbarkeit jedoch strikt schwächer; spezifisch ist $I_3$ auf jeder Domäne mit mindestens zwei Elementen bindungsirreduzibel.

Bedeutung und Ansprüche

Die Arbeit beansprucht, einen „einheitlichen Beweis“ für Peirce's Reduktionsthese auf endlichen Domänen zu liefern, indem sie eine direkte, elementare Verbindung zwischen der funktionalen Reduktionsthese (FRT) und der relationalen Reduktionsthese (RRT) herstellt.

Vereinigung: Sie löst die Diskrepanz zwischen funktionaler und relationaler Vollständigkeit auf, indem sie zeigt, dass die Graphen funktional vollständiger Systeme relationale pp-vollständige Systeme bilden.
Konstruktive Natur: Im Gegensatz zu früheren nicht-konstruktiven Beweisen, die auf Galois-Verbindungen oder Domänenerweiterungen basieren, ist diese Konstruktion rechentechnisch effektiv und stützt sich auf etablierte Methoden der funktionalen Dekomposition (Posts Logiken).
Erklärung des Versagens: Die Konstruktion verdeutlicht, warum die RRT auf booleschen Domänen versagt: die Unfähigkeit, höherwertige Disjunktionen in Existenzquantifizierungen umzuwandeln, aufgrund unzureichender Domänen-Elemente (speziell des Fehlens einer Injektion für Indizes, wenn $n > |D|$ ).
Neue Konzepte: Sie führt das Konzept der „Sheffer-Relationen“ ein und bietet eine neue Perspektive auf die „hypostatische Abstraktion“ als dualen Prozess zur „Existenzialisierung von Disjunktionen“.

Der Autor merkt bescheiden an, dass die Konstruktion zwar die Reduzierbarkeit von Relationen auf ternäre und (für kofinite Fälle) binäre Relationen erklärt, aber kein allgemeines Analogon zu den Kriterien von Post oder Slupecki für relationale Vollständigkeit auf beliebigen endlichen Domänen liefert und auch nicht vollständig die maximalen Coclone charakterisiert. Die Arbeit lässt die Frage offen, ob binäre Sheffer-Relationen auf nicht-booleschen Domänen existieren.