Inmathematics, a setA isDedekind-infinite (named after the German mathematicianRichard Dedekind) if some propersubsetB ofA isequinumerous toA. Explicitly, this means that there exists abijective function fromA onto some proper subsetB ofA. A set isDedekind-finite if it is not Dedekind-infinite (i.e., no such bijection exists). Proposed by Dedekind in 1888, Dedekind-infiniteness was the first definition of "infinite" that did not rely on the definition of thenatural numbers.[1]
A simple example is, the set ofnatural numbers. FromGalileo's paradox, there exists a bijection that maps every natural numbern to itssquaren2. Since the set of squares is a proper subset of, is Dedekind-infinite.
Until thefoundational crisis of mathematics showed the need for a more careful treatment of set theory, most mathematiciansassumed that a set isinfiniteif and only if it is Dedekind-infinite. In the early twentieth century,Zermelo–Fraenkel set theory, today the most commonly used form ofaxiomatic set theory, was proposed as anaxiomatic system to formulate atheory of sets free of paradoxes such asRussell's paradox. Using the axioms of Zermelo–Fraenkel set theory with the originally highly controversialaxiom of choice included (ZFC) one can show that a set is Dedekind-finite if and only if it isfinite in the usual sense. However, there exists a model of Zermelo–Fraenkel set theory without the axiom of choice (ZF) in which there exists an infinite, Dedekind-finite set, showing that the axioms ofZF are not strong enough to prove that every set that is Dedekind-finite is finite.[2][1] There aredefinitions of finiteness and infiniteness of sets besides the one given by Dedekind that do not depend on the axiom of choice.
A vaguely related notion is that of aDedekind-finite ring.
This definition of "infinite set" should be compared with the usual definition: a setA isinfinite when it cannot be put in bijection with a finiteordinal, namely a set of the form{0, 1, 2, ...,n−1} for some natural numbern – an infinite set is one that is literally "not finite", in the sense of bijection.
During the latter half of the 19th century, mostmathematicians simply assumed that a set is infiniteif and only if it is Dedekind-infinite. However, this equivalence cannot be proved with theaxioms ofZermelo–Fraenkel set theory without theaxiom of choice (AC) (usually denoted "ZF"). The full strength of AC is not needed to prove the equivalence; in fact, the equivalence of the two definitions isstrictly weaker than theaxiom of countable choice (CC). (See the references below.)
A setA isDedekind-infinite if it satisfies any of the following equivalent (overZF) conditions:
it isdually Dedekind-infinite if it satisfies any of the following equivalent (overZF) conditions:
it isweakly Dedekind-infinite if it satisfies any of the following equivalent (overZF) conditions:
and it isinfinite if it satisfies any of the following equivalent (overZF) conditions:
Then,ZF proves the following implications: Dedekind-infinite ⇒ dually Dedekind-infinite ⇒ weakly Dedekind-infinite ⇒ infinite.
There exist models ofZF having an infinite Dedekind-finite set. LetA be such a set, and letB be the set of finiteinjectivesequences fromA. SinceA is infinite, the function "drop the last element" fromB to itself is surjective but not injective, soB is dually Dedekind-infinite. However, sinceA is Dedekind-finite, then so isB (ifB had a countably infinite subset, then using the fact that the elements ofB are injective sequences, one could exhibit a countably infinite subset ofA).
When sets have additional structures, both kinds of infiniteness can sometimes be proved equivalent overZF. For instance,ZF proves that a well-ordered set is Dedekind-infinite if and only if it is infinite.
The term is named after the German mathematicianRichard Dedekind, who first explicitly introduced the definition. It is notable that this definition was the first definition of "infinite" that did not rely on the definition of thenatural numbers (unless one follows Poincaré and regards the notion of number as prior to even the notion of set). Although such a definition was known toBernard Bolzano, he was prevented from publishing his work in any but the most obscure journals by the terms of his political exile from theUniversity of Prague in 1819. Moreover, Bolzano's definition was more accurately a relation that held between two infinite sets, rather than a definition of an infinite setper se.
For a long time, many mathematicians did not even entertain the thought that there might be a distinction between the notions of infinite set and Dedekind-infinite set. In fact, the distinction was not really realised until afterErnst Zermelo formulated the AC explicitly. The existence of infinite, Dedekind-finite sets was studied byBertrand Russell andAlfred North Whitehead in 1912; these sets were at first calledmediate cardinals orDedekind cardinals.
With the general acceptance of the axiom of choice among the mathematical community, these issues relating to infinite and Dedekind-infinite sets have become less central to most mathematicians. However, the study of Dedekind-infinite sets played an important role in the attempt to clarify the boundary between the finite and the infinite, and also an important role in the history of the AC.
Since every infinite well-ordered set is Dedekind-infinite, and since the AC is equivalent to thewell-ordering theorem stating that every set can be well-ordered, clearly the general AC implies that every infinite set is Dedekind-infinite. However, the equivalence of the two definitions is much weaker than the full strength of AC.
In particular, there exists a model ofZF in which there exists an infinite set with nocountably infinite subset. Hence, in this model, there exists an infinite, Dedekind-finite set. By the above, such a set cannot be well-ordered in this model.
If we assume the axiom of countable choice (i. e., ACω), then it follows that every infinite set is Dedekind-infinite. However, the equivalence of these two definitions is in fact strictly weaker than even the CC. Explicitly, there exists a model ofZF in which every infinite set is Dedekind-infinite, yet the CC fails (assuming consistency ofZF).
That every Dedekind-infinite set is infinite can be easily proven in ZF: every finite set has by definition a bijection with some finite ordinaln, and one can prove by induction onn that this is not Dedekind-infinite.
By using theaxiom of countable choice (denotation: axiom CC) one can prove the converse, namely that every infinite setX is Dedekind-infinite, as follows:
First, define a function over the natural numbers (that is, over the finite ordinals)f :N → Power(Power(X)), so that for every natural numbern,f(n) is the set of finite subsets ofX of sizen (i.e. that have a bijection with the finite ordinaln).f(n) is never empty, or otherwiseX would be finite (as can be proven by induction onn).
Theimage of f is the countable set{f(n) |n ∈N}, whose members are themselves infinite (and possibly uncountable) sets. By using the axiom of countable choice we may choose one member from each of these sets, and this member is itself a finite subset ofX. More precisely, according to the axiom of countable choice, a (countable) set exists,G = {g(n) |n ∈N}, so that for every natural numbern,g(n) is a member off(n) and is therefore a finite subset ofX of sizen.
Now, we defineU as the union of the members ofG.U is an infinite countable subset ofX, and a bijection from the natural numbers toU,h :N →U, can be easily defined. We may now define a bijectionB :X →X \h(0) that takes every member not inU to itself, and takesh(n) for every natural number toh(n + 1). Hence,X is Dedekind-infinite, and we are done.
Expressed incategory-theoretical terms, a setA is Dedekind-finite if in thecategory of sets, everymonomorphismf :A →A is anisomorphism. Avon Neumann regular ringR has the analogous property in the category of (left or right)R-modules if and only if inR,xy = 1 impliesyx = 1. More generally, aDedekind-finite ring is any ring that satisfies the latter condition. Beware that a ring may be Dedekind-finite even if its underlying set is Dedekind-infinite, e.g. theintegers.