Relations and Functions Mind Map

A relation R on a set A is a subset of A × A. It is reflexive if every a in A satisfies (a, a) in R, symmetric if (a, b) in R implies (b, a) in R, and transitive if (a, b) in R and (b, c) in R imply (a, c) in R. A relation that is reflexive, symmetric, and transitive is an equivalence relation.

Write the property test in symbols before applying it. For a relation on A, the diagonal checklist (a, a) for all a in A is the fastest way to test reflexivity.

If R is an equivalence relation on a set A, the equivalence class of an element a in A is [a] = {x in A : x R a}. Equivalence classes are non-empty, pairwise disjoint or identical, and together they partition A.

After finding a class, check whether a new representative is already included in an earlier class. If yes, it does not create a new class.

A function f: A to B is one-one if different elements of A have different images in B. It is onto if every element of B has a preimage in A. It is bijective if it is both one-one and onto.

For one-one, start with f(a) = f(b). For onto, start with y = f(x) and solve for x in the domain.

For functions f: A to B and g: B to C, the composition g∘f is defined by (g∘f)(x) = g(f(x)) for x in A. The output of f must be suitable as an input for g.

Read g∘f from right to left for calculation: first f, then g. Also check whether the range of the first function fits the domain of the second.

A function f: A to B is invertible if there exists a function f⁻¹: B to A such that f⁻¹(f(x)) = x for every x in A and f(f⁻¹(y)) = y for every y in B. A function is invertible if and only if it is bijective.

Before writing f⁻¹, state why f is one-one and onto, or use the given fact that it is bijective. For restricted domains, keep the restricted range in mind.