# Cardinality

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

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

## Equipotent cardinality ($|A|=|B|$)

[ilmath]A[/ilmath] and [ilmath]B[/ilmath] are equipotent (have the same cardinality, $|A|=|B|$) 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 $B\subset C$ then $f:A\rightarrow C$ can still be injective, but would not be surjective if $\exists x(x\in C\wedge x\notin B)$, thus not bijective.[1]

This is an equivalence relation

## Less than or equal to ($|A|\le|B|$)

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 ($[|A|\le |B|\wedge |B|\le |A|]\implies|A|=|B|$ )

TODO: Cantor-Bernstein Theorem

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

$a+b=|A\cup B|$ where $a=|A|$, $b=|B|$ and $A\cap B=\emptyset$

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 $A,B,A',B'$ are such that $|A|=|A'|$ and $|B|=|B'|$ and $A\cap B=A'\cap B'=\emptyset$ that $|A\cup B|=|A'\cup B'|$

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 $A\cup B\mapsto A'\cup B'$

## References

1. p65 - Introduction to Set Theory, third edition, Hrbacek and Jech