Editing Cardinality (section)

==Comparing sets==
[[File:Aplicación 2 inyectiva sobreyectiva04.svg|thumb|250px|A one-to-one correspondence from '''N''', the set of all non-negative integers, to the set ''E'' of non-negative [[even number]]s. Although ''E'' is a proper subset of '''N''', both sets have the same cardinality.]]While the cardinality of a finite set is simply its number of elements, extending that notion to infinite sets usually starts with defining comparison of sizes of arbitrary sets (some of which are possibly infinite).

===Equinumerosity===
{{Main|Equinumerosity}}
Two sets have the same cardinality if there exists a one-to-one correspondence between the elements of {{tmath|A}} and those {{tmath|B}} (that is, a [[bijection]] from {{tmath|A}} to {{tmath|B}}).<ref name=":1">{{Cite web|date=2019-12-05|title=Infinite Sets and Cardinality|url=https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Supplemental_Modules_for_Discrete_Math/Additional_Discrete_Topics_(Dean)/Infinite_Sets_and_Cardinality|access-date=2020-08-23|website=Mathematics LibreTexts|language=en}}</ref> Such sets are said to be ''equipotent'', ''equipollent'', or ''[[equinumerous]]''. For example, the set <math>E = \{0, 2, 4, 6, \text{...}\}</math> of non-negative [[even number]]s has the same cardinality as the set <math>\N = \{0, 1, 2, 3, \text{...}\}</math> of [[natural numbers]], since the function <math>f(n) = 2n</math> is a bijection from {{tmath|\N}} to {{tmath|E}} (see picture).

For finite sets {{tmath|A}} and {{tmath|B}}, if ''some'' bijection exists from {{tmath|A}} to {{tmath|B}}, then ''each'' injective or surjective function from {{tmath|A}} to {{tmath|B}} is a bijection. This is no longer true for infinite {{tmath|A}} and {{tmath|B}}. For example, the function {{tmath|g}} from {{tmath|\N}} to {{tmath|E}}, defined by <math>g(n) = 4n</math> is injective, but not surjective since 2, for instance, is not mapped to, and {{tmath|h}} from {{tmath|\N}} to {{tmath|E}}, defined by <math>h(n) = 2 \operatorname{floor}(n/2)</math> (see: ''[[floor function]]'') is surjective, but not injective, since 0 and 1 for instance both map to 0. Neither {{tmath|g}} nor {{tmath|h}} can challenge <math>|E| = |\N|,</math> which was established by the existence of {{tmath|f}}.

==== Equivalence ====
[[File:Example for a composition of two functions.svg|thumb|Example for a composition of two functions.|282x282px]]
A fundamental result often used for cadinality is that of an [[equivalence relation]]. A binary [[Relation (mathematics)|relation]] is an equvalence relation if it satisfies the three basic properties of equality: [[Reflexive relation|reflexivity]], [[Symmetric relation|symmetry]], and [[Transitive relation|transitivity]]. A relation <math>R</math> is reflexive if, for any <math>a,</math> <math>aRa</math> (read: <math>a</math> is <math>R</math>-related to <math>a</math>); symmetric if, for any <math>a</math> and <math>b,</math> if <math>aRb,</math> then <math>bRa</math> (read: if <math>a</math> is related to <math>b,</math> then <math>b</math> is related to <math>a</math>); and transitive if, for any <math>a,</math> <math>b,</math> and <math>c,</math> if <math>aRb</math> and <math>bRc,</math> then <math>aRc.</math>

