HOME

TheInfoList



OR:

In mathematics, two
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
s or
class Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differentl ...
es ''A'' and ''B'' are equinumerous if there exists a
one-to-one correspondence 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 ...
(or bijection) between them, that is, if there exists 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 ...
from ''A'' to ''B'' such that for every element ''y'' of ''B'', there is exactly one element ''x'' of ''A'' with ''f''(''x'') = ''y''. Equinumerous sets are said to have the same cardinality (number of elements). The study of cardinality is often called equinumerosity (''equalness-of-number''). The terms equipollence (''equalness-of-strength'') and equipotence (''equalness-of-power'') are sometimes used instead. Equinumerosity has the characteristic properties of an equivalence relation. The statement that two sets ''A'' and ''B'' are equinumerous is usually denoted :A \approx B \, or A \sim B, or , A, =, B, . The definition of equinumerosity using
bijections In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function (mathematics), function between the elements of two set (mathematics), sets, where each element of one set is pair ...
can be applied to both finite and
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 ...
s, and allows one to state whether two sets have the same size even if they are infinite.
Georg Cantor Georg Ferdinand Ludwig Philipp Cantor ( , ;  – January 6, 1918) was a German mathematician. He played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of ...
, the inventor of
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 conce ...
, showed in 1874 that there is more than one kind of infinity, specifically that the collection 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 and the collection of all
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s, while both infinite, are not equinumerous (see
Cantor's first uncountability proof Cantor's first set theory article contains Georg Cantor's first theorems of transfinite set theory, which studies infinite sets and their properties. One of these theorems is his "revolutionary discovery" that the set of all real numbers is unco ...
). In his controversial 1878 paper, Cantor explicitly defined the notion of "power" of sets and used it to prove that the set of all natural numbers and the set of all
rational numbers In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rat ...
are equinumerous (an example where a
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 of ...
of an infinite set is equinumerous to the original set), and that the Cartesian product of even a countably infinite number of copies of the real numbers is equinumerous to a single copy of the real numbers.
Cantor's theorem In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any set A, the set of all subsets of A, the power set of A, has a strictly greater cardinality than A itself. For finite sets, Cantor's theorem can be ...
from 1891 implies that no set is equinumerous to its own
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
(the set of all its subsets). This allows the definition of greater and greater infinite sets starting from a single infinite set. If the axiom of choice holds, then the
cardinal number In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. T ...
of a set may be regarded as the least ordinal number of that cardinality (see
initial ordinal In a written or published work, an initial capital, also referred to as a drop capital or simply an initial cap, initial, initcapital, initcap or init or a drop cap or drop, is a letter at the beginning of a word, a chapter, or a paragraph that ...
). Otherwise, it may be regarded (by
Scott's trick In set theory, Scott's trick is a method for giving a definition of equivalence classes for equivalence relations on a proper class (Jech 2003:65) by referring to levels of the cumulative hierarchy. The method relies on the axiom of regularity but ...
) as the set of sets of minimal rank having that cardinality. The statement that any two sets are either equinumerous or one has a smaller cardinality than the other is equivalent to 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 ...
.


Cardinality

