Summary

Summary

• A relation $R$ in a set $A$ is reflexive if $(a,a)\in R$ for every $a\in A$; symmetric if $(a,b)\in R \implies (b,a)\in R$; transitive if $(a,b),(b,c)\in R \implies (a,c)\in R$. The three properties are logically independent.
• An equivalence relation is reflexive, symmetric and transitive simultaneously. Its equivalence classes $[a] = \{x : x\,R\,a\}$ partition the set into disjoint blocks whose union is the whole set, and $[a]=[b]$ iff $a\,R\,b$.
• A function $f:A\to B$ is one-one (injective) if $f(x_1)=f(x_2)\implies x_1=x_2$; it is onto (surjective) if every $y\in B$ has some preimage in $A$, i.e. $\text{range}(f)=B$.
• A function that is both one-one and onto is a bijection. Restricting domain/codomain can convert a non-bijective function (e.g. $f(x)=x^2$ on $\mathbb{R}$) into a bijective one.
• The composite $(g\circ f)(x)=g(f(x))$ is generally not commutative ($f\circ g \neq g\circ f$) but is associative; its domain can be smaller than that of $f$ alone. …