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