Cardinalities of Sets
Definition: We say that two sets , have same cardinality if there exists some bijective function . Having same cardinality is a relationship between sets that has properties of equivalence relation.
Definition: For non-negative natural number we say that has cardinality $n$ if has same cardinality as . The only set with cardinality zero is the empty set .
Definition: A set if finite if it has cardinality for some natural number, otherwise it is infinite.
Observation: The set of all natural numbers is infinite.
Definition: A set is countably infinite if it has the same cardinality as the set of natural numbers. A set is countable if it is finite or countably infinite.
Theorem: if are countable then and are countable, but is not countable.
Observation: The set of all strings over some finite alphabet is countable.
Observation: The set of real numbers is not countable.
Observation: If the set is infinite and the set has at least two elements, then set of all functions is not countable.