The Setting
A choiceless computation on a structure works with hereditarily finite sets over its atoms, and lower bounds for choiceless polynomial time compare the sets built over two structures that counting logic does not distinguish. Here such a set is described by a form: a finite tree whose leaves name entries of a tuple of atoms and whose set nodes collect the values of their children at every tuple for which the pair has a prescribed type in counting logic.
The question is how much of these sets the types of the parameters fix. Take pairs of tuples and , possibly over two different structures, of the same counting type, and two forms and . Is the value of at equal to, or a member of, the value of at exactly when the same holds at and , and do sets defined alike agree on being atoms and on the base relations?
Counting Types
Throughout, is a vocabulary of binary relation symbols and a finite set of variable names. A binary relational structure over with universe is a set together with a binary relation on for every symbol , the base relations of ; the universes here are finite and nonempty, and their elements are the atoms.✦ The formulas of the counting logic over , with variables from , are generated by the following clauses, in which and stand for formulas: (1)✦
The free variables of are the names occurring in it outside the scope of a quantifier that binds them.✦ Satisfaction under an assignment is given by the usual recursion, in which holds when exactly elements satisfy under updated to send to .✦ The type of in relative to a finite set of names is (2)✦
For a finite index set , a tuple and an injection , the type of is , where gives each name the value and every other name a fixed element of .✦ When is an injection of two disjoint copies of a finite set into and , is the type of the tuple that is on the first copy and on the second.
Forms and Their Values
The hereditarily finite sets over form the set : every atom is an element of , an urelement with no elements, and every finite set of elements of is again one.✦ Each element of is either an atom or a set.✦
A form over with labels in a set is either a leaf carrying an index or a set node with branches, numbered , of which branch carries a form over with labels in and a label .✦ The forms here are labelled by sets of formulas of .
The value of a form over labelled by sets of formulas of at a tuple , taken with an injection of into , is defined by recursion on : a leaf with index has value the atom , and a set node has value (3)✦
Supported Sets and Tuples Represented Alike
Let a group act on , and through the atoms on . A tuple of atoms supports an element of when every fixing each entry of the tuple fixes .✦ An element of is -supported, for a natural number , when some tuple of atoms supports it✦, and hereditarily -supported when , its elements, their elements and so on are all -supported.✦ The set consists of the hereditarily -supported elements of .✦
The HF structure of is the structure with universe over the vocabulary of a membership symbol , an atom symbol and a copy of each , in which holds when is an element of , when is an atom, and when and are atoms and with .✦
Let be a second structure over , with finite nonempty universe on which a group acts. Fix a finite index set , an injection of into and an injection of two disjoint copies of into , with which values of forms over are taken. Tuples of elements of and of elements of are represented alike when there are forms , for , over labelled by sets of formulas of , and families of atoms of and of atoms of , indexed by and , such that (4)✦ where and .
The Claim
Theorem 1. Let and be binary relational structures over with finite nonempty universes and , let be a finite set and an injection of into , and let and be forms over labelled by sets of formulas of . If tuples and satisfy , then (5)✦ (6)✦ Let moreover groups and act on and , let be a natural number and a finite index set, and let tuples of elements of and of elements of , indexed by , be represented alike as in (4), for injections of and of two disjoint copies of into . Then for all and , (7)✦ (8)✦
In the paper, the result reads: for forms and , if and have the same type, with the paper’s number of variables and and the same or different base structures, then if and only if , and if and only if ; the atom predicate and all base relations also agree on corresponding form values.
What Is Checked
The claim is stated over the types in of tuples from binary relational structures and the values of forms labelled by sets of such formulas, and, for atoms and base relations, over the HF structure on hereditarily -supported sets and tuples represented alike.