Cardinality.md (719B)
1 +++ 2 title = 'Cardinality' 3 +++ 4 # Cardinality (notion of size) 5 |A| cardinality of A (size) 6 7 - |A| ≤ |B| ⟷ there exists a total injection f: A ➝ B 8 - |A| = |B| ⟷ there exists a bijection f: A ➝ B 9 - |A| = #A = m ⟷ there exists a bijection f: {1,…,m} ➝ A 10 11 ## Cantor-Schroeder-Bernstein theorem (partial ordering of sets) 12 if there exist total injective functions f: A ➝ B, g: B ➝ A 13 14 then there exists a bijection h: A ➝ B 15 16 so sets can be partially ordered by cardinality. 17 18 ## Countable/Uncountable 19 set A is: 20 21 - countably infinite — there exists a bijection f: Nat ➝ A 22 - countable — A is finite or countably infinite 23 - uncountable — A is not countable 24 25 if a set is countable, it can be enumerated