🔢 mathematics

Functional completeness and primitive positive decomposition of relations on finite domains

This paper presents a new, elementary, and computationally effective construction that decomposes higher-arity relations on finite domains into binary relations by leveraging functional completeness and converting specific disjunctions into existential quantifications, thereby providing a uniform proof of Peirce's reduction thesis and demonstrating that the graph of any Sheffer function can compose all such relations.

Original authors: Sergiy Koshkin

Published 2026-06-19

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Sergiy Koshkin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, complicated instruction manual for a machine. This manual describes how to do things that require many hands working together at once (like a 5-person dance move). The paper asks a simple question: Can we break this complex, multi-person instruction down into a series of simple, two-person instructions?

The author, Sergiy Koshkin, says "Yes, we can," but with a few interesting twists depending on the size of the room (the "domain") where the machine operates.

Here is the breakdown of the paper using everyday analogies:

1. The Big Idea: Breaking Down Complexity

Think of a complex relationship (like "A is the brother of B, who is the parent of C") as a big, tangled knot. The paper is about untying that knot into smaller, simpler loops.

In math and computer science, we often deal with "relations" (rules connecting things).

Unary: One thing (e.g., "Is red").
Binary: Two things (e.g., "Is taller than").
Ternary: Three things (e.g., "Is between").
N-ary: Many things.

The goal is to take a rule that needs 5 people to understand and show that it can actually be built by chaining together rules that only need 2 or 3 people.

2. The Infinite Room vs. The Finite Room

The paper distinguishes between two types of worlds:

The Infinite World: Imagine a room with infinite people. Here, you can do a magic trick called "Hypostatic Abstraction." It's like taking a complex 5-person dance and saying, "Let's pretend this whole group is just one new person." You can instantly turn any complex rule into a simple two-person rule. It's easy, but it requires an infinite supply of "new people" to act as placeholders.
The Finite World: This is our real world, where the number of people is limited. You can't just invent new people to help you. This is where the paper does its heavy lifting. The author shows that even in a small, crowded room, you can still break down complex rules, but you need a specific, clever construction.

3. The Main Trick: Turning Rules into "Functions"

The author's secret weapon is a concept called "Relatives."
Usually, a "function" is like a vending machine: You put in a coin (input), and you get a snack (output). It's a one-way street.
A "relation" is more like a group chat: Everyone is connected, but no one is strictly the "boss" or the "output."

