The Setting
Lemma 5.9 compares models of the class of the paper whose base orders are countable. A basic structure of is handled through its normal form, made of an index set , a base order and arrays of bits on , all defined below. The question is when two normal forms with countable base orders present isomorphic structures. Behind it is a question about arrays: for countable , which arrays of bits on can be carried into which by translating each row by a finite subset of and each column by a finite subset of ?
Normal Forms
A tuple from a set is an injective map from into for some ; its length is .✦ The image of a tuple from along an injection is the tuple from , of the same length.✦
A normal form consists of a nonempty index set , a nonempty base set with a linear order , the base order, and a bit for each tuple from , each and each .✦ The base order is dense, has no least and no greatest element, and is locally countable: every closed interval of is countable. A superscript names the normal form, as in , and .
An array of bits on is a function from to ; for such an array, a finite set and a finite set , the entry of at translated by and is (1)✦
The set of points of has six disjoint kinds of element: an index point for each ; a base point for each ; a group point for each finite ; a star point for each finite ; a row for each tuple from , each and each finite ; and a column for each tuple from , each and each finite .✦
The Array Language
The array language is a countable relational vocabulary. Its unary symbols are the sort symbols index, base, group and star, a row symbol and a column symbol for , and a label for each finite . Its binary symbols are the order, the incidence and the bit symbol, and its ternary symbols are the group and star additions and the row and column actions. For it also has a row projection of arity and a column projection of arity .
A structure in a relational vocabulary consists of a set, its universe, and for each -ary symbol an -ary relation on the universe interpreting it.✦ An isomorphism of structures is a bijection between their universes such that each symbol holds of a tuple in exactly when it holds of in .✦
The structure of a normal form is the structure on in which the symbols hold of the following tuples of points and of no others. A sort symbol holds of the points of its kind, of the rows with of length , of the columns whose tuple has length , and of the star point . The row projection holds of such a row followed by the index points , and the column projection of a column with of length , followed by the base point and the index points . The order holds of base points , and incidence of a base point and a group point with . The bit symbol holds of a row and a column of the same tuple when the entry (1) of at , translated by and , is . The group and star additions hold of the triples of group points, respectively of star points; the row action holds of for a group point , and the column action of for a star point .
A presentation of a structure in the array language is a normal form together with a bijection from onto the universe of such that each symbol holds of a tuple of points in the structure of exactly when it holds of in .✦
Maps of Normal Forms
A map of normal forms consists of an injection , an order embedding , a row shift giving a finite set for each tuple from and each , and a column shift giving a finite set for each such and each , such that the bits agree: for all , and , (2)✦
The action of a map of normal forms on points is the map from to , also written , that sends index points , base points , group points , star points , rows and columns as follows: (3)✦
The Claim
Theorem 1 (Lemma 5.9). (a) Let be a countable set and an array of bits on . There are finite sets for and for such that, for all and , (4)✦
(b) Let be a countable set and , arrays of bits on . There are finite sets for and for such that, for all and , (5)✦
(c) Let and be normal forms with countable base orders and index sets of the same cardinality, . There is a map whose index and base parts are bijections: (6)✦
(d) Let be a map of normal forms whose index part and base part are onto. Then is onto the points of : (7)✦
(e) Let be a presentation of a structure and a presentation of a structure in the array language, and let be a map that is onto the points of . Then induces an isomorphism (8)✦
In the paper, the result reads: if have countable base orders and , then .
Parts (c), (d) and (e) give it for structures presented by normal forms as in (c).
What Is Checked
The claim is stated over tuples and their images along injections, normal forms with their dense, locally countable base orders without endpoints, the translated entry (1), maps of normal forms with their action (3) on points, the array language and the structure it receives on the points of a normal form, and structures, their isomorphisms and their presentations in that language.