# Injectivity implies surjectivity

In some circumstances, an injective (one-to-one) map is automatically surjective (onto). For example,

Set theory
An injective map between two finite sets with the same cardinality is surjective.

Linear algebra
An injective linear map between two finite dimensional vector spaces of the same dimension is surjective.

General topology
An injective continuous map between two finite dimensional connected compact manifolds of the same dimension is surjective.

Are you aware of other results in the same spirit?

Is there a general framework that somehow encompasses all these results?

• The set theory case really implies the other two. Finite dimensional spaces have their linear maps fully decided by behavior on some finite set, and compactness is some sort of generalized finiteness of a topology. Jul 4, 2017 at 9:41
• Gottschalk conjecture: fix a group $G$ and a finite alphabet $A$. Then (injective $\Rightarrow$ surjectivity) holds for any continuous $G$-equivariant map $A^G\to A^G$. Holds when $G$ is sofic, which includes most known groups.
– YCor
Jul 4, 2017 at 9:46
• The second example can be extended to operators of the form Identity + Compact operator, on any Banach space, by Fredholm alternative Jul 4, 2017 at 10:06
• @FernandoMartin more generally any surjective endomorphism of a noetherian module over an arbitrary ring is injective. This has a counterpart in the required direction: any injective endomorphism of an artinian module over an arbitrary ring is surjective.
– YCor
Jul 4, 2017 at 16:14
• Useful keyword: a module over something / group / whatever is cohopfian (or co-Hopfian, or have the co-Hopf property) if all its injective endomorphisms are automorphisms.
– YCor
Jul 4, 2017 at 16:16

A famous result in this spirit is the Ax-Grothendieck theorem, whose statement is the following:

Theorem. If $f \colon \mathbb{C}^n \to \mathbb{C}^n$ is an injective polynomial function then $f$ is bijective.

• There is a generalisation to maps $f \colon X \to X$ where $X$ is any variety over an algebraically closed field $k$. Jul 4, 2017 at 10:27
• I wouldn't expect Grothendieck to state it just for the complex numbers!
– YCor
Jul 4, 2017 at 16:11
• @YCor: Grothendieck's version is probably about radicial endomorphisms of finitely generated $S$-schemes, cf. EGA IV$_3$, Prop. 10.4.11. Jul 4, 2017 at 19:50

There is an improvement of the answer of Joseph Van Name which I feel is much more in the spirit in the question asked:

Let $(X,d)$ be a compact metric space, and assume that the mapping $f\colon X\to X$ does not decrease distances, that is $d(f(x),f(y))\ge d(x,y)$ for all $x,y\in X$. Then $f$ is a bijection.

Sketch of a proof. The proof I came up with long ago consists of two lemmas.

Lemma 1. A mapping $f$ as above must be an isometry.

Proof. Let $(x,y)\in X\times X$, and consider the sequence $(f^k(x),f^k(y))$. Since $X$ is compact, there is a convergent subsequence $\{(f^{k_i}(x),f^{k_i}(y))\}$. In particular, the sequence $\{f^{k_i}(x)\}$ is convergent, which implies that $\lim_{j>i\to\infty}d(f^{k_i}(x),f^{k_j}(x))=0$, and hence (since $f$ does not decrease distances) $\lim_{j>i\to\infty}d(x,f^{k_j-k_i}(x))=0$. The same is true for the sequence of the second coordinates. Thus, $(x,y)$ is a limit point of the sequence $\{(f^k(x),f^k(y))\}$. Suppose that $d(f(x),f(y))>d(x,y)$ for some $x,y\in X$. Then $d(f(x),f(y))-d(x,y)>\epsilon$ for some $\epsilon>0$. Then $d(f^n(x),f^n(y))-d(x,y)>\epsilon$ for all $n$, which is a contradiction.

Lemma 2. An isometry of a compact metric space is a bijection.

Proof. Let $x\in X$. Let us consider the sequence $\{f^n(x)\}$. This sequence has a a convergent subsequence $\{f^{k_i}(x)\}$. This implies that $\lim_{j>i\to\infty}d(f^{k_i}(x),f^{k_j}(x))=0$, and hence (since $f$ is an isometry) $\lim_{j>i\to\infty}d(x,f^{k_j-k_i}(x))=0$. Thus, $x$ is a limit point of the sequence $\{(f^{k_j-k_i}(x)\}$, in particular $x$ is a limit point of $f(X)$. But an isometry is continuous, and the image of a compact space under a continuous map is a compact, thus $x\in f(X)$, so $f$ is surjective. Since $f$ is manifestly injective, the statement is proved.

• @MarkWildon done! Jul 6, 2017 at 2:23
• @Cœur : I wish! Alas I do not know a proper reference for this. I heard the statement from Valery Ryzhikov (a Russian mathematician primarily working with dynamical systems) about 15 years ago, and then came up with the proof documented above. Jul 7, 2017 at 3:53
• One reference for this is Burago, Burago and Ivanov's book "A course in metric geometry", Theorems 1.6.14 and 1.6.15. Jul 8, 2017 at 2:10
• I think we may consider it a folk result --I myself had a proof of an analogous statement back in the 90's: A 1-Lipschitz map on a compact metric space is surjective iff it is isometric. (btw, a friend of mine named it "the Wedding Blanket theorem" for reasons that should be apparent to whoever shared a bed with a partner in winter ;) ) Jul 8, 2017 at 9:34
• Another proof. Fix $r>0$, take the maximal $r$-distant set $A$ (i.e., $d(a,b)\ge r$ for $a\ne b$ in $A$) and the maximal $\sum_{a,b\in A} d(a,b)$. Then $f(A)$ is a better $r$-distant set unless $f|_A$ is isometry. So, $A$ and $f(A)$ are $r$-nets (else they are not maximal $r$-distant sets) and for any two points $x,y$ we may find points $f(a),f(b)$ in $f(A)$ such that $d(f(a),f(x)), d(f(b),f(y))\le r$, thus $d(a,x),d(b,y)\le r$ and both $d(x,y)$, $d(f(x),f(y))$ are within $2r$ from $d(a,b)=d(f(a),f(b))$. Since $r$ was arbitrary, $f$ is isometry, also $f(X)$ is dense in $X$, and compact. Done Jul 10, 2017 at 16:51

Suppose $(X,d)$ is a compact metric space. Then every mapping $f:X\rightarrow X$ such that $d(x,y)=d(f(x),f(y))$ is always bijective.

In group theory being "Hopfian" is the reverse property: every epimorphism from the group to itself is an automorphism. There are lots of Hopfian groups, for example finitely generated residually finite groups (includes the free groups) and the rationals (being thought of as an additive group).

Banach space theory:

Antonio Avilés and Piotr Koszmider constructed an infinite dimensional Banach space of continuous functions $C(K)$ such that every one-to-one operator $T : C(K) \to C(K)$ is onto.

Minor bit of self-promotion: if $\Gamma$ is a (discrete) group and $f\in\ell^1(\Gamma)$ then the natural convolution operator $T_f:\ell^\infty(\Gamma)\to \ell^\infty(\Gamma)$ has the "injective implies surjective" property. No soficity assumptions needed, despite the superficial similarity to the Gottschalk conjecture!

Probably also worth noting that "injective with closed range implies surjective" holds for convolution operators on $\ell^p(\Gamma)$ with $1<p<\infty$ if $\Gamma$ is an amenable group, and for convolution operators on $\ell^2(\Gamma)$ without any restriction on $\Gamma$. It fails for $p=1$ and $\Gamma$ containing a nonabelian free subgroup, by a construction of G. A. Willis.

• "Injective with closed range implies surjective" holds also for convolution operators on $L_1(G)$, where $G$ is a locally compact abelian group. Jul 10, 2017 at 7:18

Regarding the "general framework" part of your question, if we work in a general category with some notion of "dimension" or "size" and replace "injective" with "monic" then we can rephrase this condition as:

"Every proper subobject of an object is of strictly smaller dimension than the original object."

Given that the "dimensions" are, say, non-negative integers, this implies a descending chain condition on subobjects. In turn, we can (sort of) recover our notion of dimension by taking the length of the longest descending chain of subobjects.

Looking at this condition, it seems reasonable to assume it might be called a "noetherian category," and in fact Googling turns up such a definition on nlab (modulo some technical set theoretic condition).

So we can say that the categories of finite sets, finite dimensional vector spaces, and finite dimensional compact manifolds are all noetherian. In fact, we can say more: namely, that they are precisely the subcategories of noetherian objects in the categories of sets, vector spaces, and compact manifolds, respectively.

• Nitpick: your final para seems to suggest that the category of finite sets is a noetherian object in the category of sets. This does not seem quite right Jul 8, 2017 at 0:15
• @Yemon Choi: I've refined the grammar of that sentence now, thanks. Jul 8, 2017 at 4:18

An injective graph homomorphism between two connected $d$-regular graphs is bijective.

Yes, there's a general framework encompassing a variety of results like this. It encompasses at least your first two results (on sets and vector spaces) and the fact that any isometry of a compact metric space into itself is surjective.

The general framework I'm referring to is the theory of the eventual image', laid out in two posts at the $n$-Category Café from 2011: post 1, post 2.

A fully faithful tensor functor between fusion categories with the same Frobenius-Perron dimension is dominant, thus an equivalence.

Theorem. Let $R$ be a commutative ring with $1$, and let $A$ be a finitely generated $R$-algebra. Then, any surjective $R$-algebra endomorphism of $A$ is bijective.

This is proven non-constructively (using Noetherianness) in math.stackexchange #1221213.

Question 1. Is there a constructive proof?

Of course, the theorem above is a multiplicative analogue of the known fact that any surjective endomorphism of a finitely generated $R$-module is bijective. That latter fact has a strengthening due to Orzech (see my A constructive proof of Orzech’s theorem and the references there in), stating that if $M$ is a finitely-generated $R$-module, if $N$ is an $R$-submodule of $M$, and if $f : N \to M$ is a surjective $R$-module homomorphism, then $f$ is bijective. I am also wondering if an multiplicative analogue exists:

Question 2. Let $R$ be a commutative ring with $1$, and let $A$ be a finitely generated $R$-algebra. Let $B$ be an $R$-subalgebra of $A$. Is it true that any surjective $R$-algebra homomorphism $B \to A$ is bijective?

(If you have an answer-length answer to any of these questions, let me know and I'll open a question.)

You might find interesting the Cantor-Schroeder-Bernstein property.

The most interesting result contained in the pdf, in my opinion, is the following.

If a category $$\mathcal{K}$$ has a faithful functor $$F : \mathcal{K} \to \text{FinSet}$$ to the category of finite sets, then $$\mathcal{K}$$ has the CSB property.

Proof is quite trivial but this sets a quite interesing framework in which the question finds its sense.

A locally isometric (i.e., locally injective and with the metric on one pulling back to the metric on the other) map between connected, complete Riemannian manifolds of the same dimension is a surjection.

The Dixmier conjecture is an interesting example. (Every endomorphism of the Weyl algebra is automatically injective, so it's equivalent to asking whether injectivity implies surjectivity.)

There is a famous conjecture in group theory: group rings are directly finite, i.e. if G is a group, k is a field and a and b are elements of k[G] then ab=1 implies ba=1.

Your second example is a special case of this conjecture, essentially equivalent to the case when G is a finite group (and your first example is a special case of the second one, by applying a suitable Hom functor).

The conjecture is due to Kaplansky. There are many partial results, for example Kaplansky showed the conjecture when k is the field of complex numbers and G is arbitrary, and I think but I can be wrong Elek and Szabo showed it for arbitrary k when G is a sofic group.

• Hi Łukasz, my understanding is that GE+ES did indeed resolve this for sofic groups and arbitrary fields arxiv.org/abs/math/0305440 Jul 9, 2017 at 21:38
• the result is actually true for a group ring $R[G]$ with G sofic and R a left Noetherian ring (see arxiv.org/abs/1510.07655 ) Jul 9, 2017 at 22:34

Suppose that $U$ is an ultrafilter over a set $X$. Then the only endomorphism $f:(X,U)\rightarrow(X,U)$ in the category of ultrafilters is the identity morphism.

There is an example of this in stable homotopy theory, related to the famous Generating Hypothesis,' conjectured by Freyd (and still open as far as I know!). For finite complexes $$X$$ and $$Y$$, the map from the stable homotopy classes of (pointed) maps from $$X$$ to $$Y$$ can be related to the algebraic maps between stable homotopy groups via $$[ X, Y]^S \to \mathrm{Hom}(\pi_*^S(X), \pi_*^S(Y) ).$$ The Generating Hypothesis says that this function is always injective finite complexes $$X$$ and $$Y$$; and it is a theorem of Freyd that if it is true, then the map is always surjective, too.

It has been long enough since I read up on this that I can't remember if the surjectivity follows on a pointwise basis, or whether you need the full conjecture to get the implication for a particular $$X$$ and $$Y$$.

I did not find in the answers the following known claim which is dual to Vladimir's answer.

If $(X,d)$ is a metric compact set and a surjection $f$ from $X$ to $X$ is 1-Lipschitz, i.e., $d(f(x),f(y))\leqslant d(x,y)$, then $f$ is bijection and, moreover, isometry.

Proof. Fix $r>0$ and a minimal $r$-net $A$ in $X$ with minimal $\sum_{a,b\in A} d(a,b)$. Then $f(A)$ is an $r$-net on $f(X)=X$, and by minimality $f$ is isometry on $A$. For any $x,y$ in $X$ find $a,b$ in $A$ such that $d(x,a),d(y,b)\leqslant r$, then $$d(x,y)\geqslant d(f(x),f(y))\geqslant d(f(a),f(b))-d(f(x),f(a))-d(f(b),f(y))\geqslant \\ \geqslant d(a,b)-d(x,a)-d(b,y)\geqslant d(x,y)-2d(x,a)-2d(b,y)\geqslant d(x,y)-4r.$$ SInce $r$ was arbitrary, we get that $f$ is isometry.

The property that injectivity implies identity or at least injectivity implies surjectivity may arise in algebraic structures that have some form of nilpotence. Let me give an example that has arisen in my work on self-distributivity.

For this answer, suppose that $$(X,*,1)$$ satisfies the identities $$x*(y*z)=(x*y)*(x*z),x*1=1,1*x=x.$$ Define the right powers by letting $$x^{[1]}=x$$ and $$x^{[n+1]}=x*x^{[n]}$$. We say that $$(X,*,1)$$ is right nilpotent if for all $$x$$, there is some $$n$$ where $$x^{[n]}=1$$. If $$a\in X$$, then define the mapping $$L_{a}:X\rightarrow X$$ by letting $$L_{a}(x)=a*x$$. Then the mapping $$L_{a}$$ is an endomorphism, so we shall call $$L_{a}$$ a basic inner endomorphism. The monoid $$\mathrm{Inn}(X)$$ generated by $$(L_{a})_{a\in X}$$ is called the inner endomorphism monoid of $$(X,*)$$ and the elements in $$\mathrm{Inn}(X)$$ are known as inner endomorphisms.

Proposition: If $$(X,*)$$ is a right nilpotent self-distributive algebra, then every injective inner endomorphism is the identity function. Furthermore, if $$L_{a}:X\rightarrow X$$ is an injective inner endomorphism, then $$a=1$$.

Proof: Suppose that $$a\neq 1$$. Then $$L_{a}^{n}(a)=a^{[n+1]}=1=L_{a}^{n}(1)$$. Therefore, since $$L_{a}^{n}$$ is not injective, the mapping $$L_{a}$$ is not injective either. Therefore, if $$L_{a}$$ is injective, then $$a=1.$$ If $$f$$ is an injective inner endomorphism, then $$f=L_{a_{1}}\circ\dots\circ L_{a_{n}}$$ for some $$a_{1},\dots,a_{n}$$, but since $$f$$ is injective, so are each $$L_{a_{i}}$$, so $$a_{1}=\dots=a_{n}=1$$, and therefore $$f$$ is the identity function. QED

Examples of right nilpotent self-distributive algebras include the quotient algebras of rank-into-rank embeddings $$\mathcal{E}_{\lambda}/\equiv^{\gamma}$$ (and similar algebraic structures), and algebras $$(X,\rightarrow,1)$$ such that $$\rightarrow$$ is the Heyting operation in a Heyting algebra, and the algebras $$(X,*,1)$$ where there Is a function $$f$$ where $$x*y=f(y)$$ for each $$x,y$$ and where $$f(1)=1$$ and for each $$x\in X$$ there is an $$n$$ with $$f^{n}(x)=1.$$