The Setting
Let and be structures over one vocabulary of binary relation symbols, on sets of atoms and , and let a group act on and a group on . Over lie the hereditarily finite sets in which choiceless polynomial time computes. Fix a number . A hereditarily -supported set over is a set that, like each of its members at every depth, is fixed by every element of that fixes some atoms chosen for it; read these sets as a structure with membership, and over , with , do the same. The question is when a formula of counting logic holds in the first of these structures at an assignment of sets over exactly when it holds in the second at an assignment of sets over . The comparison goes through the atoms: a set is described by a set-builder form over a tuple of atoms, and tuples of atoms are compared by their counting types.
Counting Types
A binary relational structure over with universe interprets each symbol as a binary relation on .✦ The counting formulas over with variable names from a set are built from , equations and atoms , for and , by negation, conjunction, existential quantification and exact counting quantification for ; with names, they are the formulas of .✦ Satisfaction under an assignment is defined by recursion on , the formula holding when exactly elements of satisfy under changed to send to .✦ The free variables of are the names occurring in it outside the scope of a quantifier binding them.✦
The type in of an assignment , relative to a finite set of names, is the set of counting formulas with free variables in that hold in under .✦ For a tuple of elements of , with finite, and an injection placing its entries at names, the counting type of is the type of the assignment sending each to , relative to the image : (1)✦
With respect to , the structure is homogeneous for -tuples placed by when tuples of one counting type lie in one orbit of : for all , (2)
Hereditarily Supported Sets
The hereditarily finite (HF) sets over form the collection of the atoms of , each an urelement with no elements, and of the finite sets of members of , two sets being equal when they have the same elements; acts on through the atoms.✦ A tuple of atoms supports when every that fixes each fixes .✦ An object of is -supported when some -tuple of atoms supports it✦, and hereditarily -supported when and every object reached from it by finitely many steps down the membership relation are -supported.✦ The set is the set of all hereditarily -supported objects of with respect to .
The HF vocabulary over has a membership symbol , an atom symbol and a copy of each symbol of .✦ The HF structure of is the structure over the HF vocabulary with universe in which is membership, holds when is an atom, and holds when and are atoms and with .✦ Over and the same construction gives and .
Set-builder Forms
A set-builder form over the indices with labels in a set is a finite tree: either a leaf carrying an index , or a set node with branches , for some , each branch carrying a child form and a label .✦ The forms used here are labelled by sets of counting formulas over in the names . Fix an injection placing two copies of at names in . The value of a form at an -tuple of atoms of is the atom when is a leaf with index , and, when is a set node with children and labels for , the set (3)✦ where is the -tuple with on the first copy and on the second.
Let be a finite set of variable names and an injection of into . Assignments and are represented alike when there are forms , for , and parameter tuples of atoms of and of atoms of , indexed by and , with (4)✦ where is the -tuple and likewise.
The Claim
Theorem 1. Let . Let and be binary relational structures over on sets of atoms and , with a group acting on and a group acting on ; let be a set of variable names, a finite set of variable names, and and injections of two copies of and of into . Suppose that , with respect to , and , with respect to , are homogeneous (2) both for -tuples placed by and for parameter tuples, indexed by and placed by . Let and be assignments represented alike (4). Then every counting formula over the HF vocabulary with variable names from satisfies (5)✦
What Is Checked
The claim is stated over counting formulas and their satisfaction, the counting types (1) and homogeneity (2), the hereditarily -supported sets with their HF structure, the values (3) of set-builder forms, and assignments represented alike (4).