In "Was sind und was sollen die Zahlen?" Dedekind gives a noncircular
proof of the statement that a set is finite if and only if it cannot be
put in bijective correspondence with a proper subset.  By "circular" I
mean in this context that you should not prove it by simply saying that a
proper subset of a finite set will have a smaller cardinality; this
theorem should be taken as the ground for the well-definedness of the
finite cardinals.


Regarding the "only if" direction, which establishes that finite ordinals
are cardinals, was Dedekind the first to publish a proof of this?  Did
Frege give a proof independently?  Galileo?  Leibniz?  Some medieval monk
perhaps?  It would seem strange if this basic aspect of the concept of
number was not reflected upon for so many centuries.



Dedekind's theorem
Regarding the narrower interpretation of your question, the fact that the finite numbers are not equinumerous with
any proper subset is also expressed as the classical
[pigeon hole
principle](http://en.wikipedia.org/wiki/Pigeonhole_principle).
And for this, the linked Wikipedia article asserts that "the first
formalization of the idea is believed to have been made by
Johann Dirichlet in 1834 under the name Schubfachprinzip
(drawer principle or shelf principle)," and this of course
pre-dates Dedekind.


One can easily prove it by induction on $n$, for if $n$ is
a minimal counterexample, with $f:n\to n$ injective but not
surjective, then one can easily construct a smaller
counterexample by considering and rearranging the action on
one point.


