Cardinality (notion of size)

|A| cardinality of A (size)

• |A| ≤ |B| ⟷ there exists a total injection f: A ➝ B
• |A| = |B| ⟷ there exists a bijection f: A ➝ B
• |A| = #A = m ⟷ there exists a bijection f: {1,…,m} ➝ A

Cantor-Schroeder-Bernstein theorem (partial ordering of sets)

if there exist total injective functions f: A ➝ B, g: B ➝ A

then there exists a bijection h: A ➝ B

so sets can be partially ordered by cardinality.

Countable/Uncountable

set A is:

• countably infinite — there exists a bijection f: Nat ➝ A
• countable — A is finite or countably infinite
• uncountable — A is not countable

if a set is countable, it can be enumerated