Cheatsheet Content
### Relations: Types - **Reflexive:** $(a, a) \in R$ for all $a \in A$. - **Symmetric:** If $(a, b) \in R$, then $(b, a) \in R$. - **Transitive:** If $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$. - **Equivalence Relation:** A relation that is reflexive, symmetric, and transitive. - **Equivalence Class:** For an equivalence relation $R$ on set $A$, the equivalence class of $a \in A$, denoted $[a]$, is the set of all elements $b \in A$ such that $(a, b) \in R$. - $[a] = \{b \in A : (a, b) \in R\}$. ### Functions: Types Let $f: A \to B$ be a function. - **One-to-One (Injective):** Different elements of $A$ have different images in $B$. - If $f(x_1) = f(x_2) \implies x_1 = x_2$. - **Onto (Surjective):** Every element in $B$ is the image of at least one element in $A$. - For every $y \in B$, there exists $x \in A$ such that $f(x) = y$. - **Bijective (One-to-one and Onto):** A function that is both injective and surjective. ### Composition & Inverse of Functions - **Composition of Functions:** Let $f: A \to B$ and $g: B \to C$. The composition $g \circ f: A \to C$ is defined by $(g \circ f)(x) = g(f(x))$. - **Properties:** - Associative: $(h \circ g) \circ f = h \circ (g \circ f)$ - Not necessarily commutative: $f \circ g \neq g \circ f$ - **Inverse of a Function:** A function $f: A \to B$ is invertible if and only if it is bijective. - If $f$ is invertible, then there exists a unique function $g: B \to A$ such that $f \circ g = I_B$ and $g \circ f = I_A$, where $I_A$ and $I_B$ are identity functions on $A$ and $B$ respectively. - The inverse function is denoted by $f^{-1}$. - **Properties:** - $(f^{-1})^{-1} = f$ - $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ ### Binary Operations - **Definition:** A binary operation $*$ on a set $A$ is a function $*: A \times A \to A$. - Denoted by $a * b$. - **Commutative:** $a * b = b * a$ for all $a, b \in A$. - **Associative:** $(a * b) * c = a * (b * c)$ for all $a, b, c \in A$. - **Identity Element:** An element $e \in A$ such that $a * e = e * a = a$ for all $a \in A$. - If it exists, the identity element is unique. - **Inverse Element:** For an operation with identity $e$, an element $b \in A$ is the inverse of $a \in A$ if $a * b = b * a = e$. - If it exists, the inverse element is unique.
