Equinumerosity

In mathematics, two sets A and B are equinumerous if there exists a one-to-one correspondence (a bijection) between them, i.e. 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 finite sets have the same number of elements. 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. Unlike finite sets, some infinite sets are equinumerous to proper subsets of themselves.^[1]

Equinumerous sets are said to have the same cardinality.^[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 statement that two sets A and B are equinumerous is usually denoted

$A \approx B \,$ or $A \sim B$, or $|A|=|B|.$

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 a 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, 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.^[1] This allows the definition of greater and greater infinite sets starting from a single infinite set.

Equinumerosity has the characteristic properties of an equivalence relation.^[1] The cardinal number of a set is the equivalence class of all sets equinumerous to it.^[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 are said to have the same cardinality. The cardinality of a set X is a measure of the "number of elements of the set" and can be defined as the equivalence class of all sets equinumerous to X.^[1] This is possible because 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.

The definition of 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 a non-empty set is too large to be a set: it is 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, e.g. 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|. 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 is equivalent to the historically highly controversial 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, e.g. by Leopold Kronecker, who strongly adhered to a finitist^[4] 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, e.g. by Richard Dedekind, and ultimately were largely accepted, strongly supported by David Hilbert. See Controversy over Cantor's theory.

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

A given set may be equinumerous to some proper subset of itself, e.g. the set of natural numbers is equinumerous to the set of even natural numbers. Such a set is called Dedekind-infinite.^[1][3]

Some weak variant of the axiom of choice (AC) is needed to show that a set that is not Dedekind-infinite is finite in the sense of having a finite number of elements. 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 e.g. the axioms of Zermelo–Fraenkel set theory without the axiom of choice but with the axiom of countable choice (ZF + AC_ω) are strong enough.^[5] Other definitions of finiteness and infiniteness of sets do not require the axiom of choice for this.^[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.

Exponentiation:

• If A ~ B and C ~ D then A^C ~ B^D. (Here X^Y denotes the set of all functions from Y to X.)
• 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 Set, the category of all sets with functions as morphisms, an isomorphism between two sets is precisely a bijection, and two sets are equinumerous precisely if they are isomorphic in this category.

See also

• Combinatorial class
• Hume's principle

References

1. 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.
3. Jech, Thomas J. (2008) [Originally published by North–Holland in 1973]. The Axiom of Choice. Dover. ISBN 978-0-486-46624-8.
4. 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.
5. Herrlich, Horst (2006). Axiom of Choice. Lecture Notes in Mathematics 1876. Springer-Verlag. ISBN 978-3540309895.