Standard alphabets vs. homogenizability

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 \atoms denote the equality atoms and \aut \atoms  denote the group of all bijections of the set \atoms. An alphabet A is just an orbit-finite, equivariant set with atoms. It inherits the action of the group \aut \atoms. We may therefore view \aut\atoms as a group of permutations of  the alphabet A.

For a family \Ff=\set{R,S,\ldots,f,g,\ldots} of relations and functions over A of finite arity, by A_\Ff we denote the logical structure with universe A, together with the functions and relations from \Ff. Let \aut{A_\Ff} denote its automorphism group.

If the elements of \Ff are equivariant with respect to the action of \aut\atoms on A, then

    \[\aut{A_\Ff}\subset \aut \atoms.\]

We say that the family \Ff retains the group \aut\atoms if above, equality holds. We say that the alphabet A can be turned into a homogeneous structure if the family \Ff can be chosen so that the \Ff retains the group \aut\atoms and the structure A_\Ff is homogeneous.

Question 1. Are the following conditions equivalent for an alphabet A?

  1. A can be turned into a homogeneous structure using finitely many relations and functions,
  2. A is a standard alphabet.

The problem is not with retaining the group \aut {\atoms}, it is with making the structure homogeneous using finitely many operations.

Lemma 1. Any alphabet A can be equipped with a finite family of relations which retains the group \aut {\atoms}.

Proof. Consider the set U\subset A^2 of those pairs (x,y) such that \sup x\cap \sup y has exactly one element (which is an atom). Let \alpha:U\to \atoms be the mapping which maps the pair (x,y) to this element. Clearly, this is an equivariant mapping.

Consider the relation R\subset U^2\subset A^4 which is the kernel of the mapping \alpha. This relation allows us to define the set of atoms \atoms within A, as equivalence classes of the relation R.

We consider several other relations. To this end, for each orbit O of A, consider an equivariant, surjective function f_O:\atoms^n \to A. Let R_O\subset A^{2n+1} be the graph of the composition

    \[A^{2n}\supset U^n\to \atoms^n\to A.\]

Claim. The family \Ff which consists of R and each relation R_O (where O is an orbit of A) retains the group \aut{\atoms}.

Let \pi: A\to A be a bijection which preserves each relation in \Ff. Since this mapping preserves the relation R, it follows that  it induces a mapping of the set U\subset A^2.

We define a mapping \hat\pi:\atoms\to \atoms so that \hat\pi(a)=b if and only if there are u,v\in U such that \pi(u)=\pi(v). \square

Below we prove the implication 1→2 and, under some additional assumptions on A, 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 A whose elements are of the form \set{a,b,c}, where a,b,c are pairwise distinct atoms. This alphabet is easily seen to be standard.  Consider the following family of relations \Ff=\set{E,P_0,P_1,P_2,P_3,T_0,T_1,T_2,T_3} defined as follows, where x,y,z range over A and i ranges over \set{0,1,2,3}.

    \begin{align*} P_i(x,y)&\iff |x\cap y|=i,\\ T_i(x,y,z)&\iff |x\cap y\cap z|=i,\\ E(x,x',y,y')&\iff x\cap x'=y\cap y' \end{align*}

Already the relations E and P_1 suffice to retain the group \aut{\atoms}. The remaining relations (perhaps not all) are needed for making A_\Ff homogeneous. The idea is that the isomorphism type of a finite substructure with elements x_1,x_2,\ldots,x_n  describes completely and uniquely the Venn diagram of the sets x_1,x_2,\ldots,x_n. 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 A only with relations in order to turn it into a homogeneous structure. In the next example, one also needs to equip A with functions.\square

Example 2. Consider the alphabet A whose elements are of the form \{(a,b),(c,d)\}, where a,b,c,d are pairwise distinct atoms (this is the Cherlin-Lachlan example). We sketch how to turn A into a homogeneous structure. 

First we several relations so that they retain the group \aut\atoms. However, to turn A into a homogeneous structure, we add a function f:A^2\to A which composes two letters, i.e. f(x,y)=x\circ y, where x and y are treated as partial functions from \atoms to \atoms — this is assuming that \im y=\dom x; if not, we set f(x,y)=x.

One can prove (this is an example from Cherlin and Lachlan) that it is impossible to turn A into a homogeneous structure using only finitely many relations.\square

 

Implication 1→2.

