Dedekind-infinite set

Encyclopedia : D : DE : DED : Dedekind-infinite set

In mathematics, a set A is Dedekind-infinite if some proper subset B of A is equinumerous to A. Explicitly, this means that there is a bijective function from A onto some proper subset B of A. A set is Dedekind-finite if it is not Dedekind-infinite.

Contents

1 Comparison with the usual definition of infinite set
2 Dedekind-infinite sets in '''ZF'''
3 Relation to AC and ACω
4 History
5 References

Comparison with the usual definition of infinite set

This definition of "infinite set" should be compared and contrasted to the usual definition: a set A is finite if A is empty, or if there is a positive integer n such that A is equinumerous to the set . Explicitly, this means that there is a bijection between A and some member of ω, where ω is defined to be the intersection of all sets which contain the empty set and are closed under the ordinal successor operation. A set is infinite if it is not finite.

During the latter half of the 19th century, most mathematicians simply assumed that a set is infinite if and only if it is Dedekind-infinite. However, this equivalence cannot be proved with the axioms of Zermelo-Fraenkel set theory without the axiom 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 is strictly weaker than the axiom of countable choice (CC). (See the references below.)

Dedekind-infinite sets in ZF

The following conditions are equivalent in ZF. In particular, note that all these conditions can be proved to be equivalent without using the AC.

A is Dedekind-infinite.
There is a function f: A → A which is injective but not surjective.
There is an injective function f : N → A, where N denotes the set of all natural numbers.
A has a denumerable subset.

Every Dedekind-infinite set A also satisfies the condition

There is a function f: A → A which is surjective but not injective,

but it is not provable (in ZF without the AC) that this condition implies that A is Dedekind-infinite. (For example, if B is an infinite but Dedekind-finite set, and A is the set of finite one-to-one sequences from B, then "drop the last element" is a surjective but not injective function from A to A, yet A is Dedekind finite.)

Also, the following statements concerning Dedekind-infinite sets are provable in ZF.

Every Dedekind-infinite set is infinite.
Every infinite, well-ordered set is Dedekind-infinite.

Relation to AC and ACω

Since every infinite, well-ordered set is Dedekind-infinite, and since the AC is equivalent to the well-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 of ZF in which there exists an infinite set with no denumerable 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 CC (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 of ZF in which every infinite set is Dedekind-infinite, yet the CC fails.

History

The term is named after the German mathematician Richard Dedekind, who first explicitly introduced the definition. It is notable that this definition was the first definition of "infinite" which did not rely on the definition of the natural numbers. Although such a definition was known to Bernard Bolzano, he was prevented from publishing his work in any but the most obscure journals by the terms of his political exile from the University of Prague in 1819. It has also been argued that his treatment of the matter was circular and ambiguous in presentation. Moreover, Bolzano's definition was more accurately a relation which held between two infinite sets, rather than a definition of an infinite set per 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 after Ernst Zermelo formulated the AC explicitly. The existence of infinite, Dedekind-finite sets was studied by Bertrand Russell and Alfred North Whitehead in 1912; these sets were at first called mediate cardinals or Dedekind 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.

References

Moore, Gregory H., Zermelo's Axiom of Choice, Springer-Verlag, 1982 (out-of-print), ISBN 0-387-90670-3, in particular pp. 22-30 and tables 1 and 2 on p. 322-323
Jech, Thomas J., The Axiom of Choice

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.