Cardinality
Cardinality is a generalization of set size.
Contents
Description
Given a countable set, the concept of 'size' is intuitive. Consider a set A containing the natural numbers up to n: A = {1,2,...,n}. The cardinality of A is n: |A| = n.
Note also that ∅ is considered to have cardinality of 0.
To generalize the concept to infinite sets, functions are utilized. Given two sets A and B:
If an injective function exists such that f : A -> B, then |A| ≤ |B|.
If a bijective function exists such that f : A -> B, then |A| = |B|.
More formally: if injective functions f : A -> B and g : B -> A exist, then |A| ≤ |B| and |B| ≤ |A|, and finally |A| = |B|. This is the Cantor-Schröder-Bernstein theorem.
If |A| ≤ |B| but |A| != |B|, then clearly |A| < |B|.
If |A| = |N| (i.e., A can be mapped to the natural numbers), then A is countably infinite. Otherwise an infinite set is uncountable.
Note that the set of all integers (Z) and the set of all rational numbers (Q) can be proven to be countably infinite.
Properties
Cardinality is...
commutative: |A| = |B| -> |B| = |A|
transitive: |A| = |B| and |B| = |C| -> |A| = |C|