# If $f:A\rightarrow A$ is injective but not surjective then $A$ is infinite.

I want to follow from something that peano axioms state about the successor function $s:\Bbb{N}\rightarrow\Bbb{N}$. Axiomatically $s$ is injective and not surjective. Now, $\Bbb{N}$ is infinite, just because it is being "generated" by function $s$. Consider following theorem:

Theorem: Let $A$ be a set. Let there be a function $f:A\rightarrow A$ which is injective but not surjective. Then $A$ is infinite.

We don't want to talk about natural numbers themselves, so we don't use the definition that set $X$ is infinite if there is no bijection $\psi:X\rightarrow\{1,2,...,n\}$. We define infinite set as follows.

Definition: A set $X$ is infinite iff there is a bijection $\varphi:X'\rightarrow X$ where $X'\subsetneq X$ is a proper subset of $X$.

I was wondering if someone could help me (dis)prove this hypothesis. My idea goes like this:

Because $f$ is not surjective, that means $f(A)\subsetneq A$, which shows $f$ is the desired bijection between proper subset of $A$ and $A$ itself. But I'm not quite sure if this is really that trivial.

• "Dedekind finite" and "Dedekind infinite" are the relevant terms here that you can search. – Robert Wolfe Aug 23 '18 at 20:11

You have the good idea. The inverse imge $g:f(A)\rightarrow A$ is a bijection, since $f(A)$ is a proper subset of $A$, it results from the definition of an infinite subset that $A$ is infinite.
• Just to make it clear, we should define $g:A\rightarrow f(A)$ and $g:n\mapsto f(n)$, by definition of $f(A)$, because it is set of all images under $f$, $g$ must be surjective, and $n\mapsto f(n)$ is injective by assumption. – Michal Dvořák Aug 27 '18 at 17:47
If $f$ is not surjective and $A$ is finite, then $n=\mid A\mid\gt m=\mid f(A)\mid$, and therefore $f$ isn't injective...