Cardinality

Informally the cardinality of a set is the number of things in it.

The cardinality of a set [ilmath]A[/ilmath] is denoted [math]|A|[/math]

Equipotent cardinality ([math]|A|=|B|[/math])

[ilmath]A[/ilmath] and [ilmath]B[/ilmath] are equipotent (have the same cardinality, [math]|A|=|B|[/math]) if there is a one-to-one (injective) function with domain [ilmath]A[/ilmath] and range [ilmath]B[/ilmath], note it need not be a bijective function, for example if [math]B\subset C[/math] then [math]f:A\rightarrow C[/math] can still be injective, but would not be surjective if [math]\exists x(x\in C\wedge x\notin B)[/math], thus not bijective.

This is an equivalence relation

Less than or equal to ([math]|A|\le|B|[/math])

There is an injective mapping from [ilmath]A[/ilmath] into [ilmath]B[/ilmath], it differs from equality in that the range need not be the entire of [ilmath]B[/ilmath]

Cantor-Bernstein Theorem ([math][|A|\le |B|\wedge |B|\le |A|]\implies|A|=|B|[/math] )

---

TODO: Cantor-Bernstein Theorem

---

Addition

We define the sum of cardinals [ilmath]a[/ilmath] and [ilmath]b[/ilmath] to be:

[math]a+b=|A\cup B|[/math] where [math]a=|A|[/math], [math]b=|B|[/math] and [math]A\cap B=\emptyset[/math]

To be sure this definition is unique (that we can add cardinals if the intersection is empty) we require the following theorem:

Proof that if [math]A,B,A',B'[/math] are such that [math]|A|=|A'|[/math] and [math]|B|=|B'|[/math] and [math]A\cap B=A'\cap B'=\emptyset[/math] that [math]|A\cup B|=|A'\cup B'|[/math]

---

---

TODO: Easy - as cardinality of A and A' are equal there's a 1:1 function, we take the union, which is 1:1 from [math]A\cup B\mapsto A'\cup B'[/math]

---