The Setting
An interpretation program runs a choiceless computation on a finite structure : one interpretation of first-order logic with the HΓ€rtig quantifier builds the first state from , another builds each state from the one before, and a halting sentence and an output sentence are read on the states. Each element of a state is a class of pairs from the previous state, and it is coded by a hereditarily finite object over the elements of as atoms, built from its stage and the codes of the members of its class. The item shows that counting logic with variables defines these codes on a domain of hereditarily finite objects, by formulas that do not depend on the input, and that sentences about the states become sentences of counting logic about the domain.
Counting Logic and Uniform Definitions
A binary relational structure over a vocabulary with universe interprets every symbol of as a binary relation on .β¦ The formulas of counting logic over with variable names from a set are built from , equations and atoms , for names and symbols , by negation, conjunction, existential quantification and, for each natural number , the counting quantifier ; is counting logic with the names .β¦ Satisfaction under an assignment of elements of to the names is the usual one, with true when exactly elements of satisfy once is sent to .β¦ The free variables of are the names that occur in it outside the scope of a quantifier binding them.β¦
Let be an index set and a family of binary relational structures over with universes . A family of -ary relations is uniformly definable in when for every map , placing the arguments on names, there is one formula of with free variables among such that for every and every assignment (1)β¦
Hereditarily Finite Codes
The set of hereditarily finite objects over a set of atoms is the least set that contains every atom of , as an object with no elements, and every finite set of its own members.β¦ The set predicate holds of the sets of and fails at the atoms.β¦ In one forms the singleton , the doubleton , the Kuratowski pair and the von Neumann ordinals, with and . A coding domain over is a set taken as the universe of a binary relational structure; it is transitive when every element of a set in lies in .β¦
Interpretation Programs
A finite structure over a set of binary relation symbols is a finite universe with a binary relation on it for each .β¦ The formulas of over in variables are built from , equations and atoms by negation, conjunction, and the HΓ€rtig quantifier , for and in the variables ; holds when as many elements satisfy as satisfy .β¦ A sentence , a formula in no variables, holds in , written , when it is satisfied under the empty assignment.β¦ The scoped width of a formula is the largest number of variables in scope at an atom or an occurrence of in it.β¦
A two-dimensional interpretation of structures over a set of binary relation symbols in structures over consists of formulas of over : a domain formula , an equivalence formula and, for each , a relation formula , where and are pairs of variables.β¦ On a finite structure over , its domain is the set of pairs with ; two pairs of the domain are linked when , and is the equivalence relation on generated by the links. The classes are the vertices of on , and the quotient is the universe of the interpreted structure .β¦
For a binary relation on a set , reachability in rounds is the binary relation on defined by recursion on : when and are joined by one step of , and when , or for some joined to by one step of .β¦
An interpretation program over a vocabulary consists of a finite set of binary state symbols, an interpretation of structures over in structures over , an interpretation of structures over in structures over , and two sentences of over , the halting condition and the output condition .β¦ The state of after steps on a finite structure over is the structure over with and .β¦
Coding the States
Let be an interpretation, a finite structure and a map coding its elements. The payload of a vertex of on and its code at stage are the objects (2)
The code of a program at step on maps into : is the code at stage for on , each element of coded by itself as an atom, and is the code at stage for on , the elements of coded by .β¦ For a bound , the trace family of on is the increasing sequence of finite subsets of in which is a base family fixed by and adds to the pairs of codes and the vertex codes that arise in building .β¦
Now let be binary relational structures over on coding domains , and let be finite structures over with maps . The family is state-definable in when the images and, for each , the relations (3)β¦ are uniformly definable in . Let be an interpretation in structures over . The encoded domain of on is the set of pairs with , and the encoded equivalence of on is the set of quadruples with in .
The Claim
Theorem 1. Let be an interpretation program over with state symbols , let be finite structures over , and let , and be natural numbers. For each , let be a transitive coding domain that contains every ordinal and the trace family of on for the bound , with a structure in which membership and the set predicate are uniformly definable in . Then, with the state of after steps on and its code, (4)β¦ If finite structures over with injective maps form a family state-definable in , each has at most elements, and is a sentence of over of scoped width less than , then there is a sentence of with (5)β¦ For such and , an interpretation in structures over , and all and , the following relations on are uniformly definable in : (6)β¦ (7)β¦ (8) (9) For a binary relation on a finite set with at most elements, generating the equivalence relation , (10)β¦ and for finite sets and in bijection with sets and , with , (11)β¦
In the paper, the result reads: at every stage through halt, a formula of selects exactly the vertex codes of the state and each formula defines exactly its corresponding binary state relation, and the translated halt and output sentences are exact at every stage through halt.
The box gives the selection of the vertex codes and the definition of the state relations for every step , and the exactness of the halt and output sentences from (5) with the halting or the output condition.
What Is Checked
The claim is stated over counting logic with its satisfaction and free variables, uniform definability (1), the hereditarily finite objects with their pairs, ordinals and set predicate, coding domains, the logic with scoped width, two-dimensional interpretations with the equivalence generated by their links, reachability in rounds, interpretation programs and their states, payloads and vertex codes (2), the codes , the trace family and state-definability (3). Under the hypotheses of the box, the library proves that every element of , as an atom, lies in β¦, and that for every code of an element of lies in β¦.