Relations and Functions

Relation:

A relation R from set X to a set Y is defined as a subset of the cartesian product X × Y. We can also write it as R ⊆ {(x, y) ∈ X × Y : xRy}.

Note: If n(A) = p and n(B) = q from set A to set B, then n(A × B) = pq and number of relations = 2^pq.

Types of Relation

Empty Relation:

A relation R in a set X, is called an empty relation, if no element of X is related to any element of X,
i.e. R = Φ ⊂ X × X

Universal Relation:

A relation R in a set X, is called universal relation, if each element of X is related to every element of X,
i.e. R = X × X

Reflexive Relation:

A relation R defined on a set A is said to be reflexive, if
(x, x) ∈ R, ∀ x ∈ A or
xRx, ∀ x ∈ R

Symmetric Relation:

A relation R defined on a set A is said to be symmetric, if
(x, y) ∈ R ⇒ (y, x) ∈ R, ∀ x, y ∈ A or
xRy ⇒ yRx, ∀ x, y ∈ R.

Transitive Relation:

A relation R defined on a set A is said to be transitive, if
(x, y) ∈ R and (y, z) ∈ R ⇒ (x, z) ∈ R, ∀ x, y, z ∈ A
or xRy, yRz ⇒ xRz, ∀ x, y,z ∈ R.

Equivalence Relation:

A relation R defined on a set A is said to be an equivalence relation if R is reflexive, symmetric and transitive.

Equivalence Classes:

Given an arbitrary equivalence relation R in an arbitrary set X, R divides X into mutually disjoint subsets A, called partitions or sub-divisions of X satisfying

· all elements of A_i are related to each other, for all i.

· no element of A_i is related to any element of A_j, i ≠ j

· A_i ∪ A_j = X and A_i ∩ A_j = 0, i ≠ j. The subsets A_i and A_j are called equivalence classes.

Function:

Let X and Y be two non-empty sets. A function or mapping f from X into Y written as f : X → Y is a rule by which each element x ∈ X is associated to a unique element y ∈ Y. Then, f is said to be a function from X to Y.
The elements of X are called the domain of f and the elements of Y are called the codomain of f. The image of the element of X is called the range of X which is a subset of Y.
Note: Every function is a relation but every relation is not a function.

Types of Functions

One-one Function or Injective Function:

A function f : X → Y is said to be a one-one function, if the images of distinct elements of x under f are distinct, i.e. f(x₁) = f(x₂ ) ⇔ x₁ = x₂, ∀ x₁, x₂ ∈ X
A function which is not one-one, is known as many-one function.

Onto Function or Surjective Function: A function f :

X → Y is said to be onto function or a surjective function, if every element of Y is image of some element of set X under f, i.e. for every y ∈ y, there exists an element X in x such that f(x) = y.
In other words, a function is called an onto function, if its range is equal to the codomain.

Bijective or One-one and Onto Function: A function f :

X → Y is said to be a bijective function if it is both one-one and onto.

Composition of Functions:

Let f : X → Y and g : Y → Z be two functions. Then, composition of functions f and g is a function from X to Z and is denoted by fog and given by (fog) (x) = f[g(x)], ∀ x ∈ X.
Note
(i) In general, fog(x) ≠ gof(x).
(ii) In general, gof is one-one implies that f is one-one and gof is onto implies that g is onto.
(iii) If f : X → Y, g : Y → Z and h : Z → S are functions, then ho(gof) = (hog)of.

Invertible Function:

A function f : X → Y is said to be invertible, if there exists a function g : Y → X such that gof = I_x and fog = I_y. The function g is called inverse of function f and is denoted by f^-1.
Note
(i) To prove a function invertible, one should prove that, it is both one-one or onto, i.e. bijective.
(ii) If f : X → V and g : Y → Z are two invertible functions, then gof is also invertible with (gof)^-1 = f^-1og^-1

Domain and Range of Some Useful Functions

Binary Operation:

A binary operation * on set X is a function * : X × X → X. It is denoted by a * b.

Commutative Binary Operation:

A binary operation * on set X is said to be commutative, if a * b = b * a, ∀ a, b ∈ X.

Associative Binary Operation:

A binary operation * on set X is said to be associative, if a * (b * c) = (a * b) * c, ∀ a, b, c ∈ X.
Note: For a binary operation, we can neglect the bracket in an associative property. But in the absence of associative property, we cannot neglect the bracket.

Identity Element:

An element e ∈ X is said to be the identity element of a binary operation * on set X, if a * e = e * a = a, ∀ a ∈ X. Identity element is unique.
Note: Zero is an identity for the addition operation on R and one is an identity for the multiplication operation on R.

Invertible Element or Inverse:

Let * : X × X → X be a binary operation and let e ∈ X be its identity element. An element a ∈ X is said to be invertible with respect to the operation *, if there exists an element b ∈ X such that a * b = b * a = e, ∀ b ∈ X. Element b is called inverse of element a and is denoted by a^-1.
Note: Inverse of an element, if it exists, is unique.

Operation Table:

When the number of elements in a set is small, then we can express a binary operation on the set through a table, called the operation table.