TheInfoList

In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, a set ''A'' is Dedekind-infinite (named after the German mathematician
Richard Dedekind Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to abstract algebra (particularly ring theory In algebra, ring theory is the study of ring (mathematics), rings ...
) if some proper
subset In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...

''B'' of ''A'' is
equinumerous In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
to ''A''. Explicitly, this means that there exists a
bijective function In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
from ''A'' onto some proper subset ''B'' of ''A''. A set is Dedekind-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 the
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...
s. A simple example is $\mathbb$, the set of
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...
s. From Galileo's paradox, there exists a bijection that maps every natural number ''n'' to its
square In Euclidean geometry Euclidean geometry is a mathematical system attributed to Alexandrian Greek mathematics , Greek mathematician Euclid, which he described in his textbook on geometry: the ''Euclid's Elements, Elements''. Euclid's method ...
''n''2. Since the set of squares is a proper subset of $\mathbb$, $\mathbb$ is Dedekind-infinite. Until the
foundational crisis of mathematics Foundations of mathematics is the study of the philosophical Philosophy (from , ) is the study of general and fundamental questions, such as those about existence, reason Reason is the capacity of consciously applying logic Logic ...
showed the need for a more careful treatment of set theory, most mathematicians assumed that a set is
infinite Infinite may refer to: Mathematics *Infinite set, a set that is not a finite set *Infinity, an abstract concept describing something without any limit Music *Infinite (band), a South Korean boy band *''Infinite'' (EP), debut EP of American mus ...
if and only if In logic Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents st ...
it is Dedekind-infinite. In the early twentieth century,
Zermelo–Fraenkel set theory In set theory illustrating the intersection of two sets Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set ...
, today the most commonly used form of
axiomatic set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, i ...
, was proposed as an
axiomatic system In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
to formulate a theory of sets free of paradoxes such as
Russell's paradox In mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical ...

. Using the axioms of Zermelo–Fraenkel set theory with the originally highly controversial
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product#Infinite Cartesian products, Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the a ...

included (ZFC) one can show that a set is Dedekind-finite if and only if it is
finite Finite is the opposite of Infinity, infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected ...
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 of ZF are not strong enough to prove that every set that is Dedekind-finite is finite. 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 implies 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 In set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch ...
" should be compared with the usual definition: a set ''A'' is
infinite Infinite may refer to: Mathematics *Infinite set, a set that is not a finite set *Infinity, an abstract concept describing something without any limit Music *Infinite (band), a South Korean boy band *''Infinite'' (EP), debut EP of American mus ...
when it cannot be put in bijection with a finite
ordinal Ordinal may refer to: * Ordinal data, a statistical data type consisting of numerical scores that exist on an arbitrary numerical scale * Ordinal date, a simple form of expressing a date using only the year and the day number within that year * O ...
, namely a set of the form 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 A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces ...

s simply assumed that a set is infinite
if and only if In logic Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents st ...
it is Dedekind-infinite. However, this equivalence cannot be proved with the
axioms An axiom, postulate or assumption is a statement that is taken to be truth, true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Greek ''axíōma'' () 'that which is thought worthy or fit' or ...
of
Zermelo–Fraenkel set theory In set theory illustrating the intersection of two sets Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set ...
without the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product#Infinite Cartesian products, Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the a ...

(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 In mathematics, mathematical writing, the term strict refers to the property of excluding equality and equivalence and often occurs in the context of Inequality (mathematics), inequality and Monotonic function, monotonic functions. It is often att ...
weaker than the
axiom of countable choice The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom An axiom, postulate or assumption is a statement that is taken to be truth, true, to serve as a premise or starting point for further reasoning and argumen ...

(CC). (See the references below.)

# 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: *it has a
countably infinite In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
subset; *there exists an injective map from a countably infinite set to ''A''; *there is a
function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...
that is
injective In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

but not
surjective In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...

; *there is an injective function , where N denotes the set of all
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...
s; it is dually Dedekind-infinite if: *there is a function 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: *there exists a surjective map from ''A'' onto a countably infinite set; *the powerset of ''A'' is Dedekind-infinite; and it is infinite if: *for any natural number ''n'', there is no bijection from 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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
sequences In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
from ''A''. 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'' (if ''B'' had a countably infinite subset, then using the fact that the elements of ''B'' are injective sequences, one could exhibit a countably infinite subset of ''A''). 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.

# History

The term is named after the German mathematician
Richard Dedekind Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to abstract algebra (particularly ring theory In algebra, ring theory is the study of ring (mathematics), rings ...
, 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 number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...
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 (, ; ; ; born Bernardus Placidus Johann Nepomuk Bolzano; 5 October 1781 – 18 December 1848) was a Bohemian A Bohemian () is a resident of Bohemia Bohemia ( ; cs, Čechy ; ; hsb, Čěska; szl, Czechy) is the westernmost a ...

, 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 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 Ernst Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel set theory, Zer ...
formulated the AC explicitly. The existence of infinite, Dedekind-finite sets was studied by
Bertrand Russell Bertrand Arthur William Russell, 3rd Earl Russell (18 May 1872 – 2 February 1970) was a British polymath A polymath ( el, πολυμαθής, , "having learned much"; la, homo universalis, "universal human") is an individual whose know ...
and
Alfred North Whitehead Alfred North Whitehead (15 February 1861 – 30 December 1947) was an English mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Greek: ) includes the study of such topics ...
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.

# 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 In mathematics, the well-ordering theorem, also known as Zermelo's theorem, states that every Set (mathematics), 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 eleme ...
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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
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).

# 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 The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom An axiom, postulate or assumption is a statement that is taken to be truth, true, to serve as a premise or starting point for further reasoning and argumen ...

(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) , 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 An image (from la, imago) is an artifact that depicts visual perception Visual perception is the ability to interpret the surrounding environment (biophysical), environment through photopic vision (daytime vision), color vision, sco ...
of f is the countable set 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, 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'', , can be easily defined. We may now define a bijection that takes every member not in ''U'' to itself, and takes ''h''(''n'') for every natural number to . Hence, ''X'' is Dedekind-infinite, and we are done.

# 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 ring In mathematics, a von Neumann regular ring is a ring (mathematics), ring ''R'' (associative, with 1, not necessarily commutative) such that for every element ''a'' in ''R'' there exists an ''x'' in ''R'' with . One may think of ''x'' as a "weak inv ...
''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.

# References

*Faith, Carl Clifton. ''Mathematical surveys and monographs''. Volume 65. American Mathematical Society. 2nd ed. AMS Bookstore, 2004. *Moore, Gregory H., ''Zermelo's Axiom of Choice'', Springer-Verlag, 1982 (out-of-print), , in particular pp. 22-30 and tables 1 and 2 on p. 322-323 * Jech, Thomas J., ''The Axiom of Choice'', Dover Publications, 2008, *Lam, Tsit-Yuen. ''A first course in noncommutative rings''. Volume 131 of
Graduate texts in mathematics Graduate Texts in Mathematics (GTM) (ISSN 0072-5285) is a series of graduate-level File:CCMDonation49.JPG, Student receives degree from the Monterrey Institute of Technology and Higher Education, Mexico City, 2013 A graduate school (sometimes sh ...
. 2nd ed. Springer, 2001. {{ISBN, 0-387-95183-0 *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. Basic concepts in infinite set theory Cardinal numbers de:Dedekind-unendlich