# Can it be shown that a set X is infinite if and only if there exists some $F:X\to X$ that is an injection but not a surjection?

If the function is not surjective, then at least one element of the codomain has no pre-image. However, because F is a function, every element in the domain is mapped to something in the codomain. But since we know that F is injective, then we can't use an element in the codomain more than once in our mapping. That must mean that there is an infinite set of elements in the codomain if we can "skip" one and still be injective. I'm having trouble, however, translating my thoughts into a proof format.

The Axiom of Choice is not available to me for the purposes of this proof. Infinite for this question would be that it as has a countably infinite subset.

Thank you to all who addressed my question, both for your help and patience.

## 2 Answers

The definition of infinite can vary. It follows from the fact that we have many definitions of finite, and without the axiom of choice they are not necessarily equivalent.

If you have defined "infinite" as "having a countably infinite subset", then there is no need to use the axiom of choice. Use the fact that $n\mapsto n+1$ is an injection which is not a surjection, and conclude the existence of such map; in the other direction let $f$ be a non-surjective injection and let $a$ be an element not in its range, show that $f^n(a)$ is a countably infinite subset of $A$, and conclude that $A$ is infinite. This sort of definition is called Dedekind-infinite.

If you have defined "infinite" as "not equipotent with a finite initial segment of the natural numbers", then you cannot prove this results without the axiom of choice. But the proofs that you can't are difficult and technical. In modern terms, by the way, the definition of infinite is this one, and when not allowing the axiom of choice it is important to be precise about which definition you are using.

Not without some part of the axiom of choice. It’s consistent with $\mathsf{ZF}$ that there be infinite, Dedekind-finite sets, i.e., sets that are not finite but that do not admit an injection to a proper subset.

Every Dedekind-infinite set is easily seen to be infinite. The converse follows from the axiom of countable choice, though I believe that it’s actually strictly weaker.

• Your belief is correct. It is weaker than countable choice. – Asaf Karagila Apr 28 '13 at 10:11