# 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.