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 $\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-injective if 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 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 $𝒜=⟨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 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_{𝒜}(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 }$

Title	pre-injectivity
Canonical name	Preinjectivity
Date of creation	2013-03-22 19:22:04
Last modified on	2013-03-22 19:22:04
Owner	Ziosilvio (18733)
Last modified by	Ziosilvio (18733)
Numerical id	4
Author	Ziosilvio (18733)
Entry type	Definition
Classification	msc 37B15
Classification	msc 68Q80
Defines	mutually erasable patterns (cellular automaton)