Infinite set
Encyclopedia
In set theory
, an infinite set is a set that is not a finite set. Infinite sets may be countable
or uncountable
. Some examples are:
) is infinite. It is the only set which is directly required by the axioms to be infinite. The existence of any other infinite set can be proved in Zermelo–Fraenkel set theory
(ZFC) only by showing that it follows from the existence of the natural numbers.
A set is infinite if and only if for every natural number the set has a subset
whose cardinality is that natural number.
If the axiom of choice holds, then a set is infinite if and only if it includes a countable infinite subset.
If a set of sets is infinite or contains an infinite element, then its union is infinite. The powerset of an infinite set is infinite. Any superset of an infinite set is infinite. If an infinite set is partitioned into finitely many subsets, then at least one of them must be infinite. Any set which can be mapped onto an infinite set is infinite. The Cartesian product
of an infinite set and a nonempty set is infinite. The Cartesian product of an infinite number of sets each containing at least two elements is either empty or infinite; if the axiom of choice holds, then it is infinite.
If an infinite set is a well-ordered set, then it must have a nonempty subset which has no greatest element.
In ZF, a set is infinite if and only if the powerset of its powerset is a Dedekind-infinite set
, having a proper subset equinumerous to itself. If the axiom of choice is also true, infinite sets are precisely the Dedekind-infinite sets.
If an infinite set is a well-orderable set, then it has many well-orderings which are non-isomorphic.
written while he was under house arrest by the Inquisition
.
Galileo argues that the set of squares S = {1,4,9,16,25,...} is the same size as N = {1,2,3,4,5,...} because there is a one-to-one correspondence:
1<-->1, 2<-->4, 3<-->9, 4<-->16, 5<-->25,...
And yet, as he says, S is a proper subset of N and S even gets less dense as the numbers get larger.
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, an infinite set is a set that is not a finite set. Infinite sets may be countable
Countable set
In 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...
or uncountable
Uncountable set
In mathematics, an uncountable set is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger than that of the set of all natural numbers.-Characterizations:There...
. Some examples are:
- the set of all integerIntegerThe integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s, {..., -1, 0, 1, 2, ...}, is a countably infinite set; and - the set of all real numberReal numberIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s is an uncountably infinite setUncountable setIn mathematics, an uncountable set is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger than that of the set of all natural numbers.-Characterizations:There...
.
Properties
The set of natural numbers (whose existence is postulated by the axiom of infinityAxiom of infinity
In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of infinity is one of the axioms of Zermelo-Fraenkel set theory...
) is infinite. It is the only set which is directly required by the axioms to be infinite. The existence of any other infinite set can be proved in Zermelo–Fraenkel set theory
Zermelo–Fraenkel set theory
In mathematics, Zermelo–Fraenkel set theory with the axiom of choice, named after mathematicians Ernst Zermelo and Abraham Fraenkel and commonly abbreviated ZFC, is one of several axiomatic systems that were proposed in the early twentieth century to formulate a theory of sets without the paradoxes...
(ZFC) only by showing that it follows from the existence of the natural numbers.
A set is infinite if and only if for every natural number the set has a 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...
whose cardinality is that natural number.
If the axiom of choice holds, then a set is infinite if and only if it includes a countable infinite subset.
If a set of sets is infinite or contains an infinite element, then its union is infinite. The powerset of an infinite set is infinite. Any superset of an infinite set is infinite. If an infinite set is partitioned into finitely many subsets, then at least one of them must be infinite. Any set which can be mapped onto an infinite set is infinite. The Cartesian product
Cartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
of an infinite set and a nonempty set is infinite. The Cartesian product of an infinite number of sets each containing at least two elements is either empty or infinite; if the axiom of choice holds, then it is infinite.
If an infinite set is a well-ordered set, then it must have a nonempty subset which has no greatest element.
In ZF, a set is infinite if and only if the powerset of its powerset is a Dedekind-infinite set
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.A vaguely related notion is that of a...
, having a proper subset equinumerous to itself. If the axiom of choice is also true, infinite sets are precisely the Dedekind-infinite sets.
If an infinite set is a well-orderable set, then it has many well-orderings which are non-isomorphic.
History
The first known occurrence of explicitly infinite sets is in Galileo's last book Two New SciencesTwo New Sciences
The Discourses and Mathematical Demonstrations Relating to Two New Sciences was Galileo's final book and a sort of scientific testament covering much of his work in physics over the preceding thirty years.After his Dialogue Concerning the Two Chief World Systems, the Roman Inquisition had banned...
written while he was under house arrest by the Inquisition
Inquisition
The Inquisition, Inquisitio Haereticae Pravitatis , was the "fight against heretics" by several institutions within the justice-system of the Roman Catholic Church. It started in the 12th century, with the introduction of torture in the persecution of heresy...
.
Galileo argues that the set of squares S = {1,4,9,16,25,...} is the same size as N = {1,2,3,4,5,...} because there is a one-to-one correspondence:
1<-->1, 2<-->4, 3<-->9, 4<-->16, 5<-->25,...
And yet, as he says, S is a proper subset of N and S even gets less dense as the numbers get larger.