Editing Cardinality (section)

==Cardinal numbers==
{{main|Cardinal number}}In the above section, "cardinality" of a set was defined relationally. In other words, it was not defined as a specific object itself. However, such an object can be defined as follows.

=== Finite sets ===
{{main|Finite set}}
[[File:Bijection.svg|thumb|200x200px|A [[bijective function]], ''f'': ''X'' → ''Y'', from set ''X'' to set ''Y''  demonstrates that the sets have the same cardinality, in this case equal to the cardinal number 4.]]Given a basic sense of [[natural numbers]], a set is said to have cardinality <math>n</math> if it can be put in one-to-one correspondence with the set <math>\{1,\,2,\, \dots, \, n\}.</math> For example, the set <math>S = \{ A,B,C,D \} </math> has a natural correspondence with the set <math>\{1,2,3,4\},</math> and therefore is said to have cardinality 4. Other terminologies include "Its cardinality is 4" or "Its cardinal number is 4". While this definition uses a basic sense of natural numbers, it may be that cardinality is used to define the natural numbers, in which case, a simple construction of objects satisfying the [[Peano axioms]] can be used as a substitute. Most commonly, the [[Von Neumann ordinal]]s.

Showing that such a correspondence exists is not always trivial, which is the subject matter of [[combinatorics]].

==== Uniqueness ====
An intuitive property of finite sets is that, for example, if a set has cardinality 4, then it does not also have cardinality 5. Intuitively meaning that a set cannot have both exaclty 4 elements and exactly 5 elements. However, it is not so obviously proven. The following proof is adapted from ''Analysis I'' by [[Terence Tao]].{{Sfn|Tao|2022|p=59}}
[[File:Lemma function.png|thumb|Intuitive depiction of the function <math>g</math> in the lemma, for the case <math>|X| = 7.</math>]]
Lemma: If a set <math>X</math> has cardinality <math>n \geq 1,</math> and <math>x_0 \in X,</math> then the set <math>X - \{x_0\} </math> (i.e. <math>X</math> with the element <math>x_0</math> removed) has cardinality <math>n-1.</math>

Proof: Given <math>X</math> as above, since <math>X</math> has cardinality <math>n,</math> there is a bijection <math>f</math> from <math>X</math> to <math>\{1,\,2,\, \dots, \, n\}.</math> Then, since <math>x_0 \in X,</math> there must be some number <math>f(x_0)</math> in <math>\{1,\,2,\, \dots, \, n\}.</math> We need to find a bijection from <math>X - \{x_0\} </math> to <math>\{1, \dots n-1\}</math> (which may be empty). Define a function <math>g</math> such that <math>g(x) = f(x)</math> if <math>f(x) < f(x_0),</math> and <math>g(x) = f(x)-1</math> if <math>f(x) > f(x_0).</math> Then <math>g</math> is a bijection from <math>X - \{x_0\} </math> to <math>\{1, \dots n-1\}.</math>

Theorem: If a set <math>X</math> has cardinality <math>n,</math> then it cannot have any other cardinality. That is, <math>X</math> cannot also have cardinality <math>m \neq n.</math>

Proof: If <math>X</math> is empty (has cardinality 0), then there cannot exist a bijection from <math>X</math> to any nonempty set <math>Y,</math> since nothing mapped to <math>y_0 \in Y.</math> Assume, by [[Mathematical induction|induction]] that the result has been proven up to some cardinality <math>n.</math> If <math>X,</math> has cardinality <math>n+1,</math> assume it also has cardinality <math>m.</math> We want to show that <math>m = n+1.</math> By the lemma above, <math>X - \{x_0\} </math> must have cardinality <math>n</math> and <math>m-1.</math> Since, by induction, cardinality is unique for sets with cardinality <math>n,</math> it must be that <math>m-1 = n,</math> and thus <math>m = n+1.</math>

