* ordered pair
(a, b) = {{a}, {a, b}}

* binary relation
A set R is a binary relation if all elements of R are ordered pairs.

* Cartesian product
A × B = { (a, b) | a ∈ A and b ∈ B}
So, cartesian product of A and B is a relation in which every element of A is related to every element of B.

proof of existence: A × B = { (a, b) ∈ P(P(A ∪ B)) | a ∈ A and b ∈ B}

* function
A binary relation F is a function if aFb and aFc implies b = c for any a, b, and c.
In other words, a binary relation F is a function iff for every a from domain of F there is exactly one b such that aFb.

* classification of functions
f: A -> B is
surjective (or onto) if range of f is equal to the codomain B.
injective (or one-to-one) if a != b then f(a) != f(b).
bijective if f is surjective and injective.

* Mapping rule for counting
If f: A -> B is
surjective, then |A| >= |B|;
injective, then |A| <= |B|;
bijective, then |A| = |B|.

* pigeonhole principle
If more than n pigeons fly into n pigeonholes, then at least 2 pigeons must fly into some hole.

If |A| > |B|, then no function f: A -> B is injective.

If |A| > k|B|, then every function f: A -> B maps at least k+1 different elements of A to the same element of B.