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

                                     

ⓘ 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. Proposed by Dedekind in 1888, Dedekind-infiniteness was the first definition of "infinite" that did not rely on the definition of the natural numbers.

Until the foundational crisis of mathematics showed the need for a more careful treatment of set theory, most mathematicians assumed that a set is infinite if and only if it is Dedekind-infinite. In the early twentieth century, Zermelo–Fraenkel set theory, today the most commonly used form of axiomatic set theory, was proposed as an axiomatic system to formulate a theory of sets free of paradoxes such as Russells paradox. Using the axioms of Zermelo–Fraenkel set theory with the originally highly controversial axiom of choice included ZFC one can show that a set is Dedekind-finite if and only if it is finite in the sense of having a finite number of elements. 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 of ZF are not strong enough to prove that every set that is Dedekind-finite has a finite number of elements. There are definitions 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 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.

                                     

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

                                     

2. Dedekind-infinite sets in ZF

A set A is Dedekind-infinite if it satisfies any, and then all, of the following equivalent over ZF conditions:

  • there is an injective function f: N → A, where N denotes the set of all natural numbers;
  • there exists an injective map from a countably infinite set to A ;
  • it has a countably infinite subset;
  • there is a function f: A → A that is injective but not surjective;

it is dually Dedekind-infinite if:

  • there is a function f: A → A that is surjective but not injective;

it is weakly Dedekind-infinite if it satisfies any, and then all, of the following equivalent over ZF conditions:

  • the powerset of A is Dedekind-infinite;
  • there exists a surjective map from A onto a countably infinite set;

and it is infinite if:

  • for any natural number n, there is no bijection from {0, 1, 2., n−1} to A.

Then, ZF proves the following implications: Dedekind-infinite ⇒ dually Dedekind-infinite ⇒ weakly Dedekind-infinite ⇒ infinite.

There exist models of ZF having infinite Dedekind-finite set. Let A be such a set, and let B be the set of finite injective sequences from B. Since A is infinite, the function "drop the last element" from B to itself is surjective but not injective, so B is dually Dedekind-infinite. However, since A is Dedekind-finite, then so is B.

When sets have additional structures, both kinds of infiniteness can sometimes be proved equivalent over ZF. For instance, ZF proves that a well-ordered set is Dedekind-infinite if and only if it is infinite.

                                     

3. 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" that did not rely on the definition of the natural numbers unless one follows Poincare 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, Bolzanos definition was more accurately a relation that 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.



                                     

4. 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 countably 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 CC 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 of ZF in which every infinite set is Dedekind-infinite, yet the CC fails assuming consistency of ZF.

                                     

5. Proof of equivalence to infinity, assuming axiom of countable choice

That every Dedekind-infinite set is infinite can be easily proven in ZF: every finite set has by definition a bijection with some finite ordinal n, and one can prove by induction on n that this is not Dedekind-infinite.

By using the axiom of countable choice denotation: axiom CC one can prove the converse, namely that every infinite set X is Dedekind-infinite, as follows:

First, define a function over the natural numbers that is, over the finite ordinals f: N → PowerPowerX), so that for every natural number n, f n is the set of finite subsets of X of size n i.e. that have a bijection with the finite ordinal n. f n is never empty, or otherwise X would be finite as can be proven by induction on n.

The image 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 of X. More precisely, according to the axiom of countable choice, a countable set exists, G = { g n | n ∈ N }, so that for every natural number n, g n is a member of f n and is therefore a finite subset of X of size n.

Now, we define U as the union of the members of G. U is an infinite countable subset of X, and a bijection from the natural numbers to U, h: N → U, can be easily defined. We may now define a bijection B: X → X ∖ h 0 that takes every member not in U to itself, and takes h n for every natural number to h n + 1. Hence, X is Dedekind-infinite, and we are done.

                                     

6. Generalizations

Expressed in category-theoretical terms, a set A is Dedekind-finite if in the category of sets, every monomorphism f: A → A 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.



                                     
  • choice is also true, then infinite sets are precisely the Dedekind - infinite sets If an infinite set is a well - orderable set then it has many well - orderings
  • Richard Dedekind Dedekind cut Dedekind domain Dedekind eta function Dedekind - infinite set Dedekind number Dedekind psi function Dedekind sum Dedekind zeta
  • to Richard Dedekind the other to Kazimierz Kuratowski. Kuratowski s is the definition used above. A set S is called Dedekind infinite if there exists
  • number Dedekind psi function Dedekind ring Dedekind sum Dedekind valuation Dedekind zeta function Dedekind Hasse norm Dedekind - infinite set Dedekind MacNeille
  • cardinal to refer to the cardinality of a Dedekind - infinite set in contexts where this may not be equivalent to infinite cardinal that is, in contexts where
  • Dedekind - infinite The axiom of countable choice ACω a weak variant of the axiom of choice AC is needed to show that a set that is not Dedekind - infinite
  • In abstract algebra, a Dedekind domain or Dedekind ring, named after Richard Dedekind is an integral domain in which every nonzero proper ideal factors
  • Cantor to Dedekind the first dated July 28 and the second dated August 3. The role of the absolute infinite in Cantor s conception of set Infinity and
  • mathematics, the Dedekind numbers are a rapidly growing sequence of integers named after Richard Dedekind who defined them in 1897. The Dedekind number M n
  • is either a finite set or a countably infinite set Whether finite or infinite the elements of a countable set can always be counted one at a time and
  • used sets of ordinals to produce an infinity of sets having different infinite cardinalities. His work on infinite sets together with Dedekind s set - theoretical