Equinumerosity

Last updated April 28, 2024

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, there is exactly one element x of A with f(x) = y.^[1] Equinumerous sets are said to have the same cardinality (number of elements).^[2] 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.

The definition of equinumerosity using bijections can be applied to both finite and infinite sets, and allows one to state whether two sets have the same size even if they are infinite. Georg Cantor, the inventor of set theory, showed in 1874 that there is more than one kind of infinity, specifically that the collection of all natural numbers and the collection of all real numbers, while both infinite, are not equinumerous (see Cantor's first uncountability proof). 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 are equinumerous (an example where a proper subset 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 from 1891 implies that no set is equinumerous to its own power set (the set of all its subsets).^[1] 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 of a set may be regarded as the least ordinal number of that cardinality (see initial ordinal). Otherwise, it may be regarded (by Scott's trick) as the set of sets of minimal rank having that cardinality.^[1]

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.^[3]

Cardinality

Equinumerous sets have a one-to-one correspondence between them,^[4] and are said to have the same cardinality. The cardinality of a set X is essentially a measure of the number of elements of the set.^[1] Equinumerosity has the characteristic properties of an equivalence relation (reflexivity, symmetry, and transitivity):^[1]

Reflexivity: Given a set A, the identity function on A is a bijection from A to itself, showing that every set A is equinumerous to itself: A ~ A.
Symmetry: For every bijection between two sets A and B there exists an inverse function 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: A ~ B implies B ~ A.
Transitivity: Given three sets A, B and C with two bijections f : A → B and g : B → C, the composition g ∘ f 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: A ~ B and B ~ C together imply A ~ C.

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, the standard form of axiomatic set theory, because the equivalence class of any non-empty set 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 A × A), and there is no set of all sets 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 set to each equivalence class (cardinal assignment). In some other systems of axiomatic set theory, for example in Von Neumann–Bernays–Gödel set theory 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 (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 numbers, so that any two sets are either equinumerous, or one has a strictly smaller cardinality than the other.^[1] The law of trichotomy for cardinal numbers also implies the axiom of choice.^[3]

The Schröder–Bernstein theorem states that any two sets A and B for which there exist two one-to-one functions f : A → B and g : B → A are equinumerous: if |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|.^[1]^[3] This theorem does not rely on the axiom of choice.

Cantor's theorem

Cantor's theorem implies that no set is equinumerous to its power set (the set of all its subsets).^[1] This holds even for infinite sets. Specifically, the power set of a countably infinite set is an uncountable set.

Assuming the existence of an infinite set N consisting of all natural numbers and assuming the existence of the power set of any given set allows the definition of a sequence N, P(N), P(P(N)), P(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, who strongly adhered to a finitist ^[5] philosophy of mathematics and rejected the idea that numbers can form an actual, completed totality (an actual infinity). 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, the axiom of power set guarantees the existence of the power set of any given set. Furthermore, the axiom of infinity 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" (GST), Kripke–Platek set theory, and pocket set theory (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)), P(P(P(N))), … are the beth numbers $\beth _{0}$ , $\beth _{1}$ , $\beth _{2}$ , $\beth _{3}$ , …, 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 to be equinumerous. For example, the set of even natural numbers is equinumerous to the set of all natural numbers. A set that is equinumerous to a proper subset of itself is called Dedekind-infinite.^[1]^[3]

The axiom of countable choice (AC_ω), a weak variant of the axiom of choice (AC), is needed to show that a set that is not Dedekind-infinite is actually finite. The axioms of Zermelo–Fraenkel set theory without the axiom of choice (ZF) are not strong enough to prove that every infinite set is Dedekind-infinite, but the axioms of Zermelo–Fraenkel set theory with the axiom of countable choice (ZF + AC_ω) are strong enough.^[6] Other definitions of finiteness and infiniteness of sets than that given by Dedekind do not require the axiom of choice for this, see Finite set § Necessary and sufficient conditions for finiteness.^[1]

Compatibility with set operations

Equinumerosity is compatible with the basic set operations in a way that allows the definition of cardinal arithmetic.^[1] Specifically, equinumerosity is compatible with disjoint unions: 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 and with A ~ B and C ~ D then A ∪ C ~ B ∪ D. This is used to justify the definition of cardinal addition.

Furthermore, equinumerosity is compatible with cartesian products:

If A ~ B and C ~ D then A × C ~ B × D.
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^C ~ B^D.
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.

Furthermore, the power set 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, denoted Set, is the category consisting of the collection of all sets as objects and the collection of all functions between sets as morphisms, with the composition of functions as the composition of the morphisms. In Set, an isomorphism between two sets is precisely a bijection, and two sets are equinumerous precisely if they are isomorphic as objects in Set.

Related Research Articles

In mathematics, the axiom of choice, abbreviated AC or AoC, 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 of sets, each containing at least one element, it is possible to construct a new set by choosing one element from each set, even if the collection is infinite. Formally, it states that for every indexed family $of nonempty sets, there exists an indexed set such that for every . The axiom of choice was formulated in 1904 by Ernst Zermelo in order to formalize his proof of the well-ordering theorem.$

<span class="mw-page-title-main">Cardinal number</span> Size of a possibly infinite set

In mathematics, a cardinal number, or cardinal for short, is what is commonly called the number of elements of a set. In the case of a finite set, its cardinal number, or cardinality is therefore a natural number. For dealing with the case of infinite sets, the infinite cardinal numbers have been introduced, which are often denoted with the Hebrew letter $(aleph) marked with subscript indicating their rank among the infinite cardinals.$

In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set $contains 3 elements, and therefore has a cardinality of 3. Beginning in the late 19th century, this concept was generalized to infinite sets, which allows one to distinguish between different types of infinity, and to perform arithmetic on them. There are two approaches to cardinality: one which compares sets directly using bijections and injections, and another which uses cardinal numbers. The cardinality of a set may also be called its size, when no confusion with other notions of size is possible.$

In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,

In mathematics, an uncountable set, informally, 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 aleph-null, the cardinality of the natural numbers.

In set theory, Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument, the anti-diagonal argument, the diagonal method, and Cantor's diagonalization proof, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers. Such sets are now known as uncountable sets, and the size of infinite sets is now treated by the theory of cardinal numbers which Cantor began.

In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable.

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 as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial axiom of choice (AC) included, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics. Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice", and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded.

<span class="mw-page-title-main">Aleph number</span> Infinite cardinal number

In mathematics, particularly in set theory, the aleph numbers are a sequence of numbers used to represent the cardinality of infinite sets that can be well-ordered. They were introduced by the mathematician Georg Cantor and are named after the symbol he used to denote them, the Hebrew letter aleph (ℵ).

In set theory, the concept of cardinality is significantly developable without recourse to actually defining cardinal numbers as objects in the theory itself. The concepts are developed by defining equinumerosity in terms of functions and the concepts of one-to-one and onto ; this gives us a quasi-ordering relation

In mathematics, particularly in set theory, the beth numbers are a certain sequence of infinite cardinal numbers, conventionally written $, where is the Hebrew letter beth. The beth numbers are related to the aleph numbers, but unless the generalized continuum hypothesis is true, there are numbers indexed by that are not indexed by .$

In mathematics, a set A is Dedekind-infinite if some proper subset B of A is equinumerous to A. Explicitly, this means that there exists a bijective function from A onto some proper subset B of A. A set is Dedekind-finite if it is not Dedekind-infinite. Proposed by Dedekind in 1888, Dedekind-infiniteness was the first definition of "infinite" that did not rely on the definition of the natural numbers.

In set theory, the cardinality of the continuum is the cardinality or "size" of the set of real numbers $, sometimes called the continuum. It is an infinite cardinal number and is denoted by or .$

In mathematical logic, the theory of infinite sets was first developed by Georg Cantor. Although this work has become a thoroughly standard fixture of classical set theory, it has been criticized in several areas by mathematicians and philosophers.

This article contains a discussion of paradoxes of set theory. As with most mathematical paradoxes, they generally reveal surprising and counter-intuitive mathematical results, rather than actual logical contradictions within modern axiomatic set theory.

In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals aimed to extend enumeration to infinite sets.

This is a glossary of set theory.

In set theory, the Schröder–Bernstein theorem states that, if there exist injective functions $f : A \to B$ and $g : B \to A$ between the sets $A$ and $B$ , then there exists a bijective function $h : A \to B$ .

In order theory and model theory, branches of mathematics, Cantor's isomorphism theorem states that every two countable dense unbounded linear orders are order-isomorphic. For instance, Minkowski's question-mark function produces an isomorphism between the numerical ordering of the rational numbers and the numerical ordering of the dyadic rationals.

References

1 2 3 4 5 6 7 8 9 10 11 12 Suppes, Patrick (1972) [originally published by D. van Nostrand Company in 1960]. Axiomatic Set Theory . Dover. ISBN 0486616304.
↑ Enderton, Herbert (1977). Elements of Set Theory. Academic Press Inc. ISBN 0-12-238440-7.
1 2 3 4 Jech, Thomas J. (2008) [Originally published by North–Holland in 1973]. The Axiom of Choice. Dover. ISBN 978-0-486-46624-8.
↑ Weisstein, Eric W. "Equipollent". mathworld.wolfram.com. Retrieved 2020-09-05.
↑ Tiles, Mary (2004) [Originally published by Basil Blackwell Ltd. in 1989]. The Philosophy of Set Theory: An Historical Introduction to Cantor's Paradise. Dover. ISBN 978-0486435206.
↑ Herrlich, Horst (2006). Axiom of Choice. Lecture Notes in Mathematics 1876. Springer-Verlag. ISBN 978-3540309895.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[suppes-1] 1 2 3 4 5 6 7 8 9 10 11 12 Suppes, Patrick (1972) [originally published by D. van Nostrand Company in 1960]. Axiomatic Set Theory . Dover. ISBN 0486616304.

[2] Enderton, Herbert (1977). Elements of Set Theory. Academic Press Inc. ISBN 0-12-238440-7.

[jech-3] 1 2 3 4 Jech, Thomas J. (2008) [Originally published by North–Holland in 1973]. The Axiom of Choice. Dover. ISBN 978-0-486-46624-8.

[4] Weisstein, Eric W. "Equipollent". mathworld.wolfram.com. Retrieved 2020-09-05.

[tiles-5] Tiles, Mary (2004) [Originally published by Basil Blackwell Ltd. in 1989]. The Philosophy of Set Theory: An Historical Introduction to Cantor's Paradise. Dover. ISBN 978-0486435206.

[herrlich-6] Herrlich, Horst (2006). Axiom of Choice. Lecture Notes in Mathematics 1876. Springer-Verlag. ISBN 978-3540309895.

[1]

[2]

[3]

[4]

[5]

[6]