Mathematics · Ch 1 — Relations and Functions

Summary

A relation from set $A$ to set $B$ is a subset of $A \times B$ . The domain is the set of all first coordinates, the range is the set of all second coordinates, and the codomain is $B$ .
A relation is a function $f: A \to B$ if every element of $A$ has exactly one image in $B$ . The domain is $A$ , the codomain is $B$ , and the range is $\{ f(x) : x \in A \}$ .
A function is one-one (injective) if $f(x_1) = f(x_2) \implies x_1 = x_2$ ; onto (surjective) if its range equals its codomain; and bijective if it is both one-one and onto.
The composition of two functions $f: A \to B$ and $g: B \to C$ is $(g \circ f)(x) = g(f(x))$ , defined only when the range of $f$ is a subset of the domain of $g$ .
A function $f: A \to B$ is invertible iff it is bijective. Its inverse $f^{-1}: B \to A$ satisfies $f^{-1}(y) = x$ exactly when $f(x) = y$ .
The empty relation $\emptyset$ and the universal relation $A \times B$ are special cases. The identity relation on $A$ is $\{ (a,a) : a \in A \}$ .
For any function, the image of a subset $X \subseteq A$ is $f(X) = \{ f(x) : x \in X \}$ , and the preimage of $Y \subseteq B$ is $f^{-1}(Y) = \{ x \in A : f(x) \in Y \}$ .
The number of relations from $A$ to $B$ is $2^{|A| \cdot |B|}$ ; the number of functions from $A$ to $B$ is $|B|^{|A|}$ . …