🔢 mathematics

Functional completeness and primitive positive decomposition of relations on finite domains

Dit artikel presenteert een nieuwe, elementaire en computationeel effectieve constructie die relaties met een hogere ariteit op eindige domeinen decomponeert in binaire relaties door gebruik te maken van functionele volledigheid en specifieke disjuncties om te zetten in existentiële kwantificaties, waarmee een uniforme bewijsvoering voor Peirce's reductiethese wordt geleverd en wordt aangetoond dat de graaf van elke Sheffer-functie al deze dergelijke relaties kan componeren.

Oorspronkelijke auteurs: Sergiy Koshkin

Gepubliceerd 2026-06-19

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Sergiy Koshkin

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een gigantische, ingewikkelde handleiding hebt voor een machine. Deze handleiding beschrijft hoe je dingen kunt doen die veel handen tegelijkertijd vereisen (zoals een dansbeweging van 5 personen). De tekst stelt een simpele vraag: Kunnen we deze complexe, meerpersoonsinstructie afbreken tot een reeks eenvoudige instructies voor twee personen?

De auteur, Sergiy Koshkin, zegt: "Ja, dat kunnen we," maar met een paar interessante wendingen afhankelijk van de grootte van de kamer (het "domein") waar de machine opereert.

Hier is de uitsplitsing van het artikel met behulp van alledaagse analogieën:

1. Het Grote Idee: Complexiteit Afbreken

Denk aan een complexe relatie (zoals "A is de broer van B, die de ouder is van C") als een grote, verwarde knoop. Het artikel gaat over het ontwarren van die knoop in kleinere, eenvoudigere lussen.

In de wiskunde en informatica hebben we het vaak over "relaties" (regels die dingen verbinden).

Unair: Eén ding (bijv. "Is rood").
Binair: Twee dingen (bijv. "Is groter dan").
Ternair: Drie dingen (bijv. "Is tussen").
N-air: Veel dingen.

Het doel is om een regel die 5 mensen nodig heeft om begrepen te worden, te nemen en aan te tonen dat deze gebouwd kan worden door het achter elkaar plaatsen van regels die slechts 2 of 3 mensen nodig hebben.

2. De Oneindige Kamer versus De Eindige Kamer

Het artikel maakt onderscheid tussen twee soorten werelden:

De Oneindige Wereld: Stel je een kamer voor met oneindig veel mensen. Hier kun je een trucje doen dat "Hypostatische Abstractie" wordt genoemd. Het is alsof je een complexe dans van 5 personen neemt en zegt: "Laten we doen alsover dat deze hele groep gewoon één nieuwe persoon is." Je kunt direct elke complexe regel veranderen in een eenvoudige regel voor twee personen. Het is makkelijk, maar het vereist een oneindige voorraad "nieuwe mensen" om als plaatsvervangers te dienen.
De Eindige Wereld: Dit is onze echte wereld, waarin het aantal mensen beperkt is. Je kunt niet zomaar nieuwe mensen uitvinden om te helpen. Dit is waar het artikel het zware werk doet. De auteur laat zien dat je zelfs in een kleine, drukke kamer nog steeds complexe regels kunt afbreken, maar dat je daarvoor een specifieke, slimme constructie nodig hebt.

3. De Belangrijkste Truc: Regels Omzetten in "Functies"

Het geheime wapen van de auteur is een concept genaamd "Relatieve".
Normaal gesproken is een "functie" als een verkoopautomaat: je stopt er een muntje in (input) en je krijgt een snack (output). Het is een eenrichtingsweg.
Een "relatie" is meer als een groepschat: iedereen is verbonden, maar niemand is strikt de "baas" of de "output".

De Analogie:
Stel je voor dat je een groepschat hebt waar iedereen praat. Om dit te vereenvoudigen, zegt de auteur: "Laten we doen alsof één persoon in de chat de 'baas' is (de output), en de rest hen alleen maar berichten stuurt."
Door te doen alsof de relatie een "partiële functie" is (een baas die soms niet antwoordt), kan de auteur bekende wiskundige trucs gebruiken voor het afbreken van functies.

