xSkill: notes, lectures and practice for CBSE and CSE

1.1 Definitions to keep on the tip of your tongue A relation R from set A to set B is any subset of the Cartesian product A \times B. Write it as a set of ordered pairs, as an arrow diagram, or as a rule. The set of first entries is the domain, the set of second entries is the range, and B is the codomain when R is a relation from A to B. A function f : A \to B is a relation in which every element of A has exactly one image in B. Functions are the special relations that pass the vertical line test on their graphs.

Domain of R = {a : (a, b) \in R}, Range of R = {b : (a, b) \in R}

Domain and range read straight off the ordered pairs

1.2 Equivalence relation checklist A relation R on a set A is an equivalence relation when all three conditions hold together. Check reflexivity first because it is the quickest to test.

Reflexive: (a, a) \in R \forall a \in A

Every element must be related to itself

Symmetric: (a, b) \in R \Rightarrow (b, a) \in R

One direction forces the reverse direction

Transitive: (a, b) \in R, (b, c) \in R \Rightarrow (a, c) \in R

Two steps can be replaced by one

R is equivalence ⟺ R is reflexive, symmetric and transitive

All three tests are needed, two out of three is not enough

1.3 Functions, images and inverses For f : X \to Y, the image of x is f(x). A one-one (injective) function never sends two different inputs to one output. An onto (surjective) function uses every element of Y. A bijection is both, and only a bijection can be reversed. Composition works right to left. If f : A \to B and g : B \to C, then gof : A \to C and gof(x) = g(f(x)). For an invertible function f, the inverse satisfies f⁻¹(f(x)) = x and f(f⁻¹(y)) = y.

f (x_{1}) = f (x_{2}) \Rightarrow x_{1} = x_{2} (one-one test)

Solve this implication to prove injectivity

For every y \in Y there is x \in X with f (x) = y

Surjectivity test on the codomain, not the range

(g o f) (x) = g (f (x)), (f o g) (x) = f (g (x))

Composition is not commutative in general

f^{- 1} (y) = x ⟺ f (x) = y

Definition of the inverse map

1.4 Counting results worth memorising From a set with m elements to a set with n elements there are 2 to the power mn relations, and n to the power m of them are functions. A one-one function needs n at least m, and then the count is n(n - 1)(n - 2) ... (n - m + 1). On a set with m elements the total number of relations is 2 to the power m², and the identity relation is the smallest equivalence relation on that set. Remember the range of 2x/(1 + x²) over the reals is [-1, 1]; board questions use it to ask about surjectivity.

Exam

Board papers rarely ask only for a definition. They give a rule and expect three labelled checks, then a conclusion. Write the reflexive check, the symmetric check and the transitive check as separate steps so the examiner can award each mark.