TheInfoList

OR:

In mathematics, 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 number theory, abstract algebra (particularly ring theory), and the axiomatic foundations of arithmetic. His ...
) if some proper
subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...
''B'' of ''A'' is
equinumerous In mathematics, two sets or classes ''A'' and ''B'' are equinumerous if there exists a one-to-one correspondence (or bijection) between them, that is, if there exists a function from ''A'' to ''B'' such that for every element ''y'' of ''B'', th ...
to ''A''. Explicitly, this means that there exists a
bijective function In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
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 ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...
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 ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...
s. From
Galileo's paradox Galileo's paradox is a demonstration of one of the surprising properties of infinite sets. In his final scientific work, ''Two New Sciences'', Galileo Galilei made apparently contradictory statements about the positive integers. First, some numbers ...
, there exists a bijection that maps every natural number ''n'' to its
square In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90- degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length ad ...
''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 and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theories concerning the nature of mathe ...
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 (group), a South Korean boy band *''Infinite'' (EP), debut EP of American m ...
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicond ...
it is Dedekind-infinite. In the early twentieth century,
Zermelo–Fraenkel set theory In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such a ...
, today the most commonly used form of
axiomatic set theory 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, set theory, as a branch of mathematics, is mostly concer ...
, was proposed as an
axiomatic system In mathematics and logic, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A theory is a consistent, relatively-self-contained body of knowledge which usually contai ...
to formulate a theory of sets free of paradoxes such as
Russell's paradox In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox discovered by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains a ...
. 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 of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
included (ZFC) one can show that a set is Dedekind-finite if and only if it is
finite Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb Traditionally, a finite verb (from la, fīnītus, past particip ...
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 ''ab'' = 1 implies ''ba'' = 1 for any two ring elements ''a'' and ''b''. In other words, all one-sided inverses in the ring are two-sided. These rings have also been called directly finite rings an ...
.

# Comparison with the usual definition of infinite set

This definition of "
infinite set In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. Properties The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only set th ...
" 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 (group), a South Korean boy band *''Infinite'' (EP), debut EP of American m ...
when it cannot be put in bijection with a finite ordinal, 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 in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History O ...
s simply assumed that a set is infinite
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicond ...
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 true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or ...
of
Zermelo–Fraenkel set theory In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such a ...
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 of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
(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 The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom of set theory that states that every countable collection of non-empty sets must have a choice function. That is, given a function ''A'' with domain N (wher ...
(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, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural number ...
subset; *there exists an injective map from a countably infinite set to ''A''; *there is a function that is
injective In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contraposit ...
but not
surjective In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of ...
; *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 ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...
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 an infinite Dedekind-finite set. Let ''A'' be such a set, and let ''B'' be the set of finite
injective In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contraposit ...
sequences In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
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 number theory, abstract algebra (particularly ring theory), and the axiomatic foundations of arithmetic. His ...
, 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 ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...
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 Gonzal Nepomuk Bolzano; 5 October 1781 – 18 December 1848) was a Bohemian mathematician, logician, philosopher, theologian and Catholic priest of Italian extraction, also known for his li ...
, 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 axiomatic se ...
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 mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ar ...
and
Alfred North Whitehead Alfred North Whitehead (15 February 1861 – 30 December 1947) was an English mathematician and philosopher. He is best known as the defining figure of the philosophical school known as process philosophy, which today has found applicat ...
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 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 ord ...
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, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural number ...
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 of set theory that states that every countable collection of non-empty sets must have a choice function. That is, given a function ''A'' with domain N (wher ...
(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 is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
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 In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the total functions from ''A'' to ''B'', and the composition of ...
, every
monomorphism In the context of abstract algebra or universal algebra, a monomorphism is an injective homomorphism. A monomorphism from to is often denoted with the notation X\hookrightarrow Y. In the more general setting of category theory, a monomorphism ...
is an
isomorphism In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
. A
von Neumann regular ring In mathematics, a von Neumann regular ring is a 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 inverse" of the eleme ...
''R'' has the analogous property in the category of (left or right) ''R''-
modules Broadly speaking, modularity is the degree to which a system's components may be separated and recombined, often with the benefit of flexibility and variety in use. The concept of modularity is used primarily to reduce complexity by breaking a sy ...
if and only if in ''R'', implies . More generally, 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''. In other words, all one-sided inverses in the ring are two-sided. These rings have also been called directly finite rings an ...
'' 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 An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language o ...
.

# 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 textbooks in mathematics published by Springer-Verlag. The books in this series, like the other Springer-Verlag mathematics series, are yellow books of a standard ...
. 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