pith. sign in

arxiv: 2606.19492 · v1 · pith:M7ZC62EYnew · submitted 2026-06-17 · 🧮 math.LO · cs.LO· math.RA

Functional completeness and primitive positive decomposition of relations on finite domains

Sergiy Koshkin This is my paper

Pith reviewed 2026-06-26 18:17 UTC · model grok-4.3

classification 🧮 math.LO cs.LOmath.RA
keywords primitive positive decompositionfunctional completenessSheffer functionfinite domainsPeirce's reduction thesisconstraint satisfactionrelationsmany-valued logic
0
0 comments X

The pith

The graph of any Sheffer function composes all relations on finite domains via primitive positive decompositions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a method for decomposing any higher-arity relation into binary relations using primitive positive formulas on finite domains. It leverages the functional completeness of two-input functions by representing relations as graphs of partially defined multivalued functions and composing them accordingly. This yields both an effective procedure and the result that any Sheffer function's graph can generate all relations. The approach first handles the reduction to ternary relations before converting to binary via existential quantifiers.

Core claim

The paper claims that there exists an effective primitive positive decomposition of higher-arity relations into binary relations on finite domains. This is achieved by exploiting the functional completeness of 2-input functions in many-valued logic, interpreting relations as graphs of partially defined multivalued functions, and composing them from ordinary functions. An additional step decomposes ternary relations into binary ones by converting disjunctions into existential quantifications. As a result, the graph of any Sheffer function composes all relations on finite domains, providing a uniform proof of Peirce's reduction thesis.

What carries the argument

Functional completeness of 2-input functions in many-valued logic, applied by interpreting relations as graphs of partially defined multivalued functions.

If this is right

  • The decomposition is computationally effective and applies directly to constraint satisfaction problems.
  • It supplies a uniform proof of Peirce's reduction thesis on finite domains.
  • Higher-arity relations reduce first to ternary relations and then to binary relations.
  • All relations on the domain can be obtained from the graph of any single Sheffer function.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The construction may simplify query processing in relational databases by reducing everything to binary constraints.
  • It links clone theory in many-valued logic to the decomposition of arbitrary relations.
  • The method could be implemented and checked on small domains such as size two or three to measure the length of the resulting formulas.

Load-bearing premise

The domain must be finite for the functional completeness of 2-input functions to hold in the required way.

What would settle it

A finite domain together with a higher-arity relation that cannot be expressed by any primitive positive formula built from the graph of a given Sheffer function would falsify the claim.

read the original abstract

We give a new and elementary construction of primitive positive decomposition of higher arity relations into binary relations on finite domains. Such decompositions come up in applications to constraint satisfaction problems, clone theory and relational databases. The construction exploits functional completeness of 2-input functions in many-valued logic by interpreting relations as graphs of partially defined multivalued 'functions'. The 'functions' are then composed from ordinary functions in the usual sense. The construction is computationally effective and relies on well-developed methods of functional decomposition, but reduces relations only to ternary relations. An additional construction then decomposes ternary into binary relations, also effectively, by converting certain disjunctions into existential quantifications. The result gives a uniform proof of Peirce's reduction thesis on finite domains, and shows that the graph of any Sheffer function composes all relations there.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript presents a new elementary construction for primitive positive decompositions of higher-arity relations into binary relations on finite domains. It interprets relations as graphs of partially defined multivalued functions, exploits functional completeness of 2-input functions to reduce arbitrary-arity relations to ternary ones via composition of ordinary functions, and then reduces ternary relations to binary ones by rewriting selected disjunctions as existential quantifiers. The result is claimed to be effective, to give a uniform proof of Peirce's reduction thesis on finite domains, and to show that the graph of any Sheffer function composes all relations there.

Significance. If the construction holds, the result is significant for constraint satisfaction problems, clone theory, and relational databases by supplying an effective, uniform method on finite domains. The explicit use of functional completeness and the reduction via multivalued-function graphs constitute a genuine contribution; the effectiveness of both steps and the uniform proof of the reduction thesis are strengths that should be credited.

minor comments (2)
  1. [Abstract / Introduction] The abstract and introduction would benefit from a short worked example (e.g., a concrete 4-ary relation reduced first to ternary and then to binary) to illustrate the two-stage construction.
  2. [Section 2 (presumed)] Notation for partially defined multivalued functions and their graphs should be introduced with a dedicated paragraph or diagram early in the paper to avoid ambiguity when the composition is defined.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment, accurate summary of the contributions, and recommendation of minor revision. The report correctly identifies the use of functional completeness, the effective construction via multivalued-function graphs, and the uniform proof of Peirce's thesis as strengths.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents an explicit, effective construction that first reduces higher-arity relations to ternary ones by composing graphs of partial multivalued functions using the externally known functional completeness of 2-input functions on finite domains, then reduces ternary to binary by rewriting disjunctions as existential quantifiers. This relies on standard results in many-valued logic and clone theory rather than any self-definition, fitted parameters renamed as predictions, or load-bearing self-citations. The finiteness assumption is stated upfront and required for the invoked completeness theorems, which are treated as independent external facts. The derivation is therefore self-contained against external benchmarks with no reduction of the central claim to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the known property of functional completeness for binary functions on finite domains in many-valued logic; no new free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Functional completeness of 2-input functions in many-valued logic on finite domains
    Invoked to allow composition of the interpreted multivalued functions from ordinary functions (abstract, paragraph 2).

