The Setting
Let be a finite structure with universe . A computation by logical interpretations starts from and applies a two-dimensional interpretation again and again, so that each element of a state is a class of pairs of elements of the state before, and each element of the first state is a class of pairs of elements of . The item writes every element of every state as a hereditarily finite set over the atoms , the objects choiceless polynomial time computes with, built from the sets of the elements it comes from, and collects the sets built along a run into one family.
The set of hereditarily finite sets over is the least set that contains the atoms of and every finite set of its own elements.✦ The von Neumann ordinal of a natural number is defined by recursion: (1)✦
Interpretations and Programs
A finite structure over a set of binary relation symbols is a finite universe together with a binary relation on it for each .✦ Formulas over are those of Härtig logic, first-order logic with equality and the Härtig quantifier: they are built from falsity, equations and atoms by negation, conjunction, existential quantification and the Härtig quantification of two formulas in a new variable .✦ In under an assignment , the connectives and are read as usual, and (2)✦
Let be a set of binary relation symbols. A two-dimensional interpretation of structures over in structures over consists of Härtig formulas over : a domain formula , an identification formula , and for each a formula defining the relation between pairs.✦ On a finite structure over , its domain of pairs and its vertex set are (3) where is the equivalence relation on generated by linking to whenever . The structure over that defines in has universe , and its elements are the vertices.
An interpretation program over a set of binary relation symbols consists of a finite set of binary relation symbols, the state symbols, an initial interpretation of structures over in structures over , a step interpretation of structures over in structures over , and two Härtig sentences over , the halting condition and the output condition.✦ On a finite structure over , its state after steps is the structure over the state symbols given by (4)✦
The Claim
Definition 1. For , the Kuratowski pair of and is (5)✦ and it determines its components: for all , (6)✦ Let be an interpretation of structures over in structures over , let be a finite structure over , and let . The payload of a vertex is the set of the pairs of images of the pairs in , (7)✦ The vertex code of at level is (8) If is injective, then for every the vertex code is injective on : for all , (9)✦ Let be an interpretation program over with initial interpretation and step interpretation , let be a finite structure over with universe and states , and let send each element to itself as an atom. The codes of the states are the maps defined by recursion on : (10)✦ For a bound , the family of objects built from the codes is the sequence of finite subsets of given by (11)✦ where is the base family for the bound , and and are the families of pair objects and of class objects at level that builds on over .
What Is Checked
The definition is stated over the hereditarily finite sets over a set of atoms, with their singletons, doubletons and von Neumann ordinals, over finite structures with binary relations and the formulas of Härtig logic, and over two-dimensional interpretations, with their domains of pairs and vertex sets, and interpretation programs with their states.