Editing Cardinality (section)

=== 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.