pre-injectivity

Let $X={\prod }_{i\in I}{X}_i$ be a Cartesian product.Call two elements $x,y\in X$ almost equalif the set $\mathrm{\Delta }(x,y)=\{i\in I\mid x_i\ne y_i\}$ is finite.A function $f:X\to X$ is said to be pre-injectiveif it sends distinct almost equal elements into distinct elements,i.e., if implies $f(x)\ne f(y)$.

If $X$ is finite, pre-injectivity is the same as injectivity;in general, the latter implies the former, but not the other way around.Moreover, it is not true in generalthat a composition of pre-injective functionsis itself pre-injective.

A cellular automaton is said to be pre-injective if its global function is.As cellular automata send almost equal configurationsinto almost equal configurations,the composition of two pre-injective cellular automata is pre-injective.

Pre-injectivity of cellular automata can be characterizedvia mutually erasable patterns.Given a finite subset $E$ of $G$,two patterns$p_1,p_2:E\to Q$are mutually erasable (briefly, m.e.)for a cellular automaton$𝒜=⟨Q,𝒩,f⟩$on $G$if for any two configurations$c_1,c_2:G\to Q$such that${c_i|}_E=p_i$and${c_1|}_{G\setminus E}={c_2|}_{G\setminus E}$one has $F_{𝒜}(c_1)=F_{𝒜}(c_2)$.

Lemma 1

For a cellular automaton$\mathrm{A}\mathrm{=}\mathrm{⟨}Q\mathrm{,}\mathrm{N}\mathrm{,}f\mathrm{⟩}\mathrm{,}$the following are equivalent.

1. $𝒜$ has no mutually erasable patterns.

2. $𝒜$ is pre-injective.

Proof.It is immediate that the negation of point 1implies the negation of point 2.So let$c_1,c_2:G\to Q$be two distinct almost equal configurations such that$F_{𝒜}(c_1)=F_{𝒜}(c_2):$it is not restrictive to suppose that$𝒩$ is symmetric(i.e., if $x\in 𝒩$ then $x^{-1}\in 𝒩$)and $e$, the identity element of $G$, belongs to $𝒩$.Let $\mathrm{\Delta }$ be a finite subset of $G$ such that${c_1|}_{G\setminus \mathrm{\Delta }}={c_2|}_{G\setminus \mathrm{\Delta }},$and let

$$E=\mathrm{\Delta }{𝒩}^2=\{g\in G\mid \exists z\in \mathrm{\Delta },u,v\in 𝒩\mid g=zuv\}:$$(1)

we shall prove that$p_1={c_1|}_E$and$p_2={c_2|}_E$are mutually erasable.(They surely are distinct, since $\mathrm{\Delta }\subseteq E$.)

So let ${\gamma }_1,{\gamma }_2:G\to Q$ satisfy${{\gamma }_i|}_E=p_i$and${{\gamma }_2|}_{G\setminus E}=p_i={{\gamma }_2|}_{G\setminus E}.$Let $z\in G$.If $z\in \mathrm{\Delta }𝒩$,then $F_{𝒜}({\gamma }_1)(z)=F_{𝒜}({\gamma }_2)(z)$,because by construction${{\gamma }_i|}_{z𝒩}={c_i|}_{z𝒩};$if$z\in G\setminus \mathrm{\Delta }𝒩,$then $F_{𝒜}({\gamma }_1)(z)=F_{𝒜}({\gamma }_2)(z)$ as well,because by construction${{\gamma }_1|}_{z𝒩}={{\gamma }_2|}_{z𝒩}.$Since ${\gamma }_1$ and ${\gamma }_2$ are arbitrary,$p_1$ and $p_2$ are mutually erasable. $\mathrm{\square }$