Dedekind-infinite set
Encyclopedia
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.
, 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 mathematician
s 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.)
Every Dedekind-infinite set A also satisfies the following condition:
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:
(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.
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.
, 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 number
s (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.
R has the analogous property in the category of (left or right) R-modules if and only if in R, implies . 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a set A is Dedekind-infinite if some proper subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
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.
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 ordinalOrdinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
, 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 mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
s simply assumed that a set is infinite if and only if
IFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...
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
Axiom of countable choice
The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom of set theory, similar to the axiom of choice. It states that any countable collection of non-empty sets must have a choice function...
(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 functionFunction (mathematics)In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
f: A → A which is injectiveInjective functionIn mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
but not surjectiveSurjective functionIn mathematics, a function f from a set X to a set Y is surjective , or a surjection, if every element y in Y has a corresponding element x in X so that f = y...
. - There is an injective function f : N → A, where N denotes the set of all natural numberNatural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s. - A has a countably infiniteCountable setIn mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
subset.
Every Dedekind-infinite set A also satisfies the following condition:
- There is a function f: A → A 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
Séquences
Séquences is a French-language film magazine originally published in Montreal, Quebec by the Commission des ciné-clubs du Centre catholique du cinéma de Montréal, a Roman Catholic film society. Founded in 1955, the publication was edited for forty years by Léo Bonneville, a member of the Clerics...
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 theoremWell-ordering theorem
In mathematics, the well-ordering theorem states that every set can be well-ordered. A set X is well-ordered by a strict total order if every non-empty subset of X has a least element under the ordering. This is also known as Zermelo's theorem and is equivalent to the Axiom of Choice...
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 DedekindRichard Dedekind
Julius Wilhelm Richard Dedekind was a German mathematician who did important work in abstract algebra , algebraic number theory and the foundations of the real numbers.-Life:...
, 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 number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s (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
Bernard Bolzano
Bernhard Placidus Johann Nepomuk Bolzano , Bernard Bolzano in English, was a Bohemian mathematician, logician, philosopher, theologian, Catholic priest and antimilitarist of German mother tongue.-Family:Bolzano was the son of two pious Catholics...
, 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
Charles University in Prague
Charles University in Prague is the oldest and largest university in the Czech Republic. Founded in 1348, it was the first university in Central Europe and is also considered the earliest German university...
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
Ernst Zermelo
Ernst Friedrich Ferdinand Zermelo was a German mathematician, whose work has major implications for the foundations of mathematics and hence on philosophy. He is known for his role in developing Zermelo–Fraenkel axiomatic set theory and his proof of the well-ordering theorem.-Life:He graduated...
formulated the AC explicitly. The existence of infinite, Dedekind-finite sets was studied by Bertrand Russell
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
and Alfred North Whitehead
Alfred North Whitehead
Alfred North Whitehead, OM FRS was an English mathematician who became a philosopher. He wrote on algebra, logic, foundations of mathematics, philosophy of science, physics, metaphysics, and education...
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 is an isomorphism. A von Neumann regular ringVon Neumann regular ring
In mathematics, a von Neumann regular ring is a ring R such that for every a in R there exists an x in R withOne may think of x as a "weak inverse" of a...
R has the analogous property in the category of (left or right) R-modules if and only if in R, implies . 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.