Dedekind-infinite set

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.

A vaguely related notion is that of a Dedekind-finite ring. A ring is said to be a Dedekind-finite ring if ab=1 implies ba=1 for any two ring elements a and b. These rings have also been called directly finite rings.

Contents


Comparison with the usual definition of infinite set

This definition of "infinite set" should be compared with the usual definition: a set A is infinite when it cannot be put in bijection with a finite ordinal, namely a set of the form {0,1,2,...,n−1} for some natural number n – an infinite set is one that is literally "not finite", in the sense of bijection.

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.

Every Dedekind-infinite set A also satisfies the following condition:

  • There is a function f: AA which is surjective but not injective.

This is sometimes written as "A is dually Dedekind-infinite". It is not provable (in ZF without the AC) that dual Dedekind-infinity 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.)

It can be proved in ZF that every dually Dedekind infinite set satisfies the following (equivalent) conditions:

  • There exists a surjective map from A onto a countably infinite set.
  • The powerset of A is Dedekind infinite

(Sets satisfying these properties are sometimes called weakly Dedekind infinite.)

It can be shown in ZF that weakly Dedekind infinite sets are infinite.

ZF also shows that every well-ordered infinite set is Dedekind infinite.

Relation to the axiom of choice

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 (unless one follows Poincaré and regards the notion of number as prior to even the notion of set). 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. 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.

Generalizations

Expressed in category-theoretical terms, a set A is Dedekind-finite if in the category of sets, every monomorphism f: AA is an isomorphism. A von Neumann regular ring R has the analogous property in the category of (left or right) R-modules if and only if in R, xy = 1 implies yx = 1. More generally, a Dedekind-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. the integers.

References

  • Faith, Carl Clifton. Mathematical surveys and monographs. Volume 65. American Mathematical Society. 2nd ed. AMS Bookstore, 2004. ISBN 0821836722
  • 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, Dover Publications, 2008, ISBN 0486466248
  • Lam, Tsit-Yuen. A first course in noncommutative rings. Volume 131 of Graduate texts in mathematics. 2nd ed. Springer, 2001. ISBN 0387951830
  • Herrlich, Horst, Axiom of Choice, Springer-Verlag, 2006, Lecture Notes in Mathematics 1876, ISSN print edition 0075–8434, ISSN electronic edition: 1617-9692, in particular Section 4.1.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Infinite set — In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. Some examples are: * the set of all integers, {..., 1, 0, 1, 2, ...}, is a countably infinite set; and * the set of all real numbers… …   Wikipedia

  • Set theory — This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects …   Wikipedia

  • Dedekind , (Julius Wilhelm) Richard — (1831–1916) German mathematician The son of an academic lawyer from Braunschweig, Germany, Dedekind was educated at the Caroline College there and at Göttingen, where he gained his doctorate in 1852. After four years spent teaching at Göttingen,… …   Scientists

  • Finite set — In mathematics, a set is called finite if there is a bijection between the set and some set of the form {1, 2, ..., n} where n is a natural number. (The value n = 0 is allowed; that is, the empty set is finite.) An infinite set is a set which is… …   Wikipedia

  • Richard Dedekind — Infobox Scientist name = PAGENAME box width = image size =180px caption =Richard Dedekind, c. 1850 birth date = October 6, 1831 birth place = Braunschweig death date = February 12, 1916 death place = Braunschweig residence = citizenship =… …   Wikipedia

  • Dedekind domain — In abstract algebra, a Dedekind domain or Dedekind ring, named after Richard Dedekind, is an integral domain in which every nonzero proper ideal factors into a product of prime ideals. It can be shown that such a factorization is then necessarily …   Wikipedia

  • Dedekind number — …   Wikipedia

  • Dedekind, Richard — ▪ German mathematician born Oct. 6, 1831, Braunschweig, duchy of Braunschweig [Germany] died Feb. 12, 1916, Braunschweig  German mathematician who developed a major redefinition of irrational numbers (irrational number) in terms of arithmetic… …   Universalium

  • Paradoxes of set theory — This article contains a discussion of paradoxes of set theory. As with most mathematical paradoxes, they generally reveal surprising and counter intuitive mathematical results, rather than actual logical contradictions within modern axiomatic set …   Wikipedia

  • Uncountable set — Uncountable redirects here. For the linguistic concept, see Uncountable noun. In mathematics, an uncountable set is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”