# Dedekind's theorem

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.

-

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

-
Good point Joel. –  Ali Enayat Jun 18 '11 at 18:19

EDIT NOTE: Thanks to Asaf Karagila for pointing out an error in the previous set-up; now the emphasis is put on finiteness vs Dedekind finiteness.

The notion of a finite ordinal is quite modern, and was only articulated after Cantor's invention of set theory and his investigations of various kinds of linearly ordered sets, especially well-ordered ones. Also

Moreover, in our modern axiomatic view of set theory, Dedekind's characterization of finiteness only works in the presence of the axiom of choice.

More specifically, let us define a set $X$ to be Dedekind finite provided there is no bijection between $X$ and a proper subset of $X$; and to be finite iff there is no $n \in \Bbb{N}$ such that $X$ has cardinality $n$. We also define $X$ is infinite iff $X$ is not finite. Then we have:

(1) The implication "If $X$ is finite, then $X$ is Dedekind finite" is provable in $ZF$ (Zermelo-Fraenkel set theory without the axiom of choice). This implication is one of the versions of the Pigeon-hole principle (see Joel Hamkins' answer).

(2) The implication "If $X$ is Dedekind finite, then $X$ is finite" is provable in $ZFC$ = $ZF$ + $AC$ [the axiom of choice].

(3) However, the implication "If $X$ is Dedekind finite, then $X$ is finite" is not provable in $ZF$. This was established first by Paul Cohen, in the early 1960's, as one of the first impressive exhibits of his "forcing" technology. Indeed, as shown by Cohen, in the absence of the axiom of choice, it is possible to have an infinite Dedekind finite subset of $\Bbb{R}$. It is not hard to see that $X$ is not Dedekind finite iff $\Bbb{N}$ can be injected into $X$; so in Cohen's model there is an infinite subset of $\Bbb{R}$ into which $\Bbb{N}$ cannot be injected.

Finally, according to the source below [p.45, footnote 4], Dedekind's definition was also independently proposed by C.S. Pierce.

Fraenkel, Abraham A.; Bar-Hillel, Yehoshua; Levy, Azriel Foundations of set theory. North-Holland, 1973.

PS. Euclid's "the whole is greater than a part" - one of the five "common notions" in the Elements - might be been argued to be a precursor of Dedekind's theorem. Also, the idea of reducing the notion of cardinality to 1-1 correspondences is referred to as Hume's Principle in some modern philosophical texts, based on Frege's attribution of the principle to the 18th century philosopher David Hume.

-
I am not concerned in this question with infinite sets. I want to know if anyone before Dedekind proved that if you can count a set with numerals and reach a stopping point (i.e. count the oranges in a sack), then such a set cannot be put in bijection with a proper subset. –  Monroe Eskew Jun 18 '11 at 7:47
Also, "finite ordinal" is certainly not modern. The von Neumann ordinals are, and perhaps the terminology, but "numerals" and "counting numbers" are ancient. Von Neumann ordinals are just one very useful kind of numerals for set theory. Arabic, Roman, Chinese, Mayan, etc. numerals are other equally valid numeral systems for the finite case. –  Monroe Eskew Jun 18 '11 at 7:55
@mbsq: While "finite" has been around for a long time, "ordinal" is a modern notion. I have added a PS in light of your comments [in particular, the link to Hume's Principle has a reference to the work of John Mayberry on Aristotle's notion of finiteness]. Also, the other notions of numerals that you mention [Arabic, Roman, ...] are different notational systems, and differ fundamentally from von Neumann's, since the von Neumann definition is not a notational device, but rather, a clever and precise implementation of the Cantor's ordinals and cardinals in modern set theory. –  Ali Enayat Jun 18 '11 at 11:40
Honestly I don't see the difference between "notational systems" for natural numbers and something like von Neumann naturals. When you use Arabic numerals, you construct correspondences between the elements of your notational system and some other objects. This is what you do with von Neumann as well when you measure the size of a set. Traditionally the distinction of ordinals and cardinals is one of order (i.e. I am 5th in line) vs. amount (there are 7 people in line), and these are old common sense notions. –  Monroe Eskew Jun 19 '11 at 5:27
@mbsq: What is common sense in a given historical era could be viewed as heresy or nonsense in a different one, even in mathematics. The notion of ordering, as simple as it strikes you and I, took centuries to explicate. There was no "theory of collections", let alone ordered ones, before Cantor's invention of set theory. The related theory of "properties" was considered as belonging to philosophy, not mathematics. Finally, as far as von Neumann ordinals go, let me just say that they allow Cantor's ordinals/cardinals to be implemented in the $\in$-language of set theory in an elegant manner. –  Ali Enayat Jun 20 '11 at 4:52

Bolzano's work on paradoxes of the infinite may be relevant in this context.

-