Mathematics · Ch 1 — Relations and Functions

Summary

Relation: A subset of $A \times B$ . Types: reflexive ( $aRa$ ), symmetric ( $aRb \implies bRa$ ), transitive ( $aRb, bRc \implies aRc$ ). An equivalence relation satisfies all three.
Equivalence class $[a]$ : set of all elements related to $a$ in an equivalence relation. Partitions the set into disjoint classes.
Function: A relation where each $x \in A$ has a unique $f(x) \in B$ . Types: injective (one-one: $f(a)=f(b) \implies a=b$ ), surjective (onto: every $y \in B$ has some $x$ ), bijective (both).
Composition $(g \circ f)(x) = g(f(x))$ : associative, but not commutative. $f$ and $g$ bijective $\implies g \circ f$ bijective.
Inverse function $f^{-1}$ exists iff $f$ is bijective. Then $f^{-1}(y) = x$ where $f(x)=y$ , and $f^{-1} \circ f = I_A$ , $f \circ f^{-1} = I_B$ . …