Het Proces:

Identificeer de Baas: Kies één variabele in je complexe regel om de "output" te zijn.
De Selector: Als de regel meerdere mogelijke outputs toestaat (zoals een baas die óf een sms óf een e-mail kan sturen), gebruikt de auteur een "selector" om één specifiek pad te kiezen.
De Keten: Zodra je een functie hebt, kun je deze afbreken. Net zoals je een complexe machine kunt bouwen uit eenvoudige tandwielen, kun je elke complexe functie bouwen uit eenvoudige 2-input tandwielen (functies die twee dingen nemen en één ding maken).
Het Resultaat: Dit bewijst dat elke complexe regel kan worden afgebroken in Ternaire relaties (regels waarbij 3 dingen betrokken zijn). Denk hierbij aan een "tussenpersoon"-regel: Als A X doet bij B, en B doet Y bij C, dan is A verbonden met C.

4. De Laatste Stap: Van 3 Personen naar 2 Personen

Het artikel gaat nog een stap verder. Kunnen we die 3-persoonsregels afbreken naar 2-persoonsregels?

Op Grote Eindige Domeinen (3+ personen): Ja! De auteur gebruikt een slimme truc genaamd "Existentiële Disjunctie".
- De Metafoor: Stel je een regel voor die zegt: "Je mag naar binnen als je een Hoed OF een Sjaal OF Handschoenen draagt."
- In een kleine kamer kun je "OF" niet gemakkelijk omzetten in een eenvoudige keten. Maar de auteur laat zien dat als je genoeg mensen hebt (minstens 3), je die "OF"-lijst kunt omzetten in een "Wie houdt het ticket vast?"-vraag. Je introduceert een tijdelijke variabele (de "tickethouder") en vraat: "Is er een persoon die een ticket vasthoudt die de regel waar maakt?"
- Dit zet de complexe "OF"-logica om in een eenvoudige "Bestaan"-logica, waardoor de 3-persoonsregel volledig gebouwd kan worden uit 2-persoonsregels.
Op Kleine Eindige Domeinen (Boolean/2 personen): Nee.
- Als je slechts twee mensen hebt (zoals Waar/Onwaar of 0/1), loop je tegen een muur aan. Er zijn sommige 3-persoonsregels die simpelweg niet afgebroken kunnen worden in 2-persoonsregels.
- De Metafoor: Het is alsof je een specifieke 3D-vorm probeert te bouwen met alleen maar 2D-platte stukken. Sommige vormen zullen simpelweg niet passen. Het artikel bewijst dat op een 2-persoonswereld bepaalde complexe relaties "onherleidbaar" zijn — zij zijn de atomaire bouwstenen die niet verder vereenvoudigd kunnen worden.

5. De "Sheffer" Verrassing

Het artikel ontdekt ook iets cools: net zoals er één "magische schakelaar" (de Sheffer-streep) in de logica is die elke andere logische poort kan bouwen, is er één specifieke "Sheffer-relatie" (een specifieke 3-persoonsregel) die elke andere relatie op een eindig domein kan bouwen.

Het is alsof je één specifieke Lego-steen vindt die, als je er genoeg van hebt, elk kasteel, auto of ruimteschip kan bouwen.

Samenvatting van de "Kernboodschap"

Complexiteit is beheersbaar: Je kunt bijna elke ingewikkelde regel met veel variabelen nemen en deze afbreken in eenvoudige regels met slechts 2 of 3 variabelen.
De "Tussenpersoon" is Ternair: De meest efficiënte manier om dingen af te breken, stopt meestal bij 3 variabelen (Ternair).
Grootte Doet Er Toe: Als je wereld groot genoeg is (3 of meer items), kun je alles afbreken naar 2 variabelen. Als je wereld piepklein is (slechts 2 items), zijn sommige 3-variabele regels "vastgelopen" en kunnen ze niet vereenvoudigd worden.
Functies Helpen Relaties: Door te doen alsof relaties als functies werken (met een baas en werkers), kunnen we wiskundige hulpmiddelen gebruiken om relatieproblemen op te lossen.