Given any set <math>A,</math> there is a bijection from <math>A</math> to itself by the [[identity function]], therefore cardinality is reflexive. Given any sets <math>A</math> and <math>B,</math> such that there is a bijection <math>f</math> from <math>A</math> to <math>B,</math> then there is an [[inverse function]] <math>f^{-1}</math> from <math>B</math> to <math>A,</math> which is also bijective, therefore cardinality is symmetric. Finally, given any sets <math>A,</math> <math>B,</math> and <math>C</math> such that there is a bijection <math>f</math>  from <math>A</math> to <math>B,</math> and <math>g</math> from <math>B</math> to <math>C,</math> then their [[Function composition|composition]] <math>g \circ f</math> (read: <math>g</math> after <math>f</math>) is a bijection from <math>A</math> to <math>C,</math> and so cardinality is transitive. Thus, cardinality forms an equivalence relation. This means that cardinality [[Partition of a set|partitions sets]] into [[equivalence classes]], and one may assign a representative to denote this class. This motivates the notion of a [[Cardinality#Cardinal numbers|cardinal number]].

Somewhat more formally, a relation must be a certain set of [[ordered pairs]]. Since there is no [[set of all sets]] in standard set theory (see: ''{{section link||Cantor's paradox}}''), cardinality is not a relation in the usual sense, but a [[Predicate (logic)|predicate]] or a relation over [[Class (set theory)|classes]].

=== Inequality ===
A set <math>A</math> is not larger than a set <math>B</math> if it can be mapped into <math>B</math> without overlap. That is, the cardinality of <math>A</math> is less than or equal to the cardinality of <math>B</math> if there is an [[injective function]] from <math>A</math> to '''<math>B</math>'''. This is written <math>A \preceq B,</math> or <math>|A| \leq |B|.</math> If <math>A \preceq B,</math> but there is no injection from <math>B</math> to <math>A,</math> then <math>A</math> is said to be ''strictly'' smaller than <math>B,</math> written without the underline as <math>A \prec B</math> or <math>|A| < |B|.</math> For example, if <math>A</math> has four elements and <math>B</math> has five, then the following are true <math>A \preceq A,</math> <math>A \preceq B,</math> and <math>A \prec B.</math>

For example, the set {{tmath|\N}} of all [[natural numbers]] has cardinality strictly less than its [[power set]] {{tmath|\mathcal P (\N)}}, because <math>g(n) = \{n\}</math> is an injective function from {{tmath|\N}} to {{tmath|\mathcal P (\N)}}, and it can be shown that no function from {{tmath|\N}} to {{tmath|\mathcal P (\N)}} can be bijective (see picture). By a similar argument, {{tmath|\N}} has cardinality strictly less than the cardinality of the set {{tmath|\R}} of all [[real number]]s. For proofs, see [[Cantor's diagonal argument]] or [[Cantor's first uncountability proof]].

If <math>|A| \leq |B|</math> and <math>|B| \leq |A|,</math> then <math>|A| = |B|</math> (a fact known as the [[Schröder–Bernstein theorem]]). The [[axiom of choice]] is equivalent to the statement that  <math>|A| \leq |B|</math> or <math>|B| \leq |A|</math> for every {{tmath|A}} and {{tmath|B}}.<ref>{{citation | author=Friedrich M. Hartogs | author-link=Friedrich M. Hartogs | editor=Felix Klein | editor-link=Felix Klein |editor2=Walther von Dyck |editor2-link=Walther von Dyck |editor3=David Hilbert |editor3-link=David Hilbert |editor4=Otto Blumenthal |editor4-link=Otto Blumenthal | title=Über das Problem der Wohlordnung | journal=[[Mathematische Annalen]] | volume=76 | number=4 | publisher=B.&nbsp;G. Teubner | location=Leipzig | year=1915 | pages=438–443 | issn=0025-5831 |url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0076&DMDID=DMDLOG_0037&L=1 | doi=10.1007/bf01458215| s2cid=121598654 }}</ref><ref>{{citation | author=Felix Hausdorff | author-link=Felix Hausdorff | editor=Egbert Brieskorn | editor-link=Egbert Brieskorn |editor2=Srishti D. Chatterji| title=Grundzüge der Mengenlehre | edition=1. | publisher=Springer | location=Berlin/Heidelberg | year=2002 | pages=587 | isbn=3-540-42224-2| url=https://books.google.com/books?id=3nth_p-6DpcC|display-editors=etal}} - [https://jscholarship.library.jhu.edu/handle/1774.2/34091 Original edition (1914)]</ref>

=== Countable sets ===
{{Main|Countable set}}
A set is called ''[[countable]]'' if it is [[Finite set|finite]] or has a bijection with the set of [[natural number]]s <math>(\N),</math> in which case it is called ''countably infinite''. The term ''[[denumerable]]'' is also sometimes used for countably infinite sets. 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 a [[proper subset]]. Similarly, the set of [[square numbers]] is countable, which was considered paradoxical for hundreds of years before modern set theory (see: ''{{section link||Pre-Cantorian Set theory}}''). However, several other examples have historically been considered surprising or initially unintuitive since the rise of set theory.

{{Multiple image
| direction         = horizontal
| image1            = Diagonal argument.svg
| image2            = Straight counter-clockwise spiral path in square grid.png
| total_width       = 330
| footer            = Two images of a visual depiction of a function from <math>\N</math> to <math>\Q.</math> On the left, a version for the positive rational numbers. On the right, a spiral for all pairs of integers <math>p/q.</math>
}}

The [[rational numbers]] <math>(\Q)</math> are those which can be expressed as the [[quotient]] or [[Fraction (mathematics)|fraction]] {{tmath|\tfrac p q}} of two [[integer]]s. The rational numbers can be shown to be countable by considering the set of fractions as the set of all [[ordered pairs]] of integers, denoted <math>\Z\times\Z,</math> which can be visualized as the set of all [[Integer lattice|integer 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. These technically over cover the rationals, since, for example, the rational number <math display="inline">\frac{1}{2}</math> gets mapped to by all the fractions <math display="inline">\frac{2}{4},\, \frac{3}{6}, \, \frac{4}{8}, \, \dots ,</math> as the grid method treats these all as distinct ordered pairs. So this function shows <math>|\Q| \leq |\N|</math> not <math>|\Q| = |\N|.</math> This can be corrected by "skipping over" these numbers in the grid, or by designing a function which does this naturally, but these menthods are usually more complicated.
[[File:Algebraicszoom.png|thumb|273x273px|Algebraic numbers on the [[complex plane]], colored by degree]]
A number is called [[Algebraic number|algebraic]] if it is a solution of some [[polynomial]] equation (with integer [[coefficient]]s). For example, the [[square root of two]] <math>\sqrt2</math> is a solution to <math>x^2 - 2 = 0,</math> and the rational number <math>p/q</math> is the solution to <math>qx - p = 0.</math> Conversely, a number which cannot be the root of any polynomial is called [[Transcendental number|transcendental]]. Two examples include [[Euler's number]] (''{{mvar|e}}'') and [[Pi|pi ({{pi}})]]. In general, proving a number is trancendental 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 (for example, see ''{{slink|Cantor'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.

=== Uncountable sets ===
{{Main|Uncountable set}}
[[File:Diagonal argument powerset svg.svg|thumb|250px|<math>\N</math> does not have the same cardinality as its [[power set]] <math>\mathcal{P}(\N)</math>: For every function ''f'' from '''<math>\N</math>''' to <math>\mathcal{P}(\N)</math>, the set <math>T = \{n \in N : n \notin f(n) \}</math> disagrees with every set in the [[range of a function|range]] of <math>f</math>, hence <math>f</math> cannot be surjective. The picture shows an example <math>f</math> and the corresponding <math>T</math>; {{color|#800000|'''red'''}}: <math>n \notin T</math>, {{color|#000080|'''blue'''}}: <math>n \in T</math>.]]A set is called ''[[uncountable]]'' 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 of [[real numbers]] <math>(\R)</math>, which can be understood as the set of all numbers on the [[number line]]. One method of proving that the reals are uncountable is called [[Cantor's diagonal argument]], credited to Cantor for his 1891 proof,<ref name="Cantor.1891">{{cite journal |author=Georg Cantor |year=1891 |title=Ueber eine elementare Frage der Mannigfaltigkeitslehre |url=https://www.digizeitschriften.de/dms/img/?PID=GDZPPN002113910&physid=phys84#navi |journal=[[Jahresbericht der Deutschen Mathematiker-Vereinigung]] |volume=1 |pages=75–78}} English translation: {{cite book |title=From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, Volume 2 |publisher=Oxford University Press |year=1996 |isbn=0-19-850536-1 |editor-last=Ewald |editor-first=William B. |pages=920–922}}</ref> though his differs from the more common presentation.

It begins by assuming, [[Proof by contradiction|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 <math>[0,1]</math>). Then, take the [[decimal expansion]]s of each real number, which looks like <math>0.d_1d_2d_3...</math> Considering these real numbers in a column, 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. We also need to make sure that the number we create has a unique decimal representation, that is, it cannot end in [[0.999...|repeated nines]]. For example, if the digit isn't a 7, make the digit of the new number a 7, and if it was a seven, make it a 3.<ref>{{Cite book |last=Bloch |first=Ethan D. |url=https://link.springer.com/book/10.1007/978-1-4419-7127-2 |title=Proofs and Fundamentals |date=2011 |publisher=Springer Science+Business Media |series=Undergraduate Texts in Mathematics |pages=242–243 |language=en |doi=10.1007/978-1-4419-7127-2 |isbn=978-1-4419-7126-5 |issn=0172-6056 |archive-url=https://archive.org/details/proofsfundamenta0002bloc/ |archive-date=2022-01-22}}</ref> 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.<ref>{{Cite book|last1=Ashlock |first1=Daniel |last2=Lee |first2=Colin |date=2020 |title=An Introduction to Proofs with Set Theory |url=https://link.springer.com/book/10.1007/978-3-031-02426-9 |publisher=Springer Cham |series=Synthesis Lectures on Mathematics & Statistics |language=en |pages=181–182 |doi=10.1007/978-3-031-02426-9 |isbn=978-3-031-01298-3 |issn=1938-1743}}</ref>

Another classical example of an uncountable set, established using a related reasoning, is the [[power set]] of the natural numbers, denoted <math>\mathcal{P}(\N)</math>. This is the set of all [[subsets]] of <math>\N</math>, including the [[empty set]] and <math>\N</math> itself. The method is much much closer to Cantor's original diagonal argument. Consider any function <math>f: \N \to \mathcal{P}(\N)</math>. One may define a subset <math>T \subseteq \N</math> which cannot be in the image of <math>f</math> by: if <math>1 \in f(1)</math>, then <math>1 \notin T</math>, and if <math>2 \notin f(2) </math>, then <math>2 \in T</math>, and in general, for each natural number <math>n</math>, <math>n \in T</math> if and only if <math>n \notin f(n) </math>. Then if the subset <math>T = f (t)</math> was in the image of <math>f</math>, then <math>t \in f (t) \iff t \notin f (t)</math> a contradiction. So <math>f</math> cannot be surjective. Therefore no bijection can exist between <math>\N</math> and <math>\mathcal{P}(\N)</math>. Thus <math>\mathcal{P}(\N)</math> must be not be countable. The two sets, <math>\R</math> and <math>\mathcal{P}(\N)</math> can be shown to have the same cardinality (by, for example, assigning each subset to a decimal expansion). Whether there exists a set <math>A</math> with cardinality between these two sets <math>|\N| < |A| < |\R|</math> is known as the [[continuum hypothesis]].

[[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 <math>A</math>, if <math>f</math> is a function from <math>A</math> to <math>\mathcal{P}(A)</math>, let the subset <math>T \subseteq A</math> be given by <math>T = \{ a \in A : a \notin f(a) \}</math>. If <math>T = f (t)</math>, then <math>t \in f (t) \iff t \notin f (t)</math> a contradiction. So <math>f</math> cannot be surjective and thus cannot be a bijection. So <math>|A| < |\mathcal{P}(A)|</math>. (Notice that a trivial injection exists -- map <math>a</math> to <math>\{ a \}</math>.) Further, since <math>\mathcal{P}(A)</math> is itself a set, the argument can be repeated to show <math>|A| < |\mathcal{P}(A)| < |\mathcal{P}(\mathcal{P}(A))|</math>. Taking <math>A = \N</math>, this shows that <math>\mathcal{P}(\mathcal{P}(\N))</math> is even larger than <math>\mathcal{P}(\N) </math>, which was already shown to be uncountable. Repeating this argument shows that there are infinitely many "sizes" of infinity.