We study the relationship between standard alphabets over the equality atoms, and those which can be made homogeneous using finitely many relations and functions. We leave open the problem whether these notions coincide.
Let denote the equality atoms and denote the group of all bijections of the set . An alphabet is just an orbit-finite, equivariant set with atoms. It inherits the action of the group . We may therefore view as a group of permutations of the alphabet .
For a family of relations and functions over of finite arity, by we denote the logical structure with universe , together with the functions and relations from . Let denote its automorphism group.
If the elements of are equivariant with respect to the action of on , then
We say that the family retains the group if above, equality holds. We say that the alphabet can be turned into a homogeneous structure if the family can be chosen so that the retains the group and the structure is homogeneous.
Question 1. Are the following conditions equivalent for an alphabet ?
- can be turned into a homogeneous structure using finitely many relations and functions,
- is a standard alphabet.
The problem is not with retaining the group , it is with making the structure homogeneous using finitely many operations.
Lemma 1. Any alphabet can be equipped with a finite family of relations which retains the group .
Proof. Consider the set of those pairs such that has exactly one element (which is an atom). Let be the mapping which maps the pair to this element. Clearly, this is an equivariant mapping.
Consider the relation which is the kernel of the mapping . This relation allows us to define the set of atoms within , as equivalence classes of the relation .
We consider several other relations. To this end, for each orbit of , consider an equivariant, surjective function . Let be the graph of the composition
Claim. The family which consists of and each relation (where is an orbit of ) retains the group .
Let be a bijection which preserves each relation in . Since this mapping preserves the relation , it follows that it induces a mapping of the set .
We define a mapping so that if and only if there are such that .
Below we prove the implication 1→2 and, under some additional assumptions on , also the implication 2→1. It is not clear whether these additional assumptions are necessary.
Before showing the implications, let’s see some examples.
Example 1. Consider the alphabet whose elements are of the form , where are pairwise distinct atoms. This alphabet is easily seen to be standard. Consider the following family of relations defined as follows, where range over and ranges over .
Already the relations and suffice to retain the group . The remaining relations (perhaps not all) are needed for making homogeneous. The idea is that the isomorphism type of a finite substructure with elements describes completely and uniquely the Venn diagram of the sets . If two such families of sets have exactly the same Venn diagrams, then there is a bijection of their elements which maps one family to the second one.
Note that it suffices to equip only with relations in order to turn it into a homogeneous structure. In the next example, one also needs to equip with functions.
Example 2. Consider the alphabet whose elements are of the form , where are pairwise distinct atoms (this is the Cherlin-Lachlan example). We sketch how to turn into a homogeneous structure.
First we several relations so that they retain the group . However, to turn into a homogeneous structure, we add a function which composes two letters, i.e. , where and are treated as partial functions from to — this is assuming that ; if not, we set .
One can prove (this is an example from Cherlin and Lachlan) that it is impossible to turn into a homogeneous structure using only finitely many relations.
Suppose that the alphabet can be turned into a homogeneous structure using a finite family of functions and relations. We show that then there exists a deterministic Turing machine recognizing the language
The machine , given on input two words proceeds by generating the substructures of induced by the elements of and of . These induced substructures are finite, since each element of is supported by , and there are only finitely many elements in which are supported by a finite set of atoms. If the mapping which sends the -th letter of to the -th letter of extends to an isomorphism of the structures , then the words and are in the same orbit of , due to homogeneity. The converse implication holds trivially. Therefore, to check if and are in the same orbit, the machine verifies that and are isomorphic structures. This ends the proof of the implication 1→2.
We can only prove the implication 2→1, under an additional assumption.
We say that a Turing machine over an input alphabet is straight if its work alphabet and state space are isomorphic to a set , where .
Fix an enumeration of the orbits in and for each orbit , fix a (possibly partial) surjective mapping .
For a letter , if , then an atomless description of consists of:
- the number of the orbit containing ,
- a list of identifiers for the atoms , each of which is a unique binary string.
Note that the description of is not unique, since, due to the automorphisms of , there might be several permutations of the atoms which project under to the same letter .
For a word , an atomless description of the word consists of the list of atomless descriptions of each of its letters, so that the same atom occurring in different letters gets the same identifier.
Note that two words are in the same orbit if and only if they have the same sets of descriptions.
Consider the language
We recall that is standard iff the language is deterministically recognizable.
Lemma 1. If the language is recognized by a straight Turing machine then the alphabet can be turned into a homogeneous structure using a finite family of functions and relations.
Proof. Let be the transition function of the machine . Since is straight, both the domain and codomain of the function are isomorphic to straight sets.
Let be a family of relations which retains the group , additionally extended by the function . Formally, is not a function nor relation over , but since its domain and codomain are straight sets, the function can be described (using an equivariant formula) by a finite family of functions and relations over .
We claim that the structure is homogeneous.
Let be a partial isomorphism between two induced substructures of . Let be a tuple consisting of all the elements in the domain of , and let be the tuple of images under of the elements of .
Let be a description of the word . Then, is accepted by the machine . From the fact that is an isomorphism, it follows that the result of the machine is the same on input and input , so also accepts the word . Therefore, , so is a description of , so is in the same orbit as under the action of on . But , so there is an automorphism of which extends . This proves that is homogeneous.
Therefore, in order to prove the implication 2→1 it suffices to prove that over a standard alphabet, every deterministic Turing machine can be converted into an equivalent one which is straight. This would be also necessary to prove the implication 2→1.
Lemma. The following conditions are equivalent for a straight alphabet .
A) Every Turing machine over this alphabet can be turned into an one which is straight and recognizes the same language,
B) There is a straight Turing machine recognizing the language ,
C) The alphabet can be turned into a homogeneous structure using a finite family of functions and relations.
Proof. The implication A→B is obvious, since, by assumption that is standard, the language is recognized by some deterministic machine, and by assumption (A) there is an another one which is straight and recognizes the same langauge.
The implication B→A follows from the fact that using a straight machine for , a deterministic straight Turing machine can first generate a description of the input word, and then simulate the computation of any deterministic Turing machine on this description, but without using any atoms.
The implication B→C was shown in the previous lemma.
For the implication C→B, observe that in the proof of the implication 1→2 we constructed a straight Turing machine for the language . By a similar argument, we could construct a straight Turing machine for the language .
Therefore, Question 1 is in fact equivalent to the following
Question 1′. Over a standard alphabet , can every deterministic Turing machine be turned into one which is straight and recognizes the same language?
It is possible that the assumption that is standard isn’t necessary.
Question 2. Is there an alphabet and a deterministic Turing machine over this alphabet, which cannot be turned into a straight one recognizing the same language?