Editing Cardinality (section)

==Comparing sets==

=== Introduction ===
[[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.]]
The basic notions of [[Set (mathematics)|sets]] and [[Function (mathematics)|functions]] are used to develop the concept of cardinality, and technical terms therein are used throughout this article. A [[Set (mathematics)|set]] can be understood as any collection of objects, usually represented with [[curly braces]]. For example, <math>S = \{1,2,3\}</math> specifies a set, called <math>S</math>, which contains the numbers 1, 2, and 3. The symbol <math>\in</math> represents set membership, for exmaple <math>1 \in S</math> says "1 is a member of the set <math>S</math>" which is true by the definition of <math>S</math> above.

A [[Function (mathematics)|function]] 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 of [[natural numbers]] to the set of [[even numbers]] by multiplying by 2. If a function does not map two elements to the same place, it is called [[injective]]. If a function covers every element in the output space, it is called [[surjective]]. If a function is both injective and surjective, it is called [[bijective]]. (For further clarification, see [[Bijection, injection and surjection|''Bijection, injection and surjection'']].)

===Equinumerosity===
{{Main|Equinumerosity}}
The intuitive property of two sets having the "same size" is that their objects can be paired one-to-one. For example, in [[Cardinality#top|the image above]], a set of apples is paired with a set of oranges, proving the sets are the same size without referring to these sets' "number of elements" at all. 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. In fact, it is often the case that functions are defined literally as this set of pairings (see ''{{slink|Function (mathematics)|Formal definition}}''). Thus, the following definition is given:

Two sets <math>A</math> and <math>B</math> are said to have the ''same cardinality'' if their elements can be paired one-to-one. That is, if there exists a function <math>f:A \mapsto B</math> which is bijective. This is written as <math>A \sim B,</math> <math>A \approx B,</math> <math>A \equiv B,</math> and eventually <math> |A| = |B| ,  </math> once <math>|A|</math> has been defined. Alternatively, these sets, <math>A </math> and <math> B,</math> may be said to be ''similar'', [[Equinumerous|''equinumerous'']], or ''equipotent''. 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 above).

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 property 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 necessary in developing a theory of cardinality is showing it is an [[equivalence relation]]. A binary [[Relation (mathematics)|relation]] is an equivalence 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 ===
[[File:Cantor-Bernstein.png|thumb|256x256px|[[Gyula Kőnig]]'s definition of a bijection {{color|#00c000|''h''}}:''A''&nbsp;→&nbsp;''B'' from the given injections {{color|#c00000|''f''}}:''A''&nbsp;→&nbsp;''B'' and {{color|#0000c0|''g''}}:''B''&nbsp;→&nbsp;''A''. ]]
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> <math>A \lesssim B</math> and eventually <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>

The basic properties of an inequality are reflexivity (for any <math>a,</math> <math>a \leq a</math>), transitivity (if <math>a \leq b</math> and <math>b \leq c,</math> then <math>a \leq c</math>) and [[Antisymmetric relation|antisymmetry]] (if <math>a \leq b</math> and <math>b \leq a,</math> then <math>a = b</math>) (See [[Inequality (mathematics)#Formal definitions and generalizations|''Inequality § Formal definitions'']]). Cardinal inequality <math>(\preceq)</math> as defined above is reflexive since the [[identity function]] is injective, and is transitive by function composition. Antisymmetry is established by the [[Schröder–Bernstein theorem]]. The proof roughly goes as follows. 

Given sets <math>A</math> and <math>B</math>, where <math>f:A \mapsto B</math> is the function that proves <math>A \preceq B</math> and <math>g: B \mapsto A</math> proves <math>B \preceq A</math>, then consider the sequence of points given by applying <math>f</math> then <math>g</math> over and over. Then we can define a bijection <math>h: A \mapsto B</math> as follows: If a sequence forms a cycle, begins with an element <math>a \in A</math> not mapped to by <math>g</math>, or extends infinitley in both directions, define <math>h(x) = f(x)</math> for each <math>x \in A</math> in those sequences. The last case, if a sequence begins with an element <math>b \in B</math>, not mapped to by <math>f</math>, define <math>h(x) = g^{-1}(x)</math> for each <math>x \in A</math> in that sequence. Then <math>h</math> is a bijection.

The above shows that cardinal inequality is a [[partial order]]. A [[total order]] has the additional property that, for any <math>a</math> and <math>b</math>, either <math>a \leq b</math> or <math>b \leq a.</math> This can be established by the [[well-ordering theorem]]. Every well-ordered set is uniquely [[order isomorphic]] to a unique [[ordinal number]], called the [[order type]] of the well-ordered set. Then, by comparing their order types, one can show that <math>A \preceq B</math> or <math>B \preceq A</math>. This result is equivalent to the [[axiom of choice]].<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 methods 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 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 (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 ===
{{hatnote group|{{Main|Uncountable set}}{{Further information|#Cardinality of the continuum}}}}
[[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...|repeating nines]] or repeating zeros. 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 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 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.