=== Aleph numbers ===
{{Main|Aleph number}}
[[File:Aleph0.svg|right|thumb|169x169px|[[Aleph-nought]], aleph-zero, or aleph-null: the smallest infinite cardinal number, and the cardinal number of the set of natural numbers. ]]
The [[aleph numbers]] are a sequence of cardinal numbers that denote the size of [[infinite sets]], denoted with an [[aleph]] <math>\aleph,</math> the first letter of the [[Hebrew alphabet]]. The first aleph number is <math>\aleph_0,</math> called "aleph-nought", "aleph-zero", or "aleph-null", which represents the cardinality of the set of all [[natural numbers]]: <math>\aleph_0 = |\N| = |\{0,1,2,3,\cdots\}| .</math>  Then, <math>\aleph_1</math> represents the next largest cardinality. The most common way this is formalized in set theory is through [[Von Neumann ordinal]]s, known as [[Von Neumann cardinal assignment]].

[[Ordinal number]]s generalize the notion of ''order'' to infinite sets. For example, 2 comes after 1, denoted <math>1 < 2,</math> and 3 comes after both, denote <math>1 < 2 < 3.</math> Then, one define a new number, <math>\omega,</math> which comes after every natural number, denoted <math>1 < 2 < 3 < \cdots < \omega.</math> Further <math>\omega < \omega+1 ,</math> and so on. More formally, these ordinal numbers can be defined as follows:

<math>0 := \{\},</math> the [[empty set]], <math>1 := \{0\} ,</math> <math>2 := \{0,1\},</math> <math>3 := \{0,1,2\},</math> and so on. Then one can define <math>m < n \text{, if } \, m \in n,</math> for examlpe, <math>2 \in \{0,1,2\} = 3,</math> therefore <math>2 < 3.</math>  Further, defining <math>\omega := \{0,1,2,3,\cdots\}</math> (a [[limit ordinal]]) gives <math>\omega</math> the desired property of being the smallest ordinal greater than all finite ordinal numbers.

Since <math>\omega \sim \N</math> by the natural correspondence, one may define <math>\aleph_0</math> as the set of all finite ordinals. That is, <math>\aleph_0 := \omega.</math> Then, <math>\aleph_1</math> is the set of all countable ordinals (all ordinals <math>\kappa</math> with cardinality <math>|\kappa| \leq \aleph_0</math>), the [[first uncountable ordinal]]. Since a set cannot contain itself, <math>\aleph_1</math> must have a strictly larger cardinality: <math>\aleph_0 < \aleph_1.</math> Furthermore, <math>\aleph_2</math> is the set of all ordinals with cardinality <math>\aleph_1,</math> and so on. By the [[well-ordering theorem]], there cannot exist any set with cardinality between <math>\aleph_0</math> and <math>\aleph_1,</math> and every infinite set has some cardinality corresponding to some aleph <math>\aleph_\alpha,</math> for some ordinal <math>\alpha.</math>