Het artikel biedt in essentie een nieuwe, eenvoudigere "instructiehandleiding" voor hoe je complexe datarelaties deconstrueert, en bewijst dat we in een beperkte wereld toch alles kunnen bouwen uit eenvoudige interacties tussen twee personen, mits we een paar specifieke "helper"-regels hebben.

Technische Samenvatting: Functionele Volledigheid en Primitief-Positieve Decompositie van Relaties op Eindige Domeinen

Probleemstelling
Het artikel behandelt het probleem van het decomponeren van relaties met een hogere ariteit naar relaties met een lagere ariteit, specifiek binaire relaties, met behulp van primitief-positieve formules (ppf's). Een primitief-positieve formule bestaat uit conjuncties en existentiële kwantoren toegepast op predicaten. Dit probleem, bekend als de Relationele Reductiethese (RRT), stelt dat $n$ -aire relaties ( $n \ge 2$ ) kunnen worden gereduceerd tot binaire relaties, hoewel niet alle binaire relaties reduceren naar unariële relaties.

Terwijl het functionele analogon (de Functionele Reductiethese, FRT)—dat $n$ -input functies reduceren naar 2-input functies—goed gevestigd is (via het werk van Post op meerwaardige logica en Sheffer-functies), is het relationele geval op eindige domeinen minder duidelijk geweest. Eerdere resultaten waren verspreid, vaak niet-constructief, of vertrouwden op het uitbreiden van het domein (hypostatische abstractie), wat niet haalbaar is op eindige domeinen zonder elementen toe te voegen. Bovendien is bekend dat RRT faalt op Booleaanse domeinen (waar irreducibele ternaire relaties bestaan), maar de structurele redenen voor dit falen en de voorwaarden voor succes op algemene eindige domeinen vereisten een verenigde, elementaire verklaring.

Methodologie
De auteur hanteert een constructieve benadering die functionele volledigheid en relationele decompositie overbrugt door relaties te interpreteren als "meerwaardige gedeeltelijk gedefinieerde functies" (relatieven). De methodologie verloopt in drie stadia:

Relatieve Reductie (Relaties naar Ternair):
Het artikel behandelt een $n$ -aire relatie $R$ als een relatief met een onderscheiden output-argument. Het decomponeert $R$ in een multifunction en een domeinrelatie. Door gebruik te maken van waarde-selectors (functies die een waarde kiezen uit de afbeelding van de multifunction), reduceert de auteur de multifunction tot een gewone functie $f(t, x_1, \dots, x_{n-1})$ . Door gebruik te maken van de bekende functionele reductie van $n$ -input functies naar 2-input functies (via de canonieke disjunctieve normaalvormen van Post in meerwaardige logica), demonstreert het artikel dat elke relatie kan worden gedecomposeerd in ternaire relaties (grafieken van 2-input functies) en relaties met een lagere ariteit.
Existentialisering van Disjuncties (Ternair naar Binair):
Om ternaire relaties te reduceren tot binaire relaties, introduceert het artikel een constructie voor cofiniete relaties (relaties waarvan de complementen eindig zijn). Deze methode is duaal aan hypostatische abstractie. In plaats van tupels te coderen in nieuwe elementen, zet het de disjuncties die inherent zijn aan de Complement Conjunctieve Normaalvorm (CCNF) van een cofiniete relatie om in existentiële kwantificaties. Dit wordt bereikt door een indexeringsvariabele te introduceren en specifieerbare binaire predicaten te definiëren die de disjunctie van unariële "coliteralen" emuleren. Deze stap is alleen geldig wanneer de ariteit $n$ de omvang van het domein $|D|$ niet overschrijdt, waardoor een injectie van indices in het domein mogelijk is.
Band-reductie en Peirce's Thesis:
Het artikel analyseert de relatie tussen primitief-positieve compositie en de oorspronkelijke "bonding" van Peirce (beperkte compositie waarbij relatieve producten en variabele identificatie worden gebruikt). Het bewijst dat voor ariteiten $n \ge 4$ , pp-reduceerbaarheid en band-reduceerbaarheid equivalent zijn, mits ternaire "teridentiteiten" ( $I_3$ ) zijn toegestaan. Echter, voor ternaire relaties is band-reduceerbaarheid strikt zwakker dan pp-reduceerbaarheid.

Kernbijdragen en Resultaten

Theorem 2 (Relatieve Reductie): Op elk domein kan elke $n$ -aire relatie worden gedecomposeerd in een compositie van een functie $f: D^n \to D$ en een domeinrelatie. Cruciaal is dat als er een functioneel volledige verzameling van 2-input functies bestaat, elke relatie kan worden gedecomposeerd in de grafieken van functies uit die verzameling. Dit impliceert dat op elk eindig domein elke $n$ -aire relatie ( $n \ge 4$ ) reduceerbaar is tot ternaire relaties.
Corollary 1 (Sheffer-relaties): Op elk eindig domein bestaan er ternaire relaties (grafieken van Sheffer-functies) die alleen een primitief-positief volledig systeem vormen. Dit vestigt het bestaan van "Sheffer-relaties" voor niet-Booleaanse domeinen.
Theorem 3 (Binaire Reductie van Cofiniete Relaties): Voor domeinen met $|D| \ge 3$ , is elke cofiniete $n$ -aire relatie (waarbij $3 \le n \le |D|$ ) reduceerbaar tot binaire relaties. Deze constructie berust op het omzetten van disjuncties van coliteralen in existentiële kwantificaties over binaire predicaten.
Theorem 4 (Irreducibiliteit op Booleaanse Domeinen): Het artikel biedt een elementair bewijs dat de ternaire relatie $\neg I_3$ (het complement van de ternaire identiteit) irreducibel is tot binaire relaties op Booleaanse domeinen. Dit wordt aangetoond door te laten zien dat $\neg I_3$ niet "bijunctief" is (niet uitgedrukt kan worden als een 2CNF), en aangezien pp-compositie bijunctiviteit behoudt, kan het niet worden gereduceerd tot binaire relaties (die allemaal bijjunctief zijn).
Theorem 5 & 6 (Band vs. pp-Reduceerbaarheid): Het artikel verheldert dat voor $n \ge 4$ , pp-reduceerbaarheid equivalent is aan band-reduceerbaarheid (gebruikmakend van teridentiteiten). Echter, voor ternaire relaties is band-reduceerbaarheid strikt zwakker; specifiek is $I_3$ band-irreducibel op elk domein met minstens twee elementen.

Betekenis en Claims
Het artikel claimt een "uniform bewijs" van Peirce's reductiethese op eindige domeinen te leveren door een directe, elementaire verbinding vast te stellen tussen de functionele reductiethese (FRT) en de relationele reductiethese (RRT).

Unificatie: Het lost de disconnect tussen functionele en relationele volledigheid op door te laten zien dat de grafieken van functioneel volledige systemen relationeel pp-complete systemen vormen.
Constructiviteit: In tegenstelling tot eerdere niet-constructieve bewijzen die steunen op Galois-verbindingen of domeinuitbreidingen, is deze constructie computationeel effectief en steunt het op goed ontwikkelde methoden van functionele decompositie (Post's logica's).
Verklaring van Falen: De constructie verduidelijkt waarom RRT faalt op Booleaanse domeinen: het onvermogen om hogere-orde disjuncties om te zetten in existentiële kwantificaties vanwege onvoldoende domeinelementen (specifiek, het gebrek aan een injectie voor indices wanneer $n > |D|$ ).
Nieuwe Concepten: Het introduceert het concept van "Sheffer-relaties" en biedt een nieuw perspectief op "hypostatische abstractie" als een duaal proces aan de "existentialisering van disjuncties."

De auteur merkt bescheiden op dat hoewel de constructie de reductibiliteit van relaties naar ternaire en (voor cofiniete gevallen) binaire relaties verklaart, het geen algemeen analoog van de Post of Slupecki criteria voor relationele volledigheid op willekeurige eindige domeinen biedt, noch het de maximale coclonen volledig karakteriseert. Het artikel laat de vraag open of er binaire Sheffer-relaties bestaan op niet-Booleaanse domeinen.