The Setting
Let be a set of indices, and color the finite tuples of distinct elements of . A color can code a diagram on a finite set of positions, the places of a tuple, a system of two binary relations and ordinal tags. The full subsequence test asks, at a tuple , whether the diagrams coded by the colors of the subsequences of are the parts of one diagram on the positions of .
Colors and Diagrams
A binary sequence is a map , and is the set of binary sequences.✦ Binary sequences and are equal outside a finite set, written , when they differ at finitely many places, and the palette of colors is the quotient of by this relation: (1)
Let be a set, whose elements are called positions. A label on is a pair in which is a nonempty finite subset of and ✦, and the root of a position is the label .✦ An injection carries a label on to the label on .✦ A diagram on is a triple in which and are binary relations on the labels on and assigns to each label a tag in .✦
A diagram on is valid when is an equivalence relation and, for all labels and all positions , (2)✦
For a diagram on and an injection , the restriction of along is the diagram on given by (3)✦
Under the continuum hypothesis (CH), , the code is an injection that assigns to each diagram on , for each , a color , distinct diagrams, of equal or of different lengths, receiving distinct colors.
The Definition
Definition 1 (Full subsequence test). Let be a set. A tuple from is an injective map , for some , of length ; the tuples from form the set (4)✦ For a tuple of length and an order embedding , the subsequence of along is the tuple of length , (5)✦ Assume CH and let . A family of colors in , indexed by the order embeddings for all , passes when there is a diagram on such that (6)✦ A coloring passes the test at a tuple of length when the colors of the subsequences of form a family that passes: (7)✦
In the paper, with the set of positions of a tuple and a nonempty subset of it, the definition reads: holds when every decodes under to a valid diagram and for every nonempty , and colors attached to a tuple pass the test when this holds for the colors of its subsequences.
What Is Checked
The definition is stated over a set with its tuples and their subsequences along order embeddings, the palette , the diagrams on with their restrictions and validity, and the code under CH.
The library proves that equality outside a finite set is an equivalence relation on ✦.