Equinumerous sets have a one-to-one correspondence between them, and are said to have the same cardinality. The cardinality of a set ''X'' is a measure of the "number of elements of the set". Equinumerosity has the characteristic properties of an equivalence relation ( reflexivity, symmetry, and transitivity): ;Reflexivity: Given a set ''A'', the
identity function Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
on ''A'' is a bijection from ''A'' to itself, showing that every set ''A'' is equinumerous to itself: . ;Symmetry: For every bijection between two sets ''A'' and ''B'' there exists an
inverse function In mathematics, the inverse function of a function (also called the inverse of ) is a function that undoes the operation of . The inverse of exists if and only if is bijective, and if it exists, is denoted by f^ . For a function f\colon X ...
which is a bijection between ''B'' and ''A'', implying that if a set ''A'' is equinumerous to a set ''B'' then ''B'' is also equinumerous to ''A'': implies . ;Transitivity: Given three sets ''A'', ''B'' and ''C'' with two bijections and , the
composition Composition or Compositions may refer to: Arts and literature *Composition (dance), practice and teaching of choreography *Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include v ...
of these bijections is a bijection from ''A'' to ''C'', so if ''A'' and ''B'' are equinumerous and ''B'' and ''C'' are equinumerous then ''A'' and ''C'' are equinumerous: and together imply . An attempt to define the cardinality of a set as the equivalence class of all sets equinumerous to it is problematic in
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 ...
, the standard form of axiomatic set theory, because the equivalence class of any
non-empty set In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
would be too large to be a set: it would be a proper class. Within the framework of Zermelo–Fraenkel set theory, relations are by definition restricted to sets (a binary relation on a set ''A'' is a subset of the Cartesian product ), and there is no
set of all sets In set theory, a universal set is a set which contains all objects, including itself. In set theory as usually formulated, it can be proven in multiple ways that a universal set does not exist. However, some non-standard variants of set theory inc ...
in Zermelo–Fraenkel set theory. In Zermelo–Fraenkel set theory, instead of defining the cardinality of a set as the equivalence class of all sets equinumerous to it one tries to assign a
representative Representative may refer to: Politics * Representative democracy, type of democracy in which elected officials represent a group of people * House of Representatives, legislative body in various countries or sub-national entities * Legislator, som ...
set to each equivalence class (
cardinal assignment In set theory, the concept of cardinality is significantly developable without recourse to actually defining cardinal numbers as objects in the theory itself (this is in fact a viewpoint taken by Frege; Frege cardinals are basically equivalence cla ...
). In some other systems of axiomatic set theory, for example in
Von Neumann–Bernays–Gödel set theory In the foundations of mathematics, von Neumann–Bernays–Gödel set theory (NBG) is an axiomatic set theory that is a conservative extension of Zermelo–Fraenkel–choice set theory (ZFC). NBG introduces the notion of class, which is a colle ...
and Morse–Kelley set theory, relations are extended to classes. A set ''A'' is said to have cardinality smaller than or equal to the cardinality of a set ''B'', if there exists a
one-to-one function 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 contrapositi ...
(an injection) from ''A'' into ''B''. This is denoted , ''A'', ≤ , ''B'', . If ''A'' and ''B'' are not equinumerous, then the cardinality of ''A'' is said to be strictly smaller than the cardinality of ''B''. This is denoted , ''A'', < , ''B'', . If the axiom of choice holds, then the law of trichotomy holds for
cardinal number In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. T ...
s, so that any two sets are either equinumerous, or one has a strictly smaller cardinality than the other. The law of trichotomy for cardinal numbers also implies 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 ...
. The
Schröder–Bernstein theorem In set theory, the Schröder–Bernstein theorem states that, if there exist injective functions and between the sets and , then there exists a bijective function . In terms of the cardinality of the two sets, this classically implies that if ...
states that any two sets ''A'' and ''B'' for which there exist two one-to-one functions and are equinumerous: if , ''A'', ≤ , ''B'', and , ''B'', ≤ , ''A'', , then , ''A'', = , ''B'', . This theorem does not rely on 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 ...
.


Cantor's theorem

Cantor's theorem In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any set A, the set of all subsets of A, the power set of A, has a strictly greater cardinality than A itself. For finite sets, Cantor's theorem can be ...
implies that no set is equinumerous to its
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
(the set of all its subsets). This holds even for
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 ...
s. Specifically, the power set of a countably infinite set is an
uncountable set In mathematics, an uncountable set (or uncountably infinite 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 nu ...
. Assuming the existence of an infinite set N consisting 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 and assuming the existence of the power set of any given set allows the definition of a sequence N, ''P''(N), ''P''(''P''(N)), of infinite sets where each set is the power set of the set preceding it. By Cantor's theorem, the cardinality of each set in this sequence strictly exceeds the cardinality of the set preceding it, leading to greater and greater infinite sets. Cantor's work was harshly criticized by some of his contemporaries, for example by
Leopold Kronecker Leopold Kronecker (; 7 December 1823 – 29 December 1891) was a German mathematician who worked on number theory, algebra and logic. He criticized Georg Cantor's work on set theory, and was quoted by as having said, "'" ("God made the integers, ...
, who strongly adhered to a finitist
philosophy of mathematics The philosophy of mathematics is the branch of philosophy that studies the assumptions, foundations, and implications of mathematics. It aims to understand the nature and methods of mathematics, and find out the place of mathematics in peop ...
and rejected the idea that numbers can form an actual, completed totality (an
actual infinity In the philosophy of mathematics, the abstraction of actual infinity involves the acceptance (if the axiom of infinity is included) of infinite entities as given, actual and completed objects. These might include the set of natural numbers, exten ...
). However, Cantor's ideas were defended by others, for example by Richard Dedekind, and ultimately were largely accepted, strongly supported by David Hilbert. See Controversy over Cantor's theory for more. Within the framework 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 ...
, the
axiom of power set In mathematics, the axiom of power set is one of the Zermelo–Fraenkel axioms of axiomatic set theory. In the formal language of the Zermelo–Fraenkel axioms, the axiom reads: :\forall x \, \exists y \, \forall z \, \in y \iff \forall w \ ...
guarantees the existence of the power set of any given set. Furthermore, the
axiom of infinity In axiomatic set theory and the branches of mathematics and philosophy that use it, the axiom of infinity is one of the axioms of Zermelo–Fraenkel set theory. It guarantees the existence of at least one infinite set, namely a set containing th ...
guarantees the existence of at least one infinite set, namely a set containing the natural numbers. There are alternative set theories, e.g. "
general set theory General set theory (GST) is George Boolos's (1998) name for a fragment of the axiomatic set theory Z. GST is sufficient for all mathematics not requiring infinite sets, and is the weakest known set theory whose theorems include the Peano axioms. ...
" (GST),
Kripke–Platek set theory The Kripke–Platek set theory (KP), pronounced , is an axiomatic set theory developed by Saul Kripke and Richard Platek. The theory can be thought of as roughly the predicative part of ZFC and is considerably weaker than it. Axioms In its fo ...
, and
pocket set theory Pocket set theory (PST) is an alternative set theory in which there are only two infinite cardinal numbers, ℵ0 (aleph-naught, the cardinality of the set of all natural numbers) and ''c'' (the cardinality of the continuum). The theory was first s ...
(PST), that deliberately omit the axiom of power set and the axiom of infinity and do not allow the definition of the infinite hierarchy of infinites proposed by Cantor. The cardinalities corresponding to the sets N, ''P''(N), ''P''(''P''(N)), are the
beth number In mathematics, particularly in set theory, the beth numbers are a certain sequence of infinite cardinal numbers (also known as transfinite numbers), conventionally written \beth_0,\ \beth_1,\ \beth_2,\ \beth_3,\ \dots, where \beth is the second H ...
s \beth_0, \beth_1, \beth_2, with the first beth number \beth_0 being equal to \aleph_0 ( aleph naught), the cardinality of any countably infinite set, and the second beth number \beth_1 being equal to \mathfrak c, the cardinality of the continuum.


Dedekind-infinite sets

In some occasions, it is possible for a set ''S'' and its
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 of ...
to be equinumerous. For example, the set of even
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 is equinumerous to the set of all natural numbers. A set that is equinumerous to a proper subsets of itself is called
Dedekind-infinite In mathematics, a set ''A'' is Dedekind-infinite (named after the German mathematician Richard Dedekind) if some proper subset ''B'' of ''A'' is equinumerous to ''A''. Explicitly, this means that there exists a bijective function from ''A'' ont ...
. 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 ...
(ACω), a weak variant of 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), is needed to show that a set that is not Dedekind-infinite is actually
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 ...
. The axioms 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 (ZF) are not strong enough to prove that every
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 ...
is Dedekind-infinite, but the axioms of Zermelo–Fraenkel set theory with the axiom of countable choice () are strong enough. Other definitions of finiteness and infiniteness of sets than that given by Dedekind do not require the axiom of choice for this, see .


Compatibility with set operations

Equinumerosity is compatible with the basic set operations in a way that allows the definition of
cardinal arithmetic In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. The ...
. Specifically, equinumerosity is compatible with
disjoint union In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A ( ...
s: Given four sets ''A'', ''B'', ''C'' and ''D'' with ''A'' and ''C'' on the one hand and ''B'' and ''D'' on the other hand
pairwise disjoint In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A c ...
and with and then This is used to justify the definition of cardinal addition. Furthermore, equinumerosity is compatible with cartesian products: * If and then * ''A'' × ''B'' ~ ''B'' × ''A'' * (''A'' × ''B'') × ''C'' ~ ''A'' × (''B'' × ''C'') These properties are used to justify cardinal multiplication. Given two sets ''X'' and ''Y'', the set of all functions from ''Y'' to ''X'' is denoted by ''X''''Y''. Then the following statements hold: * If ''A'' ~ ''B'' and ''C'' ~ ''D'' then * ''A''''B'' ∪ ''C'' ~ ''A''''B'' × ''A''''C'' for disjoint ''B'' and ''C''. * (''A'' × ''B'')''C'' ~ ''A''''C'' × ''B''''C'' * (''A''''B'')''C'' ~ ''A''''B''×''C'' These properties are used to justify
cardinal exponentiation In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. The ...
. Furthermore, the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
of a given set ''A'' (the set of all subsets of ''A'') is equinumerous to the set 2''A'', the set of all functions from the set ''A'' to a set containing exactly two elements.


Categorial definition

In category theory, 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 ...
, denoted Set, is the
category Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) ...
consisting of the collection of all sets as
object Object may refer to: General meanings * Object (philosophy), a thing, being, or concept ** Object (abstract), an object which does not exist at any particular time or place ** Physical object, an identifiable collection of matter * Goal, an ...
s and the collection of all
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 ...
s between sets as morphisms, with the
composition of functions In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
as the composition of the morphisms. In Set, 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 ...
between two sets is precisely a bijection, and two sets are equinumerous precisely if they are isomorphic as objects in Set.


See also

*
Combinatorial class In mathematics, a combinatorial class is a countable set of mathematical objects, together with a size function mapping each object to a non-negative integer, such that there are finitely many objects of each size. Counting sequences and isomorphis ...
*
Hume's principle Hume's principle or HP says that the number of ''F''s is equal to the number of ''G''s if and only if there is a one-to-one correspondence (a bijection) between the ''F''s and the ''G''s. HP can be stated formally in systems of second-order logic. ...


References

{{reflist Basic concepts in infinite set theory Cardinal numbers de:Mächtigkeit (Mathematik)#Gleichmächtigkeit, Mächtigkeit