The Setting
Let and be structures over one vocabulary of binary relations, on finite sets of atoms and acted on by groups and . Fix a number . Hereditarily finite objects over the atoms are described by set-builder forms over an -tuple of atoms, each level collecting the objects described at all -tuples of a prescribed counting type over the current one. The question is whether, when tuples of the same type are conjugate under the group, the objects over and over hereditarily supported by atoms can be matched one to one, each matched pair described by one form at tuples of the same type. The matching is also wanted to respect assignments whose entries are already given by forms at tuples of the same type, so that adjoining a matched pair to them keeps them so.
Counting Types
A binary relational structure over a vocabulary with universe interprets every symbol of as a binary relation on .✦ The formulas of over are those of first-order logic with equality, and the exact counting quantifiers , built from , equations and atoms for , with variable names from a finite set .✦ Satisfaction under an assignment is defined by recursion on , with true when exactly values of satisfy ✦, and is the set of variables of not bound by a quantifier.✦
The type of an assignment relative to a finite set of names is the set of formulas of whose free variables lie in and which satisfies under : (1)✦ For an injection and a tuple , with nonempty, the type of is the type (1), relative to the names , of the assignment from , which gives each name the value and every other name one fixed atom.✦
Write , and let be a finite set of parameter indices and a set of positions. Injections of , , and into are fixed; the type of a tuple indexed by one of these sets is taken with its injection and written , and is the type of the tuple that is on the first summand and on the second.
A structure on , with a group acting on , is homogeneous for tuples indexed by when any two tuples of with the same type are conjugate under : (2)
Supported Objects and Forms
The group acts on , the hereditarily finite objects over the atoms . The pointwise stabilizer of a tuple of atoms is the subgroup of the elements of that fix every entry of . A tuple of atoms supports an object of when fixes .✦ An object of is -supported when some tuple of atoms supports it✦, and hereditarily -supported when , its elements, their elements and so on down the membership relation are all -supported.✦ The domain of supported objects over is the set of hereditarily -supported objects of , and is defined from the action of on in the same way.✦
A form over an index set with labels in a set is a finite tree with two kinds of node: a leaf carrying an index , and a set node with branches , each carrying a child form and a label .✦ Here and the labels are sets of formulas of . The value of a form at a tuple is the atom when is a leaf carrying , and when is a set node it is (3)✦ with on the first copy of and on the second.
For and a set of formulas, the molecules of over in are the tuples with .✦ The label values of a form at over form the set of its values (3) at these molecules: (4)✦
Two assignments and are represented alike when there are forms for and tuples and , with rows and likewise, such that (5)✦
The Claim
Theorem 1. Let and be binary relational structures over on finite nonempty sets of atoms and , with groups acting on and acting on , and let and be their domains of hereditarily -supported objects.
(a) Suppose acts by automorphisms of and is homogeneous for tuples indexed by . Then for any , set of formulas, form and label values , (6)✦
(b) Suppose in addition that acts by automorphisms of and is homogeneous for tuples indexed by . If , and the set of formulas has a molecule over in and a molecule over in , then for every form (7)✦
(c) Let , suppose and are homogeneous for tuples indexed by and by , and let and have the same type. Then there is a bijection such that every has a form and tuples and with (8)✦
(d) Let , suppose and are homogeneous for tuples indexed by and by , let and be represented alike, let , and for write for with its entry at replaced by . Then there is a bijection such that for every (9)✦
In the paper, the result reads: for represented-alike assignments under the paper’s bound , in which and are the paper’s own parameters, there is a bijection such that adjoining any pair gives represented-alike assignments, and in particular for the entries and of the two assignments at every position kept when the pair is adjoined.
What Is Checked
The library states (6), (7), (8) and (9) over binary relational structures on finite sets of atoms with groups acting on them, the formulas of with their satisfaction and the counting types (1) of tuples, the hereditarily -supported objects of and , set-builder forms and their values (3), the label values (4) at molecules, and assignments represented alike (5).