# pre-injectivity

Let $X=\prod_{i\in I}X_{i}$ be a Cartesian product. Call two elements $x,y\in X$ almost equal if the set $\Delta(x,y)=\{i\in I\mid x_{i}\neq y_{i}\}$ is finite. A function $f:X\to X$ is said to be pre-injective if it sends distinct almost equal elements into distinct elements, i.e., if $0<|\Delta(x,y)|<\infty$ implies $f(x)\not=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 general that a composition of pre-injective functions is itself pre-injective.

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

Pre-injectivity of cellular automata can be characterized via 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 $\mathcal{A}=\langle Q,\mathcal{N},f\rangle$ on $G$ if for any two configurations $c_{1},c_{2}:G\to Q$ such that $\left.{c_{i}}\right|_{E}=p_{i}$ and $\left.{c_{1}}\right|_{G\setminus E}=\left.{c_{2}}\right|_{G\setminus E}$ one has $F_{\mathcal{A}}(c_{1})=F_{\mathcal{A}}(c_{2})$.

###### Lemma 1

For a cellular automaton $\mathcal{A}=\langle Q,\mathcal{N},f\rangle,$ the following are equivalent.

1. 1.

$\mathcal{A}$ has no mutually erasable patterns.

2. 2.

$\mathcal{A}$ is pre-injective.

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

 $E=\Delta\mathcal{N}^{2}=\{g\in G\mid\exists z\in\Delta,u,v\in\mathcal{N}\mid g% =zuv\}\;:$ (1)

we shall prove that $p_{1}=\left.{c_{1}}\right|_{E}$ and $p_{2}=\left.{c_{2}}\right|_{E}$ are mutually erasable. (They surely are distinct, since $\Delta\subseteq E$.)

So let $\gamma_{1},\gamma_{2}:G\to Q$ satisfy $\left.{\gamma_{i}}\right|_{E}=p_{i}$ and $\left.{\gamma_{2}}\right|_{G\setminus E}=p_{i}=\left.{\gamma_{2}}\right|_{G% \setminus E}.$ Let $z\in G$. If $z\in\Delta\mathcal{N}$, then $F_{\mathcal{A}}(\gamma_{1})(z)=F_{\mathcal{A}}(\gamma_{2})(z)$, because by construction $\left.{\gamma_{i}}\right|_{z\mathcal{N}}=\left.{c_{i}}\right|_{z\mathcal{N}};$ if $z\in G\setminus\Delta\mathcal{N},$ then $F_{\mathcal{A}}(\gamma_{1})(z)=F_{\mathcal{A}}(\gamma_{2})(z)$ as well, because by construction $\left.{\gamma_{1}}\right|_{z\mathcal{N}}=\left.{\gamma_{2}}\right|_{z\mathcal{% N}}.$ Since $\gamma_{1}$ and $\gamma_{2}$ are arbitrary, $p_{1}$ and $p_{2}$ are mutually erasable. $\Box$

## References

• 1 Ceccherini-Silberstein, T. and Coornaert, M. (2010) Cellular Automata and Groups. Springer Verlag.
• 2
Title pre-injectivity Preinjectivity 2013-03-22 19:22:04 2013-03-22 19:22:04 Ziosilvio (18733) Ziosilvio (18733) 4 Ziosilvio (18733) Definition msc 37B15 msc 68Q80 mutually erasable patterns (cellular automaton)