===Cardinality of the continuum===
{{main|Cardinality of the continuum}}
[[File:Number line.png|thumb|The [[number line]], containing all points in its continuum.]]
The cardinality of the [[real number]]s is denoted by "<math>\mathfrak c</math>" (a lowercase [[fraktur (script)|fraktur script]] "c"), and is also referred to as the [[cardinality of the continuum]]. Cantor showed, using the [[Cantor's diagonal argument|diagonal argument]], that <math>{\mathfrak c} >\aleph_0.</math> We can show that <math>\mathfrak c = 2^{\aleph_0},</math> this also being the cardinality of the set of all subsets of the natural numbers.

The [[continuum hypothesis]] says that <math>\aleph_1 = 2^{\aleph_0},</math> i.e. <math>2^{\aleph_0}</math> is the smallest cardinal number bigger than <math>\aleph_0,</math> i.e. there is no set whose cardinality is strictly between that of the integers and that of the real numbers. The continuum hypothesis is [[independence (mathematical logic)|independent]] of [[Zermelo–Fraenkel set theory with the axiom of choice|ZFC]], a standard axiomatization of set theory; that is, it is impossible to prove the continuum hypothesis or its negation from ZFC—provided that ZFC is consistent.<ref>{{Cite journal
 | first = Paul J. | last = Cohen
 | title = The Independence of the Continuum Hypothesis
 | journal = Proceedings of the National Academy of Sciences of the United States of America
 | volume = 50 | issue = 6 | date = December 15, 1963 | pages = 1143–1148
 | doi = 10.1073/pnas.50.6.1143
 | pmid = 16578557
 | pmc = 221287 | jstor=71858
 | bibcode = 1963PNAS...50.1143C
 | doi-access = free
 }}</ref><ref>{{Cite journal
 | first = Paul J. | last = Cohen
 | title = The Independence of the Continuum Hypothesis, II
 | journal = Proceedings of the National Academy of Sciences of the United States of America
 | volume = 51 | issue = 1 | date = January 15, 1964 | pages = 105–110
 | doi = 10.1073/pnas.51.1.105
 | pmid = 16591132
 | pmc = 300611 | jstor=72252
 | bibcode = 1964PNAS...51..105C
 | doi-access = free
 }}</ref><ref>{{Citation|first=R|last=Penrose|author-link=Roger Penrose|title=The Road to Reality: A Complete Guide to the Laws of the Universe|publisher=Vintage Books|year=2005|isbn=0-09-944068-7}}</ref>

One of Cantor's most important results was that the [[cardinality of the continuum]] (<math>\mathfrak{c}</math>) is greater than that of the natural numbers (<math>\aleph_0</math>); that is, there are more real numbers '''R''' than natural numbers '''N'''. Namely, Cantor showed that <math>\mathfrak{c} = 2^{\aleph_0} = \beth_1</math> (see [[Beth number#Beth one|Beth one]]) satisfies:
:<math>2^{\aleph_0} > \aleph_0</math>
:(see [[Cantor's diagonal argument]] or [[Cantor's first uncountability proof]]).

The [[continuum hypothesis]] states that there is no [[cardinal number]] between the cardinality of the reals and the cardinality of the natural numbers, that is,
:<math>2^{\aleph_0} = \aleph_1</math>

However, this hypothesis can neither be proved nor disproved within the widely accepted [[ZFC]] [[axiomatic set theory]], if ZFC is consistent.

The first of these results is apparent by considering, for instance, the [[tangent function]], which provides a [[one-to-one correspondence]] between the [[Interval (mathematics)|interval]] (−{{sfrac|1|2}}π, {{sfrac|1|2}}π) and '''R'''.

The second result was first demonstrated by Cantor in 1878, but it became more apparent in 1890, when [[Giuseppe Peano]] introduced the [[space-filling curve]]s, curved lines that twist and turn enough to fill the whole of any square, or cube, or [[hypercube]], or finite-dimensional space. These curves are not a direct proof that a line has the same number of points as a finite-dimensional space, but they can be used to obtain [[Space-filling curve#Proof that a square and its side contain the same number of points|such a proof]].

Cantor also showed that sets with cardinality strictly greater than <math>\mathfrak c</math> exist (see his [[Cantor's diagonal argument#General sets|generalized diagonal argument]] and [[Cantor's theorem|theorem]]). They include, for instance:

:* the set of all subsets of '''R''', i.e., the [[power set]] of '''R''', written ''P''('''R''') or 2<sup>'''R'''</sup>
:* the set '''R'''<sup>'''R'''</sup> of all functions from '''R''' to '''R'''

Both have cardinality
:<math>2^\mathfrak {c} = \beth_2 > \mathfrak c </math>
:(see [[Beth number#Beth two|Beth two]]).

The [[Cardinality of the continuum#Cardinal equalities|cardinal equalities]] <math>\mathfrak{c}^2 = \mathfrak{c},</math> <math>\mathfrak c^{\aleph_0} = \mathfrak c,</math> and <math>\mathfrak c ^{\mathfrak c} = 2^{\mathfrak c}</math> can be demonstrated using [[cardinal arithmetic]]:
:<math>\mathfrak{c}^2 = \left(2^{\aleph_0}\right)^2 = 2^{2\cdot{\aleph_0}} = 2^{\aleph_0} = \mathfrak{c},</math>
:<math>\mathfrak c^{\aleph_0} = \left(2^{\aleph_0}\right)^{\aleph_0} = 2^{{\aleph_0}\cdot{\aleph_0}} = 2^{\aleph_0} = \mathfrak{c},</math>
:<math> \mathfrak c ^{\mathfrak c} = \left(2^{\aleph_0}\right)^{\mathfrak c} = 2^{\mathfrak c\cdot\aleph_0} = 2^{\mathfrak c}.</math>