Equinumerosity

In mathematics, two sets or classes 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. 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. In mathematics, two sets or classes 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. 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 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 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 (an example of the situation 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). 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. 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. 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'. Equinumerosity has the characteristic properties of an equivalence relation (reflexivity, symmetry, and transitivity): 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, 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|. 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. The law of trichotomy for cardinal numbers also implies the axiom of choice.