Suppose that the alphabet A can be turned into a homogeneous structure using a finite family \Ff of functions and relations. We show that then there exists a deterministic Turing machine M recognizing the language

    \[\mathrm{Iso}_A=\set{vw\in A^*: v,w \text{ are in the same orbit}}.\]

The machine M, given on input two words v,w proceeds by generating the substructures \langle v\rangle,\langle w\rangle of A_\Ff induced by the elements of v and of w. These induced substructures are finite, since each  element of \langle v\rangle is supported by \sup v, and there are only finitely many elements in A which are supported by a finite set of atoms. If the mapping which sends the i-th letter of v to the i-th letter of w extends to an isomorphism of the structures \langle v\rangle,\langle w\rangle, then the words v and w are in the same orbit of \aut {A_\Ff}=\aut \atoms, due to homogeneity. The converse implication holds trivially. Therefore, to check if v and w are in the same orbit, the machine M verifies that \langle v\rangle  and \langle w\rangle are isomorphic structures. This ends the proof of the implication 1→2.\square

Implication 2→1.

We can only prove the implication 2→1, under an additional assumption.

We say that a Turing machine M over an input alphabet A is straight if its work alphabet B and state space Q are isomorphic to a set A^n\times \set{1,\ldots,m}, where m,n\in\Nat.

Fix an enumeration O_1,O_2,\ldots,O_n of the orbits in A and for each orbit O_i, fix a (possibly partial) surjective mapping f_i:\atoms^{n_i}\to O_i.

For a letter x\in A, if x=f_i(a_1,\ldots,a_{n_i}), then an  atomless description of x consists of:

  • the number i of the orbit O_i containing a,
  • a list of identifiers for the atoms a_1,\ldots,a_{n_i}, each of which is a unique binary string.

Note that the description of x is not unique, since, due to the automorphisms of x, there might be several permutations of the atoms a_1,\ldots,a_{n_i} which project under f_i to the same letter x.

For a word v\in A^*, an atomless description of the word v 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 v,w\in A^* are in the same orbit if and only if they have the same sets of descriptions.

Consider the language

    \[\mathrm{Type}_A=\set{vw: v\in A^*, w\in \set{0,1}^*: w\text{ is a desc. of } v}.\]

We recall that A is standard iff the language \mathrm{Type}_A is deterministically recognizable.

Lemma 1. If the language \mathrm{Type}_A is recognized by a straight Turing machine M then the alphabet A can be turned into a homogeneous structure using a finite family \Ff of functions and relations.

Proof. Let \delta:Q\times B\to Q\times B\times\set{-1,1} be the transition function of the machine M. Since M is straight, both the domain and codomain of the function \delta are isomorphic to straight sets.

Let \Ff be a family of relations which retains the group \aut{\atoms}, additionally extended by the function \delta. Formally, \delta is not a function nor relation over A, but since its domain and codomain are straight sets, the function \delta can be described  (using an equivariant formula) by a finite family of functions and relations over A.

We claim that the structure A_\Ff is homogeneous.

Let f be a partial isomorphism between two induced substructures of A_\Ff. Let v be a tuple consisting of all the elements in the domain of f, and let v' be the tuple of images under f of the elements of v.

Let w be a description of the word v. Then, vw is accepted by the machine M. From the fact that f is an isomorphism, it follows that the result of the machine M is the same on input vw and input v'w, so also M accepts the word v'w. Therefore, v'w\in \mathrm{Type}_A, so w is a description of w, so v' is in the same orbit as v under the action of \aut\atoms on A. But \aut\atoms=\aut{A_\Ff}, so there is an automorphism of A_\Ff which extends f. This proves that A_\Ff is homogeneous.\square

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.

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 \textrm{Type}_A,

C) The alphabet A can be turned into a homogeneous structure using a finite family \Ff of functions and relations.

Proof. The implication A→B is obvious, since, by assumption that A is standard, the language \textrm{Type}_A 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 \textrm{Type}_A, 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 \textrm{Iso}_A. By a similar argument, we could construct a straight Turing machine for the language \textrm{Type}_A. \square

Therefore, Question 1 is in fact equivalent to the following

Question 1′. Over a standard alphabet A, can every deterministic Turing machine be turned into one which is straight and recognizes the same language?

It is possible that the assumption that A is standard isn’t necessary.

Question 2. Is there an alphabet A and a deterministic Turing machine over this alphabet, which cannot be turned into a straight one recognizing the same language?

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>