Editing Cardinality (section)

==Cardinal numbers==
{{main|Cardinal number}}In the above section, "cardinality" of a set was defined relationally. In other words, while it was closely tied to the concept of number, the meaning of "number of elements" has not yet been defined. This can be formalized from basic set-theoretic principles, relying on some number-like structures. For finite sets, this is simply the [[natural number]] found by counting the elements. This number is called the ''cardinal number'' of that set, or simply ''the cardinality'' of that set. The cardinal number of a set <math>A</math> is generally denoted by <math>|A|,</math> with a [[vertical bar]] on each side,<ref name=":7">{{Cite web |title=Cardinality {{!}} Brilliant Math & Science Wiki |url=https://brilliant.org/wiki/cardinality/ |access-date=2020-08-23 |website=brilliant.org |language=en-us}}</ref> though it may also be denoted by <math>n(A),</math> <span style="border-top: 3px double;"><math>A</math></span>, <math>\operatorname{card}(A),</math> or <math>\#A.</math> 

For infinite sets, "cardinal number" is somewhat more difficult to define formally. However, cardinal numbers are not usually thought of in terms of their formal definition, but immaterially in terms of their arithmetic/algebraic properties. For example, defining <math>|\N| = \aleph_0</math>, and <math>A \sim B</math> if and only if <math>|A| = |B| </math>. Then <math>2^{\aleph_0} = |\mathcal{P}(\N)| \sim |\R|. </math>

=== 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 cannot also have cardinality 5. Intuitively meaning that a set cannot have both exactly 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>

==== Combinatorics ====
{{Main|Combinatorial principles}}
[[File:Inclusion-exclusion.svg|thumb|[[Inclusion–exclusion]] illustrated for three sets.]]
[[Combinatorics]] is the area of mathematics primarily concerned with [[counting]], both as a means and as an end to obtaining results, and certain properties of finite structures. The notion cardinality of finite sets is closely tied to many basic [[combinatorial principles]], and provides a set-theoretic foundation to prove them. The above shows uniqueness of finite cardinal numbers, and therefore, <math>A \sim B</math> if and only if <math>|A| = |B|</math>, formalizing the notion of a [[bijective proof]]. 

The [[addition principle]] asserts that given [[Disjoint sets|disjoint]] sets <math>A</math> and <math>B</math>, <math>|A \cup B| = |A| + |B|</math>, intuitively meaning that the sum of parts is equal to the sum of the whole. The [[multiplication principle]] asserts that given two sets <math>A</math> and <math>B</math>, <math>|A \times B| = |A| \cdot |B|</math>, intuitively meaning that there are <math>|A| \cdot |B|</math> ways to pair objects from these sets. Both of these can be proven by a bijective proof, together with induction. The more general result is the [[inclusion–exclusion principle]], which defines how to count the number of elements in overlaping sets.

=== 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, denoted <math>1 < 2 < 3.</math> Then, one defines 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>  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. Further, <math>\omega+1 := \{1,2,\cdots,\omega\}</math>, and so on.

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|Continuum hypothesis}}
[[File:Number line.png|thumb|The [[number line]], containing all points in its continuum.|314x314px]]
The [[number 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 order|dense]] and [[Archimedean property|archimedian]]) and the absence of any gaps ([[Completeness of the real numbers|completeness]]), This intuitive construct is formalized by the set of [[real numbers]] <math>(\R)</math> which model the continuum as a complete, densely ordered, uncountable set. 
[[File:Cantor set binary tree.svg|thumb|262x262px|First five itterations approaching the Cantor set]]
The [[Cardinality of the continuum|cardinality of the]] [[Cardinality of the continuum|continuum]], denoted by "<math>\mathfrak c</math>" (a lowercase [[fraktur (script)|fraktur script]] "c"), remains invariant under various transformations and mappings, many considered surprising. For example, all intervals on the real line e.g. <math>[0,1]</math>, and <math>[0,2]</math>, have the same cardinality as the entire set <math>\R</math>. First, <math>f(x) = 2x</math> is a bijection from <math>[0,1]</math> to <math>[0,2]</math>. Then, the [[tangent function]] is a bijection from the interval <math display="inline">\left( \frac{-\pi}{2} \, ,  \frac{\pi}{2} \right)</math> to the whole real line. A more surprising example is the [[Cantor set]], which is defined as follows: take the interval <math>[0,1]</math> and remove the middle third <math display="inline">\left( \frac{1}{3}, \frac{2}{3} \right)</math>, 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 in [[Ternary numeral system|ternary]] without a 1. Reinterpreting these decimal expansions as [[Binary number|binary]] (e.g. by replacing the 2s with 1s) gives a bijection between the Cantor set and the interval <math>[0,1]</math>.
[[File:Peanocurve.svg|thumb|339x339px|Three iterations of a [[Peano curve]] construction, whose [[Limit of a sequence|limit]] is a [[space-filling curve]].]]
[[Space-filling curves]] are continuous surjective maps from the [[unit interval]] <math>[0,1]</math> onto the [[unit square]] on <math>\R^2</math>, with classical examples such as the [[Peano curve]] and [[Hilbert curve|Hilbert]] [[Hilbert curve|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 <math>|\R| = |\R^n| = \mathfrak{c}</math> for any dimension <math>n \geq 1.</math> The infinite [[cartesian product]] <math>\R^\infty</math>, can also be shown to have cardinality <math>\mathfrak c</math>. This can be established by cardinal exponentiation: <math>|\R^\infty| = \mathfrak{c}^{\aleph_0} = \left(2^{\aleph_0} \right)^{\aleph_0} = 2^{(\aleph_0 \cdot \aleph_0)} = 2^{\aleph_0} = \mathfrak{c} = |\R|</math>.  Thus, the real numbers, all finite-dimensional real spaces, and the countable cartesian product share the same cardinality.

As shown in {{slink||Unountable sets}}, the set of real numbers is strictly larger than the set of natural numbers. Specifically, <math>|\R| = |\mathcal{P}(\N)|  </math>. The [[Continuum Hypothesis]] (CH) asserts that the real numbers have the next largest cardinality after the natural numbers, that is <math>|\R| = \aleph_1</math>. As shown by [[Kurt Gödel|Gödel]] and [[Paul Cohen|Cohen]], 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 [[Consistency|consistent]].<ref>{{Cite journal |last=Cohen |first=Paul J. |date=December 15, 1963 |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 |pages=1143–1148 |bibcode=1963PNAS...50.1143C |doi=10.1073/pnas.50.6.1143 |jstor=71858 |pmc=221287 |pmid=16578557 |doi-access=free}}</ref><ref>{{Cite journal |last=Cohen |first=Paul J. |date=January 15, 1964 |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 |pages=105–110 |bibcode=1964PNAS...51..105C |doi=10.1073/pnas.51.1.105 |jstor=72252 |pmc=300611 |pmid=16591132 |doi-access=free}}</ref><ref>{{Citation |last=Penrose |first=R |title=The Road to Reality: A Complete Guide to the Laws of the Universe |year=2005 |publisher=Vintage Books |isbn=0-09-944068-7 |author-link=Roger Penrose}}</ref> The [[Generalized Continuum Hypothesis]] (GCH) extends this to all infinite cardinals, stating that <math>2^{\aleph_\alpha} = \aleph_{\alpha+1}</math> for every ordinal <math>\alpha</math>. Without GHC, the cardinality of <math>\R</math> cannot be written in terms of alephs. The [[Beth numbers]] provide a concise notation for powersets of the real numbers starting from <math>\beth_1 = |\R|</math>, then <math>\beth_2 = |\mathcal{P}(\R)| = 2^{\beth_1}</math>, and in general <math>\beth_{n+1} = 2^{\beth_n}</math>.