In this chapter, you study different types of relations and equivalence relation, composition of functions, invertible functions and binary operations.
Empty relation is the relation R in X given by R = φ ⊂ X × X.
Universal relation is the relation R in X given by R = X × X.
Reflexive relation R in X is a relation with (a, a) ∈ R ∀ a ∈ X.
Symmetric relation R in X is a relation satisfying (a, b) ∈ R implies (b, a) ∈ R.
Transitive relation R in X is a relation satisfying (a, b) ∈ R and (b, c) ∈ R implies that (a, c) ∈ R.
Equivalence relation R in X is a relation which is reflexive, symmetric and transitive.
Equivalence class [a] containing a ∈ X for an equivalence relation R in X is the subset of X containing all elements b related to a.
A function f : X → Y is one-one (or injective) if f(x1) = f(x2) ⇒ x1 = x2 ∀ x1, x2 ∈ X.
A function f : X → Y is onto (or surjective) if given any y ∈ Y, ∃ x ∈ X such that f(x) = y.
A function f : X → Y is one-one and onto (or bijective), if f is both one-one and onto.
The composition of functions f : A → B and g : B → C is the function gof : A → C given by gof(x) = g(f(x)) ∀ x ∈ A.
A function f : X → Y is invertible if ∃ g : Y → X such that gof = IX and fog = IY.
A function f : X → Y is invertible if and only if f is one-one and onto.
Given a finite set X, a function f : X → X is one-one (respectively onto) if and only if f is onto (respectively one-one). This is the characteristic property of a finite set. This is not true for infinite set.
A binary operation ∗ on a set A is a function ∗ from A × A to A.
An element e ∈ X is the identity element for binary operation ∗ : X × X → X, if a ∗ e = a = e ∗ a ∀ a ∈ X.
An element a ∈ X is invertible for binary operation ∗ : X × X → X, if there exists b ∈ X such that a ∗ b = e = b ∗ a where, e is the identity for the binary operation ∗. The element b is called inverse of a and is denoted by a-1.
An operation ∗ on X is commutative if a ∗ b = b ∗ a ∀ a, b in X.
An operation ∗ on X is associative if (a ∗ b) ∗ c = a ∗ (b ∗ c)∀ a, b, c in X.