The Analogy:
Imagine you have a group chat where everyone is talking. To simplify this, the author says: "Let's pretend one person in the chat is the 'boss' (the output), and everyone else is just sending them messages."
By pretending the relation is a "partial function" (a boss who sometimes doesn't reply), the author can use well-known math tricks for breaking down functions.

The Process:

Identify the Boss: Pick one variable in your complex rule to be the "output."
The Selector: If the rule allows for multiple possible outputs (like a boss who might send either a text or an email), the author uses a "selector" to pick one specific path.
The Chain: Once you have a function, you can break it down. Just like you can build a complex machine out of simple gears, you can build any complex function out of simple 2-input gears (functions that take two things and make one).
The Result: This proves that any complex rule can be broken down into Ternary relations (rules involving 3 things). Think of this as a "middleman" rule: If A does X to B, and B does Y to C, then A is connected to C.

4. The Final Step: From 3 People to 2 People

The paper goes one step further. Can we break those 3-person rules down into 2-person rules?

On Large Finite Domains (3+ people): Yes! The author uses a clever trick called "Existentialization of Disjunctions."
- The Metaphor: Imagine you have a rule that says, "You can enter if you are wearing a Hat OR a Scarf OR Gloves."
- In a small room, you can't easily turn "OR" into a simple chain. But the author shows that if you have enough people (at least 3), you can turn that "OR" list into a "Who is holding the ticket?" question. You introduce a temporary variable (a "ticket holder") and ask, "Is there a person holding a ticket who makes the rule true?"
- This converts the complex "OR" logic into a simple "Exists" logic, allowing the 3-person rule to be built entirely from 2-person rules.
On Small Finite Domains (Boolean/2 people): No.
- If you only have two people (like True/False or 0/1), you hit a wall. There are some 3-person rules that simply cannot be broken down into 2-person rules.
- The Metaphor: It's like trying to build a specific 3D shape using only 2D flat pieces. Some shapes just won't fit. The paper proves that on a 2-person world, certain complex relationships are "irreducible"—they are the atomic building blocks that cannot be simplified further.

5. The "Sheffer" Surprise

The paper also discovers something cool: Just as there is a single "magic switch" (the Sheffer stroke) in logic that can build any other logic gate, there is a single "Sheffer Relation" (a specific 3-person rule) that can build any other relationship on a finite domain.

It's like finding one specific Lego brick that, if you have enough of them, can build any castle, car, or spaceship.

Summary of the "Takeaway"

Complexity is manageable: You can take almost any complicated rule involving many variables and break it down into simple rules involving just 2 or 3 variables.
The "Middleman" is Ternary: The most efficient way to break things down usually stops at 3 variables (Ternary).
Size Matters: If your world is big enough (3 or more items), you can break everything down to 2 variables. If your world is tiny (only 2 items), some 3-variable rules are stuck and cannot be simplified.
Functions help Relations: By pretending relationships are like functions (with a boss and workers), we can use existing math tools to solve relationship problems.

The paper essentially provides a new, simpler "instruction manual" for how to deconstruct complex data relationships, proving that even in a limited world, we can build anything out of simple two-person interactions, provided we have a few specific "helper" rules.

Technical Summary: Functional Completeness and Primitive Positive Decomposition of Relations on Finite Domains

Problem Statement
The paper addresses the problem of decomposing higher-arity relations into relations of lower arity, specifically binary relations, using primitive positive formulas (ppfs). A primitive positive formula consists of conjunctions and existential quantifiers applied to predicates. This problem, known as the Relational Reduction Thesis (RRT), posits that $n$ -ary relations ( $n \ge 2$ ) can be reduced to binary relations, though not all binary relations reduce to unary ones.

While the functional analog (Functional Reduction Thesis, FRT)—that $n$ -input functions reduce to 2-input functions—is well-established (via Post's work on many-valued logic and Sheffer functions), the relational case on finite domains has been less clear. Previous results were scattered, often non-constructive, or relied on extending the domain (hypostatic abstraction), which is not feasible on finite domains without adding elements. Furthermore, it is known that RRT fails on Boolean domains (where irreducible ternary relations exist), but the structural reasons for this failure and the conditions for success on general finite domains required a unified, elementary explanation.

Methodology
The author employs a constructive approach that bridges functional completeness and relational decomposition by interpreting relations as "multivalued partially defined functions" (relatives). The methodology proceeds in three main stages:

Relative Reduction (Relations to Ternary):
The paper treats an $n$ -ary relation $R$ as a relative with a distinguished output argument. It decomposes $R$ into a multifunction and a domain relation. By utilizing value selectors (functions that pick a value from the image of the multifunction), the author reduces the multifunction to an ordinary function $f(t, x_1, \dots, x_{n-1})$ . Leveraging the known functional reduction of $n$ -input functions to 2-input functions (via Post's canonical disjunctive normal forms in many-valued logics), the paper demonstrates that any relation can be decomposed into ternary relations (graphs of 2-input functions) and lower-arity relations.
Existentialization of Disjunctions (Ternary to Binary):
To reduce ternary relations to binary ones, the paper introduces a construction for cofinite relations (relations whose complements are finite). This method is dual to hypostatic abstraction. Instead of encoding tuples into new elements, it converts the disjunctions inherent in the Complement Conjunctive Normal Form (CCNF) of a cofinite relation into existential quantifications. This is achieved by introducing an indexing variable and defining specific binary predicates that emulate the disjunction of unary "coliterals." This step is valid only when the arity $n$ does not exceed the domain size $|D|$ , allowing for an injection of indices into the domain.
Bond Reduction and Peirce's Thesis:
The paper analyzes the relationship between primitive positive composition and Peirce's original "bonding" (restricted composition involving relative products and variable identification). It proves that for arities $n \ge 4$ , pp-reducibility and bond reducibility are equivalent, provided ternary "teridentities" ( $I_3$ ) are allowed. However, for ternary relations, bond reducibility is strictly weaker than pp-reducibility.

Key Contributions and Results

Theorem 2 (Relative Reduction): On any domain, any $n$ -ary relation decomposes into a composition of a function $f: D^n \to D$ and a domain relation. Crucially, if a functionally complete set of 2-input functions exists, every relation can be decomposed into the graphs of functions from that set. This implies that on any finite domain, every $n$ -ary relation ( $n \ge 4$ ) is reducible to ternary relations.
Corollary 1 (Sheffer Relations): On any finite domain, there exist ternary relations (graphs of Sheffer functions) that alone form a primitive positive complete system. This establishes the existence of "Sheffer relations" for non-Boolean domains.
Theorem 3 (Binary Reduction of Cofinite Relations): For domains with $|D| \ge 3$ , any cofinite $n$ -ary relation (where $3 \le n \le |D|$ ) reduces to binary relations. This construction relies on converting disjunctions of coliterals into existential quantifications over binary predicates.
Theorem 4 (Irreducibility on Boolean Domains): The paper provides an elementary proof that the ternary relation $\neg I_3$ (the complement of the ternary identity) is irreducible to binary relations on Boolean domains. This is demonstrated by showing $\neg I_3$ is not "bijunctive" (cannot be expressed as a 2CNF), and since pp-composition preserves bijunctivity, it cannot be reduced to binary relations (which are all bijunctive).
Theorem 5 & 6 (Bond vs. pp-Reducibility): The paper clarifies that for $n \ge 4$ , pp-reducibility is equivalent to bond reducibility (using teridentities). However, for ternary relations, bond reducibility is strictly weaker; specifically, $I_3$ is bond irreducible on any domain with at least two elements.

Significance and Claims
The paper claims to provide a "uniform proof" of Peirce's reduction thesis on finite domains by establishing a direct, elementary connection between the functional reduction thesis (FRT) and the relational reduction thesis (RRT).

Unification: It resolves the disconnect between functional and relational completeness by showing that the graphs of functionally complete systems form relationally pp-complete systems.
Constructiveness: Unlike previous non-constructive proofs relying on Galois connections or domain extensions, this construction is computationally effective and relies on well-developed methods of functional decomposition (Post's logics).
Explanation of Failure: The construction elucidates why RRT fails on Boolean domains: the inability to convert higher-order disjunctions into existential quantifications due to insufficient domain elements (specifically, the lack of an injection for indices when $n > |D|$ ).
New Concepts: It introduces the concept of "Sheffer relations" and provides a new perspective on "hypostatic abstraction" as a dual process to the "existentialization of disjunctions."

The author notes modestly that while the construction explains the reducibility of relations to ternary and (for cofinite cases) binary relations, it does not provide a general analog of Post's or Slupecki's criteria for relational completeness on arbitrary finite domains, nor does it fully characterize maximal coclones. The paper leaves open the question of whether binary Sheffer relations exist on non-Boolean domains.