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$ ?

$A$ can be turned into a homogeneous structure using finitely many relations and functions,
$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?

Atompress

Standard alphabets vs. homogenizability

Leave a Reply Cancel reply

Computation with atoms