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.

  • 1
    $\begingroup$ "Dedekind finite" and "Dedekind infinite" are the relevant terms here that you can search. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Michal Dvořák Aug 27 '18 at 17:47

This seems to be an instance of the pigeonhole principle ...

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.