Mapping from set $A$ surjectively onto itself which is not injective.

Question

Let $A$ denote some arbitrary set. Is it possible to construct a non-injective mapping from $A$ surjectively onto itself? This is a relatively elementary question; however, it's a concept I've never had a concrete example for. If somebody could provide something quick, I would really appreciate it! Shockingly, I couldn't find any duplicate on this site...unless I'm not looking hard enough.

(Also, as far motivation is concerned: I am curious to determine whether the First Fundamental Homomorphism Theorem for Rings is an "if and only if" statement; i.e. $A\cong B$ if and only if $ker(\mu)=\{1\}$ for some ring homomorphism $\mu:A\to B$. It is for this reason I have chosen to include the tag of "group-theory" to this post.)

Answer 1

I assume you mean, can we have a surjection $A\to A$ that is not injective. Then the answer is yes. By counting reasons, you need that $A$ is infinite, but then it is always possible.

For a simple example, take $\Bbb{N}\to \Bbb{N}$ given by $n\mapsto \lceil\frac{n}{2}\rceil$, i.e. we map $1$ and $2$ to $1$, $3$ and $4$ to $2$, $5$ and $6$ to $3$ and so on.

For your second question, it is true that two rings $G,H$ are isomorphic if and only if there exists a surjective ring homomorphism $\mu:G\to H$ with trivial kernel. But note that it does not mean that for two isomorphic rings $G,H$, any surjective homomorphism must have trivial kernel, or that any homomorphism with trivial kernel must be surjective.

As an example of the latter, consider $\Bbb{Z}\to \Bbb{Z}$ given by multiplication by 2. This is a group homomorphism (admittedly not a ring homomorphism but you get the idea), and it must be injective, i.e. trivial kernel, but its image are all the even integers, so it is not surjective.

Answer 2

Theorem. Let $A$ be a set. Consider the following statements:

1. $A$ can be bijected with a proper subset of itself.
2. There exists a function $f\colon A\to A$ that is one-to-one but not surjective.
3. There exists a function $g\colon A\to A$ that is surjective but not injective.

Then 1 is equivalent to 2, and 1 implies 3. If we assume the Axiom of Choice, then 3 implies 2 (and hence 1).

Proof. 1$\implies 2$. Let $B\subseteq A$, $B\neq A$, and assume that $h\colon A\to B$ is a bijection. If $i\colon B\to A$ is the subset inclusion, then $f=i\circ h$ is one-to-one but not surjective.

2$\implies$ 1. Let $f\colon A\to A$ be one to one and not surjective, and let $B=f(A)$. Then $B$ is ap roper subset of $A$, and the co-restriction of $f$ to $B$ (that is, the map $h\colon A\to B$ given by $h(a)=f(a)$ for all $a\in A$) is a bijection of $A$ with a proper subset of itself.

1$\implies$3. Let $B\neq A$ be a proper subset of $A$ (which means $A\neq \varnothing$) and a bijection $h\colon A\to B$. Let $a_0\in A$, and define $g\colon A\to A$ by $$g(a) = \left\{\begin{array}{ll} h^{-1}(a) &\text{if }a\in B,\\ a_0 &\text{otherwise.} \end{array}\right.$$ Then $g$ is surjective, since $h^{-1}(B)=A$; and it is not injective: given any $x\in A$, $x\notin B$ (which exists since $B$ is a proper subset of $A$), we have
$$g(x) = a_0 = h^{-1}(h(a_0)) = g(h(a_0)).$$ But $h(a_0)\in B$ and $x\notin B$, so $h(a_0)\neq x$. Thus, $g$ is not injective.

Finally, assume the Axiom of Choice, and let $g\colon A\to A$ be a function that is surjective but not injective. By the Axiom of Choice, every surjection has a right inverse $h$, so there exists $h\colon A\to A$ such that $g\circ h = \mathrm{id}_A$. Let $B=\mathrm{Im}(h) = h(A)$. Note that because $g\circ h$ is bijective, then $h$ is injective, so $h\colon A\to B$ is a bijection. In addition, $B\neq A$: indeed, let $a,a'\in A$ be such that $g(a)=g(a')$. If $a$ and $a'$ are both in $B$, then there exist $u,v\in A$ such that $h(u)=a$, $h(v)=a'$. Then $$u = g(h(u)) = g(a) = g(a') = g(h(v)) = v,$$ so $a = h(u) = h(v) = a'$. Now let $a,a'\in A$ be such that $a\neq a'$ and $g(a)=g(a')$ (possible, since $g$ is not injective). Then either $a\notin B$ or $a'\notin B$ (or both). So $B\neq A$. Thus, $A$ can be bijected with $B$, which is a proper subset of itself. $\Box$

Note that statement 1 is often taken to be the definition of "infinite set" (or more precisely, of a Dedekind infinite set). Assuming the Axiom of Choice, such functions exist if and only if the set $A$ is infinite.