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