The Setting
Take a finite structure with binary relations on a set of atoms, and a group acting on by automorphisms of . A program of choiceless polynomial time over computes with hereditarily finite sets over , and moves these sets as it moves the atoms. The question is which of these sets have a support of atoms at every level of membership, and how each of them is named from atoms in counting logic. The answer is given by forms, set-builder terms over a tuple of atoms whose steps are guarded by counting types.
Counting Types
A binary relational structure over a vocabulary with universe interprets every symbol as a binary relation on .✦ A formula of counting logic over with variable names from a set is , an equation or an atom with and , or is built from formulas by negation, conjunction, existential quantification and the counting quantifiers for ; for finite these are the formulas of .✦ Satisfaction of a formula under an assignment is the usual one, with true under when exactly elements make true under .✦
The type of an assignment in relative to a finite set of names is the set of formulas whose free variables lie in and which satisfies under : (1)✦ For an injection and a tuple over a nonempty , the counting type of is the type, relative to the names of the tuple, of the assignment that sends to for each and every other name to a fixed element of .✦
Fix and an injection of two disjoint copies of into . For tuples , is the -tuple with on the first copy and on the second, and is its counting type under .
Hereditarily Finite Objects and Supports
The set of hereditarily finite objects over a set of atoms is the smallest set that contains the atoms and every finite subset of itself.✦ A group acting on acts on by and on tuples of atoms entrywise.
A tuple supports an object when every element of that fixes each entry of fixes : (2)✦ For , an object is -supported when some tuple supports .✦ An object is hereditarily -supported when , its elements, their elements and so on down the membership relation are all -supported; is the set of these objects.✦
Forms and Their Values
A form over an index set with labels in a set is a finite tree that is either an atom node carrying an index or a set node with branches for some , branch carrying a form over with labels in and a label .✦
Given and , the value of a form over whose labels are sets of formulas of counting logic over with names from , at a tuple , is defined by recursion on . An atom node with index has as value the atom ; a set node with branches has as value (3)✦
The Claim
Theorem 1. Let be a binary relational structure over on a finite nonempty set of atoms, let a group act on by automorphisms of , let , and let place two disjoint copies of at distinct names of a finite set . For every form and every tuple , (4)✦ every with satisfies (5)✦ and every satisfies (6)✦ Conversely, suppose that and that any two -tuples of atoms with the same counting type under satisfy for some . Then for every there are a form and a tuple with (7)✦
In the paper, the result reads: every value belongs to and is supported by , every object of has such a representation, and for every , the paper’s and standing where the page has and .
What Is Checked
The claim is stated over binary relational structures on a finite nonempty set of atoms with a group acting by automorphisms, the counting types of tuples of atoms in counting logic with names from a finite set, forms labelled by sets of formulas and their values in , and the supports, -supports and hereditary -supports of hereditarily finite objects.