The Setting
Diophantine representations of complicated relations are assembled from representations of simpler ones: two relations are intersected or joined, a variable is eliminated by an existential quantifier, a function is substituted into a relation. For a single-fold representation each of these steps has to keep the auxiliary tuple unique, and two of them can break it. A tuple lying in both relations of a union gets an auxiliary tuple from each side; eliminating a variable from a relation makes every with part of a separate auxiliary tuple for the tuple . The question is which steps keep single-fold representations single-fold, and under which hypotheses.
Single-fold Representations
Here . For a set , a tuple indexed by is an element of , and a relation on is a subset of ; for these are the tuples in and the relations on them. A tuple indexed by a disjoint union is written , with and .
A single-fold representation of a relation is a polynomial with integer coefficients in the variables and finitely many auxiliary variables such that for every (1)✦ We write for the set of single-fold representations of . A relation is single-fold, written , when is nonempty.✦
A map is single-fold when its graph (2)✦ is in .
The projection of a relation and the pullback of a relation along a map are the relations on (3)
The Claim
Theorem 1. Let and be sets and and finite sets.
Let be relations. There is a map (4)✦ and if and are single-fold, then (5)✦
Let , for , be single-fold relations. Then (6)✦
Let be disjoint relations. There is a map (7)✦ and if and are single-fold, then (8)✦
Let be a relation such that for every there is at most one with . There is a map (9)✦ and if is single-fold, then (10)✦
Let and be single-fold maps. Then (11)✦ and for every single-fold relation (12)✦
In the paper, the result reads: finite conjunctions of single-fold systems, with separate auxiliary tuples for distinct calls, preserve uniqueness for fixed values of all displayed arguments; composition of single-fold graphs preserves uniqueness of outputs and of complete auxiliary tuples; and a finite union of single-fold relations has a single-fold system when their displayed argument sets are pairwise disjoint.
What Is Checked
The claim is stated over single-fold representations (1) by integer polynomials with finitely many auxiliary variables, over the class of relations that have one, and over single-fold maps, those whose graph (2) lies in .