pith-pipeline@v0.9.1-grok · 5664 in / 1214 out tokens · 26897 ms · 2026-06-26T18:17:22.418336+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 1 canonical work pages

  1. [1]

    Anellis, The genesis of the truth-table device, Russell: the Journal of the Russell Archives, 24 (2004) 55-70

    I. Anellis, The genesis of the truth-table device, Russell: the Journal of the Russell Archives, 24 (2004) 55-70

    2004

  2. [2]

    Barto, Z

    L. Barto, Z. Brady, A. Bulatov, M. Kozik, D. Zhuk, Minimal Taylor algebras as a common framework for the three algebraic approaches to the CSP, inProcceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), IEEE Press, Piscataway, NJ, 2021, 13 pp

    2021

  3. [3]

    Bodnarchuk, L

    V. Bodnarchuk, L. Kaluzhnin, V. Kotov, B. Romov, Galois theory for Post algebras I, II, Cyber- netics, 5 (1969) 243-252 and 531-539

    1969

  4. [4]

    B¨ ohler, S

    E. B¨ ohler, S. Reith, H. Schnoor, H. Vollmer, Bases for Boolean coclones, Information Processing Letters, 96 (2005) no. 2, 59-66

    2005

  5. [5]

    B¨ orner, Basics of Galois connections, inComplexity of Constraints, Lecture Notes in Computer Science, v

    F. B¨ orner, Basics of Galois connections, inComplexity of Constraints, Lecture Notes in Computer Science, v. 5250, Springer, Berlin, 2008, 38-67

    2008

  6. [6]

    Brunning, C

    J. Brunning, C. S. Peirce’s relative product, Modern Logic, 2 (1991) no. 1, 33-49

    1991

  7. [7]

    Bulatov, P

    A. Bulatov, P. Jeavons, A. Krokhin, Classifying the complexity of constraints using finite algebras, SIAM Journal on Computing, 34 (2005), no.3, 720-742

    2005

  8. [8]

    Burch,A Peircean Reduction Thesis: The Foundations of Topological Logic, Texas Tech Uni- versity Press, Lubbock, TX, 1991

    R. Burch,A Peircean Reduction Thesis: The Foundations of Topological Logic, Texas Tech Uni- versity Press, Lubbock, TX, 1991

    1991

  9. [9]

    Burch, Peirce’s reduction thesis, inStudies in the Logic of Charles Sanders Peirce, ch

    R. Burch, Peirce’s reduction thesis, inStudies in the Logic of Charles Sanders Peirce, ch. 16, Indiana University Press, 1997, 234-252

    1997

  10. [10]

    Creignou, H

    N. Creignou, H. Vollmer, Boolean constraint satisfaction problems: when does Post’s lattice help? inComplexity of Constraints, Lecture Notes in Computer Science, vol. 5250, 2008, Springer, Berlin, 3-37

    2008

  11. [11]

    Hereth, R

    J. Hereth, R. P¨ oschel, The power of Peircean Algebraic Logic (PAL), inConcept Lattices, Second International Conference on Formal Concept Analysis, Springer, Berlin, 2004, 337-351

    2004

  12. [12]

    Herzberger, Peirce’s remarkable theorem, inPragmatism and Purpose: Essays Presented to Thomas A

    H. Herzberger, Peirce’s remarkable theorem, inPragmatism and Purpose: Essays Presented to Thomas A. Goudge, University of Toronto Press, 1981, 41-58

    1981

  13. [13]

    Jech,The axiom of choice, Elsevier, New York, 1973

    T. Jech,The axiom of choice, Elsevier, New York, 1973. 18

    1973

  14. [14]

    Jeavons, D

    P. Jeavons, D. Cohen, M. Gyssens, Closure properties of constraints, Journal of the ACM, 44(4) (1997) 527-548

    1997

  15. [15]

    Koshkin, Is Peirce’s reduction thesis gerrymandered? Transactions of the Charles S

    S. Koshkin, Is Peirce’s reduction thesis gerrymandered? Transactions of the Charles S. Peirce Society, 58 (2022) no. 4, 271-300

    2022

  16. [16]

    Koshkin, Logical reduction of relations: from relational databases to Peirce’s reduction thesis, Logic Journal of the IGPL, 31 (2023) no

    S. Koshkin, Logical reduction of relations: from relational databases to Peirce’s reduction thesis, Logic Journal of the IGPL, 31 (2023) no. 4, doi: 10.1093/jigpal/jzad010

    work page doi:10.1093/jigpal/jzad010 2023

  17. [17]

    Lagerkvist, M

    V. Lagerkvist, M. Wahlstr¨ om, The power of primitive positive definitions with polynomially many variables, Journal of Logic and Computation, 27 (2017) no. 5, 1465-1488

    2017

  18. [18]

    Lau, Function algebras on finite sets, Springer-Verlag, Berlin, 2006

    D. Lau, Function algebras on finite sets, Springer-Verlag, Berlin, 2006

    2006

  19. [19]

    Lewis, A survey of symbolic logic, University of California Press, Berkeley, 1918

    C.I. Lewis, A survey of symbolic logic, University of California Press, Berkeley, 1918

    1918

  20. [20]

    L¨ owenheim,¨Uber M¨ oglichkeiten im Relativkalk¨ ul(German), Mathematische Annalen 76 (1915) 447-470

    L. L¨ owenheim,¨Uber M¨ oglichkeiten im Relativkalk¨ ul(German), Mathematische Annalen 76 (1915) 447-470. English translation: On possibilities in the calculus of relatives, inFrom Frege to G¨ odel: a source book in mathematical logic 1879-1931, Harvard University Press, Cambridge, MS, 1967, 228-251

    1915

  21. [21]

    Marchenkov, The invariants of Post classes, Fundamental’naya i Prikladnaya Matematika, 4 (1998) no

    S. Marchenkov, The invariants of Post classes, Fundamental’naya i Prikladnaya Matematika, 4 (1998) no. 4, 1385-1404

    1998

  22. [22]

    P¨ oschel, L

    D. P¨ oschel, L. Kalu˘ znin,Funktionen- und Relationenalgebren, Mathematische Monographien 15, Deutscher Verlag der Wissenschaften, Berlin, 1979

    1979

  23. [23]

    Robinson, Recent developments in model theory, inProceedings of the 1960 International Congress on Logic, Methodology and Philosophy of Science, Stanford, CA, 1962, pp

    A. Robinson, Recent developments in model theory, inProceedings of the 1960 International Congress on Logic, Methodology and Philosophy of Science, Stanford, CA, 1962, pp. 60-79

    1960

  24. [24]

    Romov, Partial hyperclones on a finite set, inProceedings of 32nd IEEE International Sym- posium on Multiple-Valued Logic, Boston, 2002, 17-22

    B. Romov, Partial hyperclones on a finite set, inProceedings of 32nd IEEE International Sym- posium on Multiple-Valued Logic, Boston, 2002, 17-22

    2002

  25. [25]

    Rosenberg, Some algebraic and combinatorial aspects of multiple-valued circuits, inProceedings of 6th IEEE International Symposium on Multiple-Valued Logic, Logan, UT, 1976, 9-23

    I. Rosenberg, Some algebraic and combinatorial aspects of multiple-valued circuits, inProceedings of 6th IEEE International Symposium on Multiple-Valued Logic, Logan, UT, 1976, 9-23

    1976

  26. [26]

    Rosenberg, Completeness properties of multiple-valued logic algebras, inComputer Science and Multiple-Valued Logic, ch

    I. Rosenberg, Completeness properties of multiple-valued logic algebras, inComputer Science and Multiple-Valued Logic, ch. 6, Elsevier, Amsterdam, 1977, 144-186

    1977

  27. [27]

    Rosenberg, Minimal clones I: the five types, Colloquia Mathematica Societatis J’anos Bolyai, 43 (1986) 405-427

    I. Rosenberg, Minimal clones I: the five types, Colloquia Mathematica Societatis J’anos Bolyai, 43 (1986) 405-427

    1986

  28. [28]

    Rosenberg, An algebraic approach to hyperalgebras, inProceedings of 26th IEEE International Symposium on Multiple-Valued Logic, Santiago de Compostela, Spain, 1996, 203-207

    I. Rosenberg, An algebraic approach to hyperalgebras, inProceedings of 26th IEEE International Symposium on Multiple-Valued Logic, Santiago de Compostela, Spain, 1996, 203-207

    1996

  29. [29]

    Sierpi´ nski,Sur les fonctions de plusieurs variables, Fundamenta Mathematicae, 33 (1945) 169-173

    W. Sierpi´ nski,Sur les fonctions de plusieurs variables, Fundamenta Mathematicae, 33 (1945) 169-173

    1945

  30. [30]

    Schaefer, The complexity of satisfiability problems, inConference Record of the 10th Annual ACM Symposium on Theory of Computing, San Diego, 1978, 216-226

    T. Schaefer, The complexity of satisfiability problems, inConference Record of the 10th Annual ACM Symposium on Theory of Computing, San Diego, 1978, 216-226

    1978

  31. [31]

    Urquhart, Basic many-valued logic, inHandbook of philosophical logic, vol

    A. Urquhart, Basic many-valued logic, inHandbook of philosophical logic, vol. 2, Kluwer, Dor- drecht, 2001, 249-295

    2001

  32. [32]

    Urquhart, Emil Post, inHandbook of the history of logic, vol

    A. Urquhart, Emil Post, inHandbook of the history of logic, vol. 5, Logic from Russell to Church, Elsevier, Amsterdam, 2009, 430-478

    2009

  33. [33]

    Zusmanovich, On the last question of Stefan Banach, Expositiones Mathematicae, 34 (2016), no

    P. Zusmanovich, On the last question of Stefan Banach, Expositiones Mathematicae, 34 (2016), no. 4, 454-466. 19

    2016