= Cardinality =

'''Cardinality''' is a generalization of [[Analysis/Sets|set]] size.

<<TableOfContents>>

----



== Description ==

Given a '''countable''' [[Analysis/Sets|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, [[Analysis/Functions|functions]] are utilized. Given two sets ''A'' and ''B'':

 * If an [[Analysis/Injectivity|injective]] function exists such that ''f : A -> B'', then ''|A| ≤ |B|''.
 * If a [[Analysis/Surjectivity|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|''



----
CategoryRicottone