Editing Cardinality (section)

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