Injectivity implies surjectivity

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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).

Answer 5

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.

Answer 6

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!

Reference: http://cms.math.ca/10.4153/CMB-2010-053-5 or http://arxiv.org/abs/math.FA/0606367

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.

Answer 7

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.

Answer 8

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.

Answer 9

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

Answer 10

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

Answer 11

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.)

Answer 12

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.

Answer 13

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.

Answer 14

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.)

Answer 15

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.

Answer 16

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.

Answer 17

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$.

Answer 18

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.

Answer 19

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.$