The Setting
Let be a tuple in a finite structure and a tuple of the same length in a finite structure , and suppose the two have the same type in the counting logic with variables. Extend each by further entries indexed by a finite set , so that the longer tuples have at most entries. Does every type of the longer tuples occur as often among the extensions of as among those of ?
Two companion questions come with it: whether equal types stay equal on subtuples, taken in any order, and whether a single formula defines a given type in both structures at once.
Counting Logic and Types
A -structure , for a vocabulary of binary relation symbols, is a set , its universe, with a binary relation for each symbol .โฆ
Fix a finite set of variable names. The formulas of the counting logic over are falsity, equations and relational atoms between names, and the formulas built from them by negation, conjunction, existential quantification and exact counting quantification: (1)โฆ The free variables of a formula are the names occurring in it outside the scope of a quantifier that binds them; both and bind .โฆ
An assignment into is a map , and agrees with except that it sends to . Satisfaction is defined by the usual recursion: never holds, and are read at the values and , negation and conjunction are classical, and holds when for some ; the counting quantifier asks for exactly such : (2)โฆ
The type of an assignment into on a set of names is the set of formulas of with free variables in that hold in under : (3)โฆ
A tuple , indexed by a finite set , is placed at the names by an injection ; its names are the image .โฆ When is nonempty, the assignment of sends to for each and every other name to a fixed default element of โฆ, and the type of at is the type of this assignment on the names of : (4)โฆ
For a finite set and , the extension agrees with on and with on . For an injection , the subtuple lists the entries of at in the order of .
The Claim
Theorem 1. Let and be -structures with nonempty universes and , and in parts (a) to (c) let them be finite.
Let and be finite sets, let and be injections, and let and have the same type, . Then for every set of formulas of (5)โฆ and there is a bijection with (6)โฆ
Let and , put , and let and be assignments with . Then for every type of an assignment (7)โฆ
For every and every assignment there is a formula of with such that for all assignments and (8)โฆ
Let and be finite sets, let , and be injections, and let and satisfy . Then (9)โฆ
In the paper, the result reads: if tuples and have the same type in two structures chosen from the grid structures and of the two charges and , and , then for every realized type of length the number of tuples indexed by with of type equals the number of tuples indexed by with of type , and tuples of equal type have equal types on every projected or reordered subtuple.
In (5) and (6) the bound is the injection of into the names.
What Is Checked
The claim is stated over -structures and the formulas (1) of with their free variables and satisfaction (2), through the types of assignments (3) and of tuples (4).