In
mathematics, a set ''A'' is Dedekind-infinite (named after the German mathematician
Richard Dedekind) if some proper
subset ''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'', the ...
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
, 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 a ...
''n''
2. Since the set of squares is a proper subset of
,
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 mathem ...
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 b ...
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 ...
, today the most commonly used form of
axiomatic set theory, 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 contains ...
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 ...
. 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, a verb form that has a subject, usually being inflected or marke ...
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 s ...
" 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
On ...
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 b ...
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 f ...
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 ...
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 (where ...
(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 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 type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
that is
injective but not
surjective;
*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 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 called 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, 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 lib ...
, 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, ...
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.
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 orde ...
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).
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 (where ...
(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 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 o ...
, 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 i ...
. 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 elemen ...
''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 s ...
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 ...
.
Notes
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