Inmathematics,cardinality is an intrinsic property ofsets, roughly meaning the number of individualobjects they contain, which may beinfinite. The concept is understood throughone-to-one correspondences between sets. That is, if their objects can be paired such that each object has a pair, and no object is paired more than once.
The basic concepts of cardinality go back as early as the 6th century BCE, and there are several close encounters with it throughout history, however, the results were generally dismissed as paradoxical. It is considered to have been first introduced formally to mathematics byGeorg Cantor at the turn of the 20th century. Cantor's theory of cardinality was then formalized, popularized, and explored by many influential mathematicians of the time, and has since become a fundamental concept of mathematics.
Two sets are said to beequinumerous orhave the same cardinality if there exists a one-to-one correspondence between them. Otherwise, one is said to bestrictly larger orstrictly smaller than the other. A set iscountably infinite if it can be placed in one-to-one correspondence with the set ofnatural numbers For example, the set of even numbers and the set ofrational numbers are countable.Uncountable sets are those strictly larger than the set of natural numbers—for example, the set of allreal numbers or thepowerset of the set of natural numbers.
Forfinite sets, cardinality coincides with the natural number found bycounting their elements. However, it is more often difficult to ascribe "sizes" toinfinite sets. Thus, a system ofcardinal numbers can be developed to extend the role of natural numbers as abstractions of the sizes of sets. The cardinal number corresponding to a set is written as between two vertical bars. Most commonly, theAleph numbers are used, since it can be shown every infinite set has cardinality equivalent to some Aleph.
The set of natural numbers has cardinality. The question of whether the real numbers have cardinality is known as thecontinuum hypothesis, which has been shown to beunprovable in standard set theories such asZermelo–Fraenkel set theory. Alternative set theories and additionalaxioms give rise to different properties and have often strange or unintuitive consequences. However, every theory of cardinality using standard logical foundations of mathematics admitsSkolem's paradox, which roughly asserts that basic properties of cardinality are notabsolute, but relative to themodel in which the cardinality is measured.
Cardinality is an intrinsic property ofsets which defines their size, roughly corresponding to the number of individualobjects they contain.[1] Fundamentally however, it is different from the concepts ofnumber orcounting as the cardinalities of two sets can be compared without referring to their number of elements, or defining number at all. For example, in the imageabove, a set of apples is compared to a set of oranges such that every fruit is used exactly once which shows these two sets have the same cardinality, even if one doesn't know how many of each there are.[2][3] Thus, cardinality is measured by putting sets inone-to-one correspondence. If it is possible, the sets are said to have thesame cardinality, and if not, one set is said to bestrictly larger orstrictly smaller than the other.[4]
Georg Cantor, the originator of the concept, defined cardinality as "the general concept which, with the aid of our intelligence, results from a set when we abstract from the nature of its various elements and from the order of their being given."[5] This definition was considered to be imprecise, unclear, and purely psychological.[6] Thus,cardinal numbers, a means of measuring cardinality, became the main way of presenting the concept. The distinction between the two is roughly analogous to the difference between an object'smass and its massinkilograms.[7] However, somewhat confusingly, the phrases "The cardinality of M" and "The cardinal number of M" are used interchangeably.
The termcardinality originates from thepost-classical Latincardo ("to hinge"), which referred to something central or pivotal, both literally and metaphorically. This passed intomedieval Latin and then into English, wherecardinal came to describe things considered to be, in some sense, fundamental, such as,cardinal sins,cardinal directions, and (in linguistics)cardinal numbers.[8][9] The last of which referred to numbers used for counting (e.g.,one,two,three),[10] as opposed toordinal numbers, which express order (e.g.,first, second, third),[11] andnominal numbers used for labeling without meaning (e.g.,jersey numbers andserial numbers).[12]
In mathematics, the notion of cardinality was first introduced byGeorg Cantor in the late 19th century, wherein he used the termMächtigkeit, which may be translated as "magnitude" or "power", though Cantor credited the term to a work byJakob Steiner onprojective geometry.[13][14][15] The termscardinality andcardinal number were eventually adopted from the grammatical sense, and later translations would use these terms.[16][17]
From the 6th century BCE, the writings ofGreek philosophers, such asAnaximander, show hints of comparing infinite sets or shapes, however, it was generally viewed as paradoxical and imperfect (cf.Zeno's paradoxes).[18]Aristotle distinguished between the notions ofactual infinity and potential infinity, arguing that Greek mathematicians understood the difference, and that they "do not need the [actual] infinite and do not use it."[19] The Greek notion of number (αριθμός,arithmos) was used exclusively for a definite number of definite objects (i.e. finite numbers).[20] This would be codified inEuclid'sElements, where thefifth common notion states "The whole is greater than the part", often called theEuclidean principle. This principle would be the dominating philosophy in mathematics until the 19th century.[18][21]
Around the 4th century BCE,Jaina mathematics would be the first to discuss different sizes of infinity. They defined three major classes of number: enumerable (finite numbers), unenumerable (asamkhyata, roughly,countably infinite), and infinite (ananta). Then they had five classes of infinite numbers: infinite in one direction, infinite in both directions, infinite in area, infinite everywhere, and infinite perpetually.[22][23]
One of the earliest explicit uses of a one-to-one correspondence is recorded inAristotle'sMechanics (c. 350 BCE), known asAristotle's wheel paradox. The paradox can be briefly described as follows: A wheel is depicted as twoconcentric circles. The larger, outer circle is tangent to a horizontal line (e.g. a road that it rolls on), while the smaller, inner circle is rigidly affixed to the larger. Assuming the larger circle rolls along the line without slipping (or skidding) for one full revolution, the distances moved by both circles are the same: thecircumference of the larger circle. Further, the lines traced by the bottom-most point of each is the same length.[24] Since the smaller wheel does not skip any points, and no point on the smaller wheel is used more than once, there is a one-to-one correspondence between the two circles.[25][26][27]
Galileo Galilei presented what was later coinedGalileo's paradox in his bookTwo New Sciences (1638),[28] where he presents a seeming paradox in infinite sequences of numbers. It goes roughly as follows: for eachperfect square 1, 4, 9, 16, and so on, there is a uniquesquare root 1, 2, 3, 4, and so on. Therefore, there are as many perfect squares as there are square roots. However, every number is a square root, since it can besquared, but not every number is a perfect square. Moreover, the proportion of perfect squares as one passes larger values diminishes, and is eventually smaller than any given fraction. Galileo denied that this was fundamentally contradictory, however he concluded that this meant we could not compare the sizes of infinite sets, missing the opportunity to discover cardinality.[29]
InA Treatise of Human Nature (1739),David Hume is quoted for saying"When two numbers are so combined, as that the one has always a unit answering to every unit of the other, we pronounce them equal",[30] now calledHume's principle, which was used extensively byGottlob Frege later during the rise of set theory.[31][32][33]
Bernard Bolzano'sParadoxes of the Infinite (Paradoxien des Unendlichen, 1851) is often considered the first systematic attempt to introduce the concept of sets intomathematical analysis. In this work, Bolzano defended the notion ofactual infinity, presented an early formulation of what would later be recognized as one-to-one correspondence between infinite sets. He discussed examples such as the pairing between theintervals and by the relation and revisited Galileo's paradox. However, he too resisted saying that these sets were, in that sense, the same size. WhileParadoxes of the Infinite anticipated several ideas central to later set theory, the work had little influence on contemporary mathematics, in part due to itsposthumous publication and limited circulation.[34][35][36]
The concept of cardinality emerged nearly fully formed in the work of Georg Cantor during the 1870s and 1880s, in the context ofmathematical analysis. In a series of papers beginning withOn a Property of the Collection of All Real Algebraic Numbers (1874),[37] Cantor introduced the idea of comparing the sizes of infinite sets, through the notion of one-to-one correspondence.[38] He showed that the set ofreal numbers was, in this sense, strictly larger than the set of natural numbersusing a nested intervals argument.[39] This result was later refined into the more widely knowndiagonal argument of 1891, published inÜber eine elementare Frage der Mannigfaltigkeitslehre,[40] where he also proved the more general result (now calledCantor's Theorem) that thepower set of any set is strictly larger than the set itself.[41]
Cantor introduced the notioncardinal numbers in terms ofordinal numbers. He viewed cardinal numbers as an abstraction of sets, introduced the notations, where, for a given set, theorder type of that set was written, and the cardinal number was, a double abstraction.[42] He also introduced theAleph sequence for infinite cardinal numbers. These notations appeared in correspondence and were formalized in his later writings, particularly the seriesBeiträge zur Begründung der transfiniten Mengenlehre (1895–1897).[43] In these works, Cantor developed anarithmetic of cardinal numbers, defining addition, multiplication, and exponentiation of cardinal numbers based on set-theoretic constructions. This led to the formulation of theContinuum Hypothesis (CH), the proposition that no set has cardinality strictly between the cardinality of the natural numbers and thecardinality of the continuum, that is whether. Cantor was unable to resolve CH and left it as anopen problem.[44]
Parallel to Cantor’s development,Richard Dedekind independently formulated many advanced theorems of set theory, and helped establish set-theoretic foundations of algebra and arithmetic.[45] Dedekind'sThe Nature and Meaning of Numbers [de] (1888)[46] emphasized structural properties over extensional definitions, and supported the bijective formulation of size and number. Dedekind was in correspondence with Cantor during the development of set theory; he supplied Cantor with a proof of the countability of thealgebraic numbers, and gave feedback and modifications on Cantor's proofs before publishing.[47][34][48]
After Cantor's 1883 proof that all finite-dimensional spaces have the same cardinality,[49] in 1890,Giuseppe Peano introduced thePeano curve, which was a more visual proof that theunit interval has the same cardinality as theunit square on[50] This created a new area of mathematical analysis studying what is now calledspace-filling curves.[51]
German logicianGottlob Frege attempted to ground the concepts of number and arithmetic in logic using Cantor's theory of cardinality andHume's principle inDie Grundlagen der Arithmetik (1884) and the subsequentGrundgesetze der Arithmetik (1893, 1903).[31][32][33] Frege defined cardinal numbers asequivalence classes of sets under equinumerosity. However, Frege's approach to set theory was later shown to be flawed. His approach was eventually reformalized byBertrand Russell andAlfred Whitehead inPrincipia Mathematica (1910–1913, vol. II)[52] using atheory of types.[53] Though Russell initially had difficulties understanding Cantor's and Frege’s intuitions of cardinality.[54][55] This definition of cardinal numbers is now referred to as theFrege–Russell definition.[56] This definition was eventually superseded by the convention established byJohn von Neumann in 1928 which uses representatives to define cardinal numbers.[57]
At theParis conference of theInternational Congress of Mathematicians in 1900,David Hilbert, one of the most influential mathematicians of the time, gave a speech wherein he presented ten unsolved problems (of a total of 23, later published, now calledHilbert's problems). Of these, he placed "Cantor's problem" (now called the Continuum Hypothesis) as the first on the list. This list of problems would prove to be very influential in 20th century mathematics, and attracted a lot of attention from other mathematicians toward Cantor's theory of cardinality.[58][34]
In 1908,Ernst Zermelo proposed the firstaxiomatization of set theory, now calledZermelo set theory, primarily to support his earlier (1904) proof of theWell-ordering theorem, which showed that all cardinal numbers could be represented asAlephs, though the proof required a controversial principle now known as theAxiom of Choice (AC).[59] Zermelo's system would later be extended byAbraham Fraenkel andThoralf Skolem in the 1920s to create the standard foundation of set theory, calledZermelo–Fraenkel set theory (ZFC, "C" for the Axiom of Choice). ZFC provided a rigorous foundation through which infinite cardinals could be systematically studied while avoiding theparadoxes of naive set theory.[34][60]
Ignoring possible foundational issues, during the early 1900s,Felix Hausdorff would begin studying "exorbitant numbers": roughly, very large cardinal numbers, or what are now calledinaccessible cardinals. This work would be continued and popularized by several other influential set theorists such asPaul Mahlo—who introducedMahlo cardinals—as well asWacław Sierpiński, andAlfred Tarski. Their work would eventually be known collectively as the study oflarge cardinals.[61]
In 1940,Kurt Gödel showed that the Continuum Hypothesis (CH) cannot bedisproved from the axioms of ZFC by showing that both CH and AC hold in hisconstructible universe: aninner model of ZFC. The existence of a model of ZFC in which additional axioms hold shows that the additional axioms are (relatively)consistent with ZFC.[62] In 1963,Paul Cohen showed that CH cannot beproven from the ZFC axioms, which showed that CH wasindependent from ZFC. To prove his result, Cohen developed the method offorcing, which has become a standard tool in set theory. Cohen was awarded theFields Medal in 1966 for his proof.[63][64]
The basic notions ofsets andfunctions are used to develop the concept of cardinality, and technical terms therein are used throughout this article. Aset can be understood as any collection of objects, usually represented withcurly braces. For example, specifies a set, called, which contains the numbers 1, 2, and 3. The symbol represents set membership, for example says "1 is a member of the set" which is true by the definition of above.
Afunction is an association that maps elements of one set to the elements of another, often represented with an arrow diagram. For example, the adjacent image depicts a function which maps the set ofnatural numbers to the set ofeven numbers by multiplying by 2. If a function does not map two elements to the same place, it is calledinjective. If a function covers every element in the output space, it is calledsurjective. If a function is both injective and surjective, it is calledbijective. (For further clarification, seeBijection, injection and surjection.)
The intuitive property of two sets having the "same size" is that their objects can be paired one-to-one. A one-to-one pairing between two sets defines a bijective function between them by mapping each object to its pair. Similarly, a bijection between two sets defines a pairing of their elements by pairing each object with the one it maps to. Therefore, these notions of "pairing" and "bijection" are intuitively equivalent.[65] In fact, it is often the case that functions are defined literally as this set of pairings (seeFunction (mathematics) § Formal definition).[66] Thus, the following definition is given:
Two sets and are said to have thesame cardinality if their elements can be paired one-to-one. That is, if there exists a function which is bijective. This is written as and eventually once has been defined.[76] Alternatively, these sets, and may be said to beequivalent,similar,equinumerous,equipotent, orequipollent.[81] For example, the set of non-negativeeven numbers has the same cardinality as the set ofnatural numbers, since the function is a bijection from to (see picture above).
The intuitive property for finite sets that "the whole is greater than the part" is no longer true for infinite sets, and the existence of surjections or injections that don't work does not prove that there is no bijection. For example, the function from to, defined by is injective, but not surjective (since 2, for instance, is not mapped to), and from to, defined by (see:floor function) is surjective, but not injective, (since 0 and 1 for instance both map to 0). Neither nor can challenge which was established by the existence of.[82]
A fundamental result necessary in developing a theory of cardinality is relating it to anequivalence relation. A binaryrelation is an equivalence relation if it satisfies the three basic properties of equality:reflexivity,symmetry, andtransitivity.[83]
Since equinumerosity satisfies these three properties, it forms an equivalence relation. This means that cardinality, in some sense,partitions sets intoequivalence classes, and one may assign a representative to denote this class. This motivates the notion of acardinal number.[84] Somewhat more formally, a relation must be a certain set ofordered pairs. Since there is noset of all sets in standard set theory, equinumerosity is not a relation in the usual sense, but apredicate or a relation overclasses.
A set is not larger than a set if it can be mapped into without overlap. That is, the cardinality of is less than or equal to the cardinality of if there is aninjective function from to. This is written and eventually[92] and read as isnot greater than or isdominated by[93] If but there is no injection from to then is said to bestrictly smaller than written without the underline as or[94] For example, if has four elements and has five, then the following are true and
The basic properties of an inequality are reflexivity (for any), transitivity (if and then) andantisymmetry (if and then) (SeeInequality § Formal definitions). Cardinal inequality as defined above is reflexive since theidentity function is injective, and is transitive by function composition.[95] Antisymmetry is established by theSchröder–Bernstein theorem. The proof roughly goes as follows.[96]
Given sets and, where is the function that proves and proves, then consider the sequence of points given by applying then to each element over and over. Then we can define a bijection as follows: If a sequence forms a cycle, begins with an element not mapped to by, or extends infinitely in both directions, define for each in those sequences. The last case, if a sequence begins with an element, not mapped to by, define for each in that sequence. Then is a bijection.[96]
The above shows that cardinal inequality is apartial order. Atotal order has the additional property that, for any and, either or This can be established by thewell-ordering theorem. Every well-ordered set isisomorphic to a uniqueordinal number, called theorder type of the set. Then, by comparing their order types, one can show that or. This result is equivalent to theaxiom of choice.[97][98][99]
A set is calledcountable if it isfinite or has a bijection with the set ofnatural numbers in which case it is calledcountably infinite. The termdenumerable is also sometimes used for countably infinite sets.[100] For example, the set of all even natural numbers is countable, and therefore has the same cardinality as the whole set of natural numbers, even though it is aproper subset. Similarly, the set ofsquare numbers is countable, which was considered paradoxical for hundreds of years before modern set theory (cf.§ Pre-Cantorian set theory). However, several other examples have historically been considered surprising or initially unintuitive since the rise of set theory.[101]
Therational numbers are those which can be expressed as thequotient orfraction of twointegers. The rational numbers can be shown to be countable by considering the set of fractions as the set of allordered pairs of integers, denoted which can be visualized as the set of allinteger points on a grid. Then, an intuitive function can be described by drawing a line in a repeating pattern, or spiral, which eventually goes through each point in the grid. For example, going through each diagonal on the grid for positive fractions, or through a lattice spiral for all integer pairs.[102] These technically over cover the rationals, since, for example, the rational number gets mapped to by all the fractions as the grid method treats these all as distinct ordered pairs. So this function shows not This can be corrected by "skipping over" these numbers in the grid, using the Schröder–Bernstein theorem, or by designing a function which does this naturally, for example using theCalkin–Wilf tree.[103]
A number is calledalgebraic if it is a solution of somepolynomial equation (with integercoefficients). For example, thesquare root of two is a solution to and the rational number is the solution to Conversely, a number which cannot be the root of any polynomial is calledtranscendental. Two examples includeEuler's number (e) andpi (π). In general, proving a number is transcendental is considered to be very difficult, and only a few classes of transcendental numbers are known. However, it can be shown that the set of algebraic numbers is countable by ordering the polynomialslexicographically (for example, seeCantor's first set theory article § The proofs). Since the set of algebraic numbers is countable while the real numbers are uncountable (shown in the following section), the transcendental numbers must form the vast majority of real numbers, even though they are individually much harder to identify. That is to say,almost all real numbers are transcendental.[104]
Hilbert's paradox of the Grand Hotel is a popularthought experiment devised by the German mathematicianDavid Hilbert to illustrate a counterintuitive property of countably infinite sets, allowing them to have the same cardinality as aproper subset of themselves. The scenario begins by imagining a hotel with an infinite number of rooms, one for each natural number, all of which are occupied. But then a new guest walks in asking for a room. The hotel accommodates by moving the occupant of room 1 to room 2, the occupant of room 2 to room 3, room 3 to room 4, and in general, room n to room n+1. Then every guest still has a room, but room 1 is open for the new guest.[105][106]
Then, the scenario continues by imagining an infinitely long bus of new guests seeking a room. The hotel accommodates by moving the person in room 1 to room 2, room 2 to room 4, and in general, room n to room 2n. Thus, all the even-numbered rooms are occupied, but all the odd-numbered rooms are vacant, leaving room for the infinite bus of new guests. The scenario continues further by assuming an infinite number of these infinite buses arrive at the hotel, and showing that the hotel is still able to accommodate. Finally, an infinite bus which has a seat for everyreal number arrives, and the hotel is no longer able to accommodate.[105][106]
A set is calleduncountable if it is not countable; that is, it is infinite and strictly larger than the set of natural numbers. The usual first example of this is the set ofreal numbers, which can be understood as the set of all numbers on thenumber line. One method of proving that the reals are uncountable is calledCantor's diagonal argument, credited to Cantor for his 1891 proof,[107] though his method differs from the more common presentation.[108]
It begins by assuming,by contradiction, that there is some one-to-one mapping between the natural numbers and the set of real numbers between 0 and 1 (the interval). Then, take thedecimal representation of each real number, for example, with a leading zero followed by any sequence of digits. The number 1 is included in this set since1 =0.999... Considering these real numbers in a column, it is always possible to create a new number such that the first digit of the new number is different from that of the first number in the column, the second digit is different from the second number in the column, and so on. The new number must also have a unique decimal representation, that is, it cannot end inrepeating nines or repeating zeros. For example, if the digit isn't 2, make the digit of the new number 2, and if it was 2, make it 3.[109][110] Then, this new number will be different from each of the numbers in the list by at least one digit, and therefore must not be in the list. This shows that the real numbers cannot be put into a one-to-one correspondence with the naturals, and thus must be strictly larger.[111][112]
Another classical example of an uncountable set, established using a related reasoning, is thepower set of the natural numbers, denoted. This is the set of allsubsets of, including theempty set and itself. The method is much closer to Cantor's original diagonal argument. Again, assume by contradiction that there exists a one-to-one correspondence between and, so that every subset of is assigned to some natural number. These subsets are then placed in a column, in the order defined by (see image). Now, one may define a subset of which is not in the list by taking the negation of the "diagonal" of this column as follows:[113]
If, then, that is, if 1 is in the first subset of the list, then 1 isnot in the subset. Further, if, then, that is if the number 2 is not in the second subset of the column, then 2is in the subset. Then in general, for each natural number, if and only if, meaning is put in the subset only if the nth subset in the column does not contain the number. Then, for each natural number,, meaning, is not the nth subset in the list, for any number, and so it cannot appear anywhere in the list defined by. Since was chosen arbitrarily, this shows that every function from to must be missing at least one element, therefore no such bijection can exist, and so must be not be countable.[113]
These two sets, and can be shown to have the same cardinality (by, for example, assigning each subset to a decimal expansion) called thecardinality of the continuum.[114] Whether there exists a set with cardinality between these two sets is known as thecontinuum hypothesis.[115]
Cantor's theorem generalizes the second theorem above, showing that every set is strictly smaller than its powerset. The proof roughly goes as follows: Given a set, assume by contradiction that there is a bijection from to. Then, the subset given by taking the negation of the "diagonal", formally,, cannot be in the list. Therefore, every function is missing at least one element, and so. Further, since is itself a set, the argument can be repeated to show. Taking, this shows that is even larger than, which was already shown to be uncountable. Repeating this argument shows that there are infinitely many "sizes" of infinity.[116]
In the above sections, "the cardinality of a set" was described relationally. In other words, one set could be compared to another, intuitively comparing their "size".Cardinal numbers are a means of measuring this "size" more explicitly. For finite sets, this is simply thenatural number found by counting the elements. This number is called thecardinal number of that set, or simplythe cardinality of that set. The cardinal number of a set is generally denoted by with avertical bar on each side,[117] though it may also be denoted by, or[129]
For infinite sets, "cardinal number" is somewhat more difficult to define formally. Cardinal numbers are not usually thought of in terms of their formal definition, but immaterially in terms of their arithmetic/algebraic properties.[130] The assumption that there issomecardinal function which satisfies, sometimes called theaxiom of cardinality[131] orHume's principle,[132] is sufficient for deriving most properties of cardinal numbers.[133]
Commonly in mathematics, if a relation satisfies the properties of anequivalence relation, the objects used to materialize this relation areequivalence classes, which groups all the objects equivalent to one another. These called theFrege–Russell cardinal numbers.[134] However, this would mean that cardinal numbers are too large to form sets (apart from the cardinal number whose only element is theempty set), since, for example, the cardinal number would be the set of all sets with one element, and would therefore be aproper class.[135] Thus, due toJohn von Neumann, it is more common to assignrepresentatives of these classes.[136]
Given a basic sense ofnatural numbers, a set is said to have cardinality if it can be put in one-to-one correspondence with the set analogous tocounting its elements.[137][138] For example, the set has a natural correspondence with the set and therefore is said to have cardinality 4. Other terminologies include "Its cardinality is 4" or "Its cardinal number is 4". In formal contexts, the natural numbers can be understood as some construction of objects satisfying thePeano axioms.[139]
Showing that such a correspondence exists is not always trivial.Combinatorics is the area of mathematics primarily concerned withcounting, both as a means and as an end to obtaining results, and certain properties of finite structures.[140] The notion cardinality of finite sets is closely tied to many basiccombinatorial principles, and provides a set-theoretic foundation to prove them. It can be shownby induction on the possible sizes of sets that finite cardinality corresponds uniquely with natural numbers (cf.Finite set § Uniqueness of cardinality).[141] This is related—though not equivalent—to thepigeonhole principle.[142]
Theaddition principle asserts that givendisjoint sets and,, intuitively meaning that the sum of the parts is equal to the whole.[143] Themultiplication principle asserts that given two sets and,, intuitively meaning that there are ways to pair objects from these sets.[144] Both of these can be proven by abijective proof, together with induction.[145] The more general result is theinclusion–exclusion principle, which defines how to count the number of elements in overlapping sets.[146]
Naturally, a set is defined to be finite if it isempty or can be put in correspondence with the set for some natural number[137][138] However, there existother definitions of "finite" which don't rely on a definition of "number." For example, a set is calledDedekind-finite if it cannot be put in one-to-one correspondece with aproper subset of itself.[147]
Thealeph numbers are a sequence of cardinal numbers that represent the sizes ofinfinite sets, denoted with analeph the first letter of theHebrew alphabet.[148] The first aleph number is called "aleph-nought", "aleph-zero", or "aleph-null", which represents the cardinality of the set of allnatural numbers: Then, represents the next largest cardinality, then, and so on.[149] The most common way this is formalized in set theory is throughVon Neumann ordinals, known asVon Neumann cardinal assignment.[150]
Ordinal numbers generalize the notion oforder to infinite sets. For example, 2 comes after 1, denoted and 3 comes after both, denoted Then, one defines a new number, which comes after every natural number, denoted Further and so on.[151] More formally, these ordinal numbers can be defined as follows:
theempty set, and so on. Then one can define for example, therefore Defining (alimit ordinal) gives the desired property of being the smallest ordinal greater than all finite ordinal numbers. Further,, and so on.[152]
Since by the natural correspondence, one may define as the set of all finite ordinals. That is, Then, is the set of all countable ordinals (all ordinals with cardinality), thefirst uncountable ordinal. Since a set cannot contain itself, must have a strictly larger cardinality:[153] Furthermore, is the set of all ordinals with cardinality less than or equal to and in general thesuccessor cardinalis the set of all ordinals with cardinality up to. Put another way for infinite cardinals, is the number of possiblewell-orderings on up toorder isomorphism.[154] This is sometimes called theHartogs number of.[155] Then, for a limit ordinal is theunion of all lesser alephs.[156] By thewell-ordering theorem, there cannot exist any set with cardinality between and and every infinite set has some cardinality corresponding to some aleph for some ordinal[157]
Basic arithmetic can be done on cardinal numbers in a very natural way, by extending the theorems for finite combinatorial principles above. The intuitive principle that is and are disjoint then addition of these sets is simply taking theirunion, written as. Thus if and are infinite, cardinal addition is defined as where denotesdisjoint union. Similarly, the multiplication of two sets is intuitively the number of ways to pair their elements (as in themultiplication principle), therefore cardinal multiplication is defined as, where denotes theCartesian product. These definitions can be shown to satisfy the basic properties of standard arithmetic:
Cardinal exponentiation is defined viaset exponentiation, the set of all functions, that is, For finite sets this can be shown to coincide with standardnatural number exponentiation, but includes as a corollary thatzero to the power of zero is one since there is exactly one function from theempty set to itself: theempty function. A combinatorial argument can be used to show. In general, cardinal exponentiation is not as well-behaved as cardinal addition and multiplication. For example, even though it can be proven that the expressiondoes indeed correspond to some aleph, it isunprovable from standard set theories which aleph it corresponds to.
| Exponentiation | Inequality andMonotonicity | Identity elements | Identities (for infinite A,B) |
|---|---|---|---|
| (cf.Currying) | implies | ||
| implies | |||
| implies | (annihilator) |
Theset of all cardinal numbers refers to a hypothetical set which contains all cardinal numbers. Such a set cannot exist, which has been considered paradoxical, and related to theBurali-Forti paradox. Using the definition of cardinal numbers as representatives of their cardinalities. It begins by assuming there is some set Then, if there is some largest cardinal then the powerset is strictly greater, and thus not in Conversely, if there is no largest element, then theunion contains the elements of all elements of and is therefore greater than or equal to each element. Since there is no largest element in for any element there is another element such that and Thus, for any and so Thus, the collection of cardinal numbers is too large to form a set, and is aproper class.
Thenumber line is a geometric construct of the intuitive notions of "space" and "distance" wherein each point corresponds to a distinct quantity or position along a continuous path. The terms "continuum" and "continuous" refer to the totality of this line, having some space (other points) between any two points on the line (dense andarchimedian) and the absence of any gaps (completeness), This intuitive construct is formalized by the set ofreal numbers which model the continuum as a complete, densely ordered, uncountable set.
Thecardinality of the continuum, denoted by "" (a lowercasefraktur script "c"), remains invariant under various transformations and mappings, many considered surprising. For example, all intervals on the real line e.g., and, have the same cardinality as the entire set. First, is a bijection from to. Then, thetangent function is a bijection from the interval to the whole real line. A more surprising example is theCantor set, which is defined as follows: take the interval and remove the middle third, then remove the middle third of each of the two remaining segments, and continue removing middle thirds (see image). The Cantor set is the set of points that survive this process. This set that remains is all of the points whose decimal expansion can be written internary without a 1. Reinterpreting these decimal expansions asbinary (e.g. by replacing the 2s with 1s) gives a bijection between the Cantor set and the interval.
Space-filling curves are continuous surjective maps from theunit interval onto theunit square on, with classical examples such as thePeano curve andHilbert curve. Although such maps are not injective, they are indeed surjective, and thus suffice to demonstrate cardinal equivalence. They can be reused at each dimension to show that for any dimension The infinitecartesian product, can also be shown to have cardinality. This can be established by cardinal exponentiation:. Thus, the real numbers, all finite-dimensional real spaces, and the countable cartesian product share the same cardinality.
As shown in§ Uncountable sets, the set of real numbers is strictly larger than the set of natural numbers. Specifically,. TheContinuum Hypothesis (CH) asserts that the real numbers have the next largest cardinality after the natural numbers, that is. As shown byGödel andCohen, the continuum hypothesis isindependent ofZFC, a standard axiomatization of set theory; that is, it is impossible to prove the continuum hypothesis or its negation from ZFC—provided that ZFC isconsistent.[158][159][160] TheGeneralized Continuum Hypothesis (GCH) extends this to all infinite cardinals, stating that for every ordinal. Research on CH and GCH continues independent of ZFC, especially indescriptive set theory and through the exploration oflarge cardinal axioms.[161] Without GHC, the cardinality of cannot be written in terms of specific alephs. TheBeth numbers provide a concise notation for powersets of the real numbers starting from, then, and, and in general and if is alimit ordinal.
Inmodel theory, amodel corresponds to a specific interpretation of aformal language ortheory. It consists of adomain (a set of objects) and aninterpretation of the symbols in the language, such that the axioms of the theory are satisfied within this structure. Infirst-order logic, theLöwenheim–Skolem theorem states that if a theory has an infinite model, then it also has models of every other infinite cardinality. Applied to set theory, it asserts thatZermelo–Fraenkel set theory, which proves the existence of uncountable sets such as, nevertheless has a countable model. Thus,Skolem's paradox was posed as follows: how can it be that there exists a domain of set theory which only contains countably many objects, but is capable ofsatisfying the statement "there exists a set with uncountably many elements"?[162]
Skolem's paradox does not only apply to ZFC, butany first-order set theory, if it isconsistent, has a model which is countable. A mathematical explanation of the paradox, showing that it is not a true contradiction in mathematics, was first given in 1922 byThoralf Skolem. He explained that the countability or uncountability of a set is notabsolute, but relative to the model in which the cardinality is measured. This is because, for example, if the set is countable in a model of set theory then there is a bijection But a submodel containing which excludes all such functions would thus contain no bijection between and, and therefore would be uncountable. Insecond-order andhigher-order logics, the Löwenheim–Skolem theorem does not hold. This is due to the fact that second-order logic quantifies over all subsets of the domain. Skolem's work was harshly received byErnst Zermelo, who argued against the limitations of first-order logic and Skolem's notion of "relativity", but the result quickly came to be accepted by the mathematical community.[163][162]
Around the turn of the 20th century, set theory turned to an axiomatic approach to avoid rampant foundational issues related to its naive study (cf.§ Axiomatic set theory). The most common axiomatic set theory used today isZermelo–Fraenkel set theory (ZFC).[60] In this system, the relevant axioms include: theAxiom of Infinity, stating roughly "there is an infinite set", specifically, a set with cardinality of the natural numbers; theAxiom of power set, which says that, for any set, the powerset also exists; and theAxiom of Choice, explained below. ZFC has been criticized both for being too strong, and too weak. Similarly, there are many "natural extensions" of ZFC studied by set theorists. Thus, there exist many alternative systems of axioms each of which has implications to the standard theory of cardinality discussed above.
TheAxiom of Choice (AC) is a fundamental principle in the foundations of mathematics which has seen much controversy in its history. Roughly, it states that given any collection of non-empty sets, it is possible to construct a new set by choosing one element from each set, even if the collection is infinite. In many cases, a set created by choosing elements can be made without invoking the axiom of choice. But it is not possible to do this in general, in which case, the axiom of choice must be invoked.
If the Axiom of Choice is assumed to be false in ZF, it has several implications:
Some set theories allow forproper classes, which are, roughly, collections "too large" to form sets. For example, theUniverse of all sets, theclass of all cardinal numbers, or theclass of all ordinal numbers. Such set theories includeVon Neumann–Bernays–Gödel set theory, andMorse–Kelley set theory. In such set theories, some authors find this definition more elegant than assigning representatives, as it more accurately describes the concept by "definition by abstraction".
Proper classes can, in a sense, be assigned cardinalities. Cantor originally called the cardinality of a proper class "Absolute infinite", denoted withtavת (the last letter of theHebrew alphabet), and associated the concept withGod.[165] The first to distinguish between sets and classes wasJohn von Neumann, who formalized the notion of "too large to form sets". More accurately, he defined a class to be a proper class if and only if it was equinumerous with the whole Universe of sets (cf.Axiom of limitation of size). Thus, all proper classes have the same "size". The axiom has several implications, mostly relating to thelimitation of size principles of early set theory. It implies theaxiom of specification, theaxiom of replacement, theaxiom of union, and theaxiom of global choice.
Large cardial axioms assert the existence of cardinal numbers which, as the name suggests, are very large—so large that they cannot be proven to exist within ZFC. For example, aninaccessible cardinal is, roughly, a cardinal that cannot be approached from below using basic set-theoretic operations such as unions, limits, and powersets (more formally, aregular,limit cardinal). Large cardinals are understood in terms of theVon Neumann hierarchy, denoted (for some ordinal), which can be roughly understood as the sets that can be obtained from the empty set, followed by recursively applying the powerset times. Specifically,, and for a limit ordinal.[166]
There existmany known properties defining large cardinals, which come roughly in a linear higherarchy, in terms of consistency strength. As an analogy, in ZFC without theAxiom of Infinity can only prove the existence of finite sets. Therefore, whose existence is provable in usual ZFC, can serve as a model of ZFC–Infinity, and thus if ZFC is consistent, ZFC–Infinity is consistent.[167] Analogously, ZFC+"There exists an inaccessible cardinal" implies the consistency of ZFC, since if is inaccessible, can serve as a model of ZFC (cf.Grothendieck universe). Stronger and stronger large cardinal axioms assert the existence of larger and larger cardinals, each of which proves the consistency of the weaker systems.[168]
Large cardinals are at the forefront of set-theoretic research for both practical and philosophical reasons. In a practical sense, it is often the case that unproven or unprovable conjectures can be settled by sufficiently strong large cardinal axioms. In a philosophical sense, according to aplatonic view among set-theorists such asW. Hugh Woodin, these axioms simply extend the system to include sets that are "supposed" to be considered. That is, there is some fundamentaluniverse of sets, which these axioms grant further access to.[169] For this reason, large cardinal axioms are generally given preference compared to other possible axioms of set theory. This view is controversial among a competing philosophy, sometimes calledpluralsim,[170] which posits that set theory should be understood as amultiverse of set theories, but no "absolute" or "true" model.[171]
Theaxiom of constructibility was the axiom introduced byKurt Gödel to prove the relative consistency of the axiom of choice and generalized continuum hypothesis. It states that all sets are "constructable" (cf.Constructible universe § What L is). It has several consequences, naturally, including AC and GCH, but resolvesseveral other important questions in set theory. The axiom, however, is not well-accepted by set-theorists, most believing it to be "too restrictive". In part it is because the axiom is contradicted by sufficiently strong large cardinal axioms.
TheAxiom of Determinacy (AD) asserts thatcertain kinds ofmathematical games on the natural numbers aredetermined; that is, one player will always have a guaranteed winning strategy.[172] The first serious study of the consequences of AD started durring the 1960s indescriptive set theory—which, roughly, studies the definable sets of the real numbers—after it was noticed that it leads to very nice regulatory properties of the real numbers.[173] Specifically, it implies theperfect set property, theproperty of Baire, and that all sets of real numbers areLebesgue measurable.[174] However, it was shown that this axiom is inconsistent with AC (cf.Axiom of determinacy § Incompatibility with the axiom of choice), and thus was never taken as a fundamental axiom of set theory.[175] However, its relationship to and consistency with large cardinals is still of heavy interest among set theorists such asDonald A. Martin,John R. Steel, andW. Hugh Woodin.[176]
Replacing the Axiom of Choice with the Axiom of Determinacy has several implications:
{{cite book}}:ISBN / Date incompatibility (help)§63. Ein solches Mittel nennt schon Hume: »Wenn zwei Zahlen so combinirt werden, dass die eine immer eine Einheit hat, die jeder Einheit der andern entspricht, so geben wir sie als gleich an.«
| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems (list) and paradoxes | |||||||||
| Logics |
| ||||||||
| Set theory |
| ||||||||
| Formal systems (list), language and syntax |
| ||||||||
| Proof theory | |||||||||
| Model theory | |||||||||
| Computability theory | |||||||||
| Related | |||||||||
| Overview |  | |
|---|---|---|
| Axioms | ||
| Operations | ||
| ||
| Set types | ||
| Theories | ||
| ||
| Set theorists | ||
Authority control databases: National |
|---|
