# Ax–Grothendieck and the Garden of Eden

It's an obvious consequence of the pigeonhole principle that any injective function over finite sets is bijective. But there are some similar results in different areas of mathematics that apply to less-finite settings.

In algebraic geometry, the Ax–Grothendieck theorem states (if I have it correctly) that any injection from an algebraic variety over an algebraically closed field to itself is bijective; the standard proof involves some sort of local-global principle together with the same fact over finite fields.

In the theory of cellular automata, the Garden of Eden theorem states that any injective cellular automaton (over an integer grid of some fixed finite dimension, say) is bijective; the standard proof involves again the same fact for finite sets of cells together with a limiting argument that shows that for large enough bounded regions of an unbounded grid, the boundary of the region has negligible effect compared to the interior.

Is there some way of viewing these three injective-bijective statements (or others) as instances of a single more general phenomenon?

• Another example are co-Hopfian groups en.wikipedia.org/wiki/Hopfian_group. For example, $\mathbb{Z}/p^{\infty}$ is co-Hopfian. More generally, we may ask which objects $x$ of a category have the property that every monomorphism $x \to x$ is an isomorphism. – Martin Brandenburg Mar 18 '11 at 8:26
• David: In fact Garden of Eden says more: If $G$ is an amenable group and $\tau\colon A^G\rightarrow A^G$ is an algebraic CA on $G$ then $\tau$ is pre-injective iff $\tau$ is surjective. Pre-injective means, if $x_1,x_2$ are two almost equal(differ on a finite set) configurations then $f(x_1)=f(x_2).$ so Martin's generalization is too general. – Niyazi Mar 18 '11 at 9:42
• An injective endomorphism of a finite-dimensional vector space is bijective.:) If you reverse the arrows, this statement can be widely generalized.:) – Mikhail Bondarko Mar 18 '11 at 12:45
• Wikipedia tells me that the Garden of Eden theorem uses Konig's theorem -- I think of Konig's theorem as quite close to the compactness theorem in logic, which is also the finite-to-infinite tool used in Ax's model-theoretic proof that injective polynomial maps from affine n-space to itself are surjective. – Marty Mar 18 '11 at 15:09
• Have you looked at the paper of Misha Gromov titled:Endomorphisms of symbolic algebraic varieties.It is in the first issue of Journal of European mathematical society.You can also find a copy in Gromov's home page at IHES. – Mohan Ramachandran Mar 18 '11 at 15:16

See the recent paper "On algebraic cellular automata", for a proof of how to derive the Garden of Eden theorem from the Ax-Grothendieck theorem. This is indeed in the spirit of Gromov's paper that Mohan mentioned in the comments. This paper is were he introduced Sofic groups. The story as I understand it is: The Ax-Grothendieck theorem tells us that every regular algebraic map from a complex algebraic variety to itself can not be a strict embedding. If one takes a power of the variety indexed by a group G, then the analogous result holds for G-equivariant pro-regular maps when the group G satisfies some conditions (can be approximated by "nice" groups). Gromov calls this property "surjunctive". The original GOE theorem is about $G=\mathbb{Z}^n$. It turns out that this works for any amenable group, and more generally for sofic groups, those groups that can be approximated by amenable groups.

• Thanks! I added the reference to the Wikipedia GoE article. – David Eppstein Mar 19 '11 at 19:46

Another example is a monorphisms (i.e. injective) between finite dimentional vectorial spaces . I think taht a general key is the general concept of algebraic dependent (see matroid theory), free system and bases, this is a "generalization " of the usual vector spaces (linear algebra) concept, for example you can generalize this "dependence theory" for analyze the trascendence degree for field extension .

If this "general theory of dependence" is applicable, then a injective morphism maps a base (in the domain) to a free system (in the codomain) and a free system of the some cardinality of a base (all bases have the some cardinality, and we can call it the dimention) is a base, then a base generate the space and the map is surjective too.

In the theory of von Neumann algebras, there is a similar phenomenon.

Let $M$ be a type $II_1$-factor. That is, it's an infinite dimensional von Neumann algebra with center $\mathbb C$, and with an (everywhere defined) trace $tr:M\to \mathbb C$.

Then there is a complete invariant of $M$-modules called the von Neumann dimension. This invariant takes values in $\mathbb R_{\ge 0}\cup \{\infty\}$ and can take any value in that set. It has the property that any isometric map $H_1 \to H_2$ between modules of the same dimension is actually a unitary isomorphism (except if the von Neumann dimension is $\infty$, in which case, that's not true).

In particular, if $H$ is an $M$-module of finite von Neumann dimension, then any isometry (not assumed to be surjective) is actually a unitary isomorphism.