E-LESSON-2-3

IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.

B.C.A 2 All right are reserved with CU-IDOL Mathematics Course Code: BCA114 Semester: First SLM UNITS : e-Lesson No.: 2&3 2 www.cuidol.in Unit-2, 3 (BCA114)

Relation and Functions 33 OBJECTIVES INTRODUCTION Student will be able to : In this unit we are going to learn about the Define Relation and Function. Relation and function. Illustrate the representation and types of relation Under this unit you will also understand the and function. representation and types of relation and function. Describe the process of equivalence relation. This Unit will also make us to understand the Illustrate function in terms of composite. Equivalence relation and composite function. www.cuidol.in Unit-2, 3 (BCA114) INASllTITriUgThEt aOrFeDreISsTeArNveCdE AwNitDh OCNUL-IIDNOE LLEARNING

TOPICS TO BE COVERED 4 •Relation •Domain and Range of a Relation •Types of Relation •Equivalence Relation •Functions •Range and Domain of a Function •Types of Functions •Composition of Functions •Three Function Composition www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Relation 5 Definition •The relations such as less than, perpendicular to, not equal to, subset of, etc. are often used in mathematics and computer science problems concerning discrete objects. The relationships help establishing a relation between pair of objects taken in particular order. A relation between two sets can be defined by listing their elements as an ordered pair. •An ordered pair consists of two elements, say a and b in which one of them is designated as the first element and the other as the second element. An ordered pair is usually denoted by (a, b). Two ordered pairs (a, b) and (c, d) are said to be equal if and only if a = c and b = d. In other words, (a, b) = (c, d)  a = c and b = d www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Relation 6 •Thus, the ordered pair (2, 3) and (2, 3) are equal while ordered pair (2, 3) and (3, 2) are different. The reader must note the difference between the set {2, 3} and ordered pair (2, 3). We have {2, 3} = {3, 2} but (2, 3) ≠ (3, 2) Cartesian Product •If A and B are any two non-empty finite sets, then the set of all distinct ordered pairs whose first member (or coordinate) belongs to A and the second member (or coordinate) belongs to B is called the Cartesian product of A and B (in that order) and is denoted by A × B (read as A cross B). Symbolically, A × B = {(a, b) : a ϵ A, b ϵ B} www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Relation 7 •Example : If A = {1,2,3} and B = {2,3} , prove that A × B ≠ B × A. Also find, n(A × B). Solution: The product, A × B = {(1,2), (1,3),(2,2),(2,3),(3,2),(3,3)} B × A = {(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)} Since, elements of A × B and B × A are not the same, therefore A × B ≠ B × A. Now, n(A ×B) = n(A) × n(B) = 3 × 2 = 6 www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Domain and Range of a Relation 8 • If R is the relation from set A to another set B, then the set of elements in A that are related to some element or elements in B is called the domain of R and set B is called codomain of R. In other words, domain of R, a subset of A, is the set of all first elements in the ordered pairs which belong to R. Symbolically, D = {x : (x, y) ϵ R, x ϵ A for some y ϵ B} •The range, say E of the relation R, is the set of elements in B that appear as second element in the ordered pair which belong to R, i.e., all elements in B that are related to some element in A. Symbolically, E = {y : (x, y) ϵ R for some x ϵ A}. •Let A = {1,2,3,4} and B = {a, b, c}. Then every subset of A × B is a relation from A to B. So if R = {(2,a), (4,a), (4,c)}, then the domain of R is the set {2,4} and the range of R is the set {a, c}. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Types of Relation 9 •Inverse Relation Let R be any relation from a set A to a set B. The inverse relation, denoted by R–1, is a relation from B to A and is denoted by R-1 ={(y, x) : x ϵ A, y ϵ B, x, y ϵ R}. •In other words, the inverse relation is obtained by reversing each of the ordered pairs belong to R. Thus, (x, y) ϵ R (y, x) ϵ R-1 or xRy  yR-1x. •Evidently, range of R is domain of R–1 and vice versa. If A = B, then R and R–1 are both relations on A. Example: Let R be the set of relations on the set R of real numbers defined by x is less than y, where x, y ϵ R. Then R–1 is the relation defined by ‘x is greater than y, where x, y ϵ R’. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Types of Relation 10 •Identity Relation Let A be any set. Then the relation R in a set A denoted by I is said to be identity relation if I ={(x, y) : xϵA, y ϵ A, x = y}. In other words, the identity relation I in a set A is the set of all ordered pairs (x, y) of A × B for which x = y. The domain and range of I are both A. Example: Let A = {a, b, c, d}, then the identity relation A is I = {(a, a), (b, b), (c, c), (d, d)} •Universal Relation A relation in a set A is said to be universal relation provided R = A×A, In other words, universal-relation is the relation if each element of set A is related to every element of A. For example, if A = {2, 3}, then R = A×A = {(2, 2), (2, 3), (3, 2), (3, 3)} is a universal relation. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Types of Relation 11 •Void Relation A relation R in a set is said to be a void relation provided R is a null set, i.e., R = ϕ. For example, if A = {2, 3, 5} and the relation R is defined as: aRb if and only if a divides b, then R = ϕ and hence A × A is a void relation. •Reflexive Relation A relation R on a set A is reflexive if and only if each element in A is related to itself, i.e., aRa, for all a ϵ A. In other words, for all a ϵ A, (a, a) ϵ R. The necessary and sufficient conditions that a relation R on A be reflexive is that IA  R. A relation R on a set A is not reflexive, if there is at least one element, say b ϵ A such that b  R. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Types of Relation 12 •Symmetric Relation A relation R on a set A is said to be symmetric if and only if for all, a, b ϵ R aRb  bRa, i.e., (a, b) ϵ R  (b, a) ϵ R. The necessary and sufficient condition for relation R to be symmetric is R = R–1. •Example: Let A = {1, 2, 3} and R = {(1, 2), (2, 3), (2, 1), (3, 3)}. Then R–1 = {(2, 1), (3, 2), (1, 2), (3, 3)}. Since (2, 3) ϵ R but (2, 3)  R–1, therefore R ≠ R–1. Hence, R is not symmetric. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Types of Relation 13 •Anti-symmetric Relation Let R be a relation on a set A. Then R is anti-symmetric if and only if aRb and bRa  a = b, for a, b ϵ R, i.e., (a, b) ϵ R, (b, a) ϵ R  a = b. Thus, it is evident that a relation R on a set A is anti-symmetric if R  R–1  I, where I represents the identity relation on A. •Example: The relation in N defined by x divides y is anti-symmetric because x divides y and y divides x implies x = y. •Transitive Relations A relation R on a set A is transitive if and only if for all a, b, c ϵ R, aRb and bRc  aRc, i.e., (a, b), (b, c) ϵ R  (a, c) ϵ R. •The relation in N defined by x is less than y is transitive relation because x < y and y < z  x < z. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Equivalence Relation 14 • A relation R on a set A is called an equivalence relation (denoted by ~) if and only if following three conditions are true: 1. R is reflexive 2. R is symmetric 3. R is transitive Example 1: Give an example of an relation that is reflexive but neither symmetric nor transitive. Solution: Let A = {1, 2, 3} and R is defined as R = {(1, 1), (1, 2), (2, 3), (2, 2), (3, 3)}. Then R is reflexive since (a, a) ϵ R for all a ϵ A. It is not symmetric since (1, 2) ϵ R but (2, 1) ϵ R. It is also not transitive since (1, 2) ϵ R and (2, 3) ϵ R but (1, 3) ϵ R. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

FUNCTIONS 15 • Let A and B be any two non-empty sets, not necessarily distinct. If there exists a rule or correspondence, denoted by f, which relates (or associates) each element x ϵ A, to a unique (one and only one) element y ϵ B, then such a rule is called a function from A to B. •Symbolically, the function is expressed as: f: A → B such that y = f(x), for x ϵ A and y ϵ B However, a relation R from A to B may not relate an element of A to an element of B or more than one element of B may be related to an element of A. •In other words, the relation f can be described as the set of elements written as: {(x, f(x)): x ϵ A, f(x) ϵ B} www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Range and Domain of a Function 16 • The set A is called domain of the function f and B is called the co-domain of f. The element x ϵ A is called argument of function f and f(x) ϵ B is called the value of function for x and is also called the image or f-image of x under f. • Fig. 3.1 represents the functional relationship between two sets, set A and set B. Fig. 3.1 suggests that x may be considered as an input that is transformed by f into corresponding output f(x) = y. f(A) = {f(x): x ϵ A} = {y: y ϵ B, y = f(x) for same x ϵ A}. •The sets A and B are called the domain and co-domain of f respectively. Obviously, f(A)  B. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Types of Functions 17 • Equal Functions: Two functions f: A → B and g: A → B are said to be equal if and only if f(x) = g(x) for every x ϵ A and are written as f = g. •Constant Functions: A function f: A → B is called a constant function, if some element y ϵ B, is assigned to every element of A, i.e., f(x) = y for every x ϵ A. In other words, f: A → B is a constant function if range of f consists of only one element. •Examples: (a) f(x) = 4 • Onto and Into Functions The function f: A → B is said to be: Onto (or Subjective) Functions: If every element of B is f-image of at least one element in A. In this case, the range of f is equal to B, i.e., for all y ϵ B, y = f(x) for some x ϵ A or f(A) = B. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Types of Functions 18 Into Functions: If there is at least one element in B which is not the f-image of any element in A. But every element of A has f-image in B. In this case, the range of f is proper subset of B, i.e., f(A)  B and f(A) ≠ B. •Many-to-one and One-to-one Functions:  Many-to-one Functions: If two or more different elements in A have same f-image in B, i.e., f(x1) = f(x2) even when x1 ≠ x2, for all x1, x2 ϵ A.  One-to-one Functions (Injective Functions): If different elements in A have different f-image in B, i.e., x1 ≠ x2 implies f(x1) ≠ f(x2) for all x1, x2 A or equivalently f(x1) = f(x2)  x1 = x2 for all x1, x2 ϵ A. If f is one-to-one with A and B finite, then we must have |A| ≤ |B |. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Types of Functions 19 One-to-one Onto (Bijective) Functions: The function f: A → B is said to be one-to-one onto function if, to every element in A, there corresponds one and only one element of B and every element of B has one and only image in A. One-to-one onto functions are also called bijective. One-to-one and Into Function: The function f: A → B is said to be one-to-one into if, to each element in A, there corresponds one element of B, but there are some elements of B which do not correspond to any element in A. Many-to-one Into Function: The function f: A → B is said to be many-to-one onto function if each element of B is joined at least one element in A and two or more elements in A are joined to elements in B. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Types of Functions 20 Inverse Function: An inverse function or an anti-function is defined as a function, which can reverse into another function. In simple words, if any function f takes x to y then, the inverse of f, i.e., f–1 will take y to x. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Composition of Functions 21 •Let f: A → B and g: B → C be two functions. Then the composition of function f and g is denoted by (gof) is a function from A to C and is written as (gof): A → C such that (gof) (x) = g(f(x)) for each x ϵ A. •Obviously, domain of (gof) is set A and range of (gof) is set of C. •Composite Function is possible if the range of first function is a subset of the domain of second function. If this is not the case, composite function cannot be formed. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

Three Function Composition 22 •Let f: X → Y, g: Y → Z and h: Z → P be the given functions. •Let x ϵ X, y ϵ Y and z ϵ Z such that f(x) = y and g(y) = z, then we have [(hog)of](x) = (hog)[f(x)] = (hog)(y) = h[g(y)] = h(z) [(hog)of](x) = h(z) ....................(1) On the other hand, [ho(gof)](x) = h[(gof)x] = h[g(f(x))] = h(z) ………………...(2) From (1) and (2), we have [(hog)of](x) = [ho(gof)]x) x ϵX www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONS 1) The subset relation on a set of sets is ________. (c) (a) and (b) (d) None 23 (a) A partial ordering (b) An equivalence relation 2) Let R be a symmetric and transitive relation on set A, then ________. (a) R is reflexive and hence an equivalence relation (b) R is reflexive and hence a partial order (c) R is not reflexive and hence not an equivalence relation (d) None of the above 3) Let f(x) = x^2 + x and g(x) = x + 1, then f(x) + g(x) = ________. (a) x^2 + 1 (b) (x + 1)^2 (c) x + 1 (d) None 4) The domain D of f (x)= 1/x-2 real valued function is ________. (a) D – R{2} (b) D = {–5, 5} (c) D = {1} (d) None 5) A function is said to be ______________ if and only if f(a) = f(b) implies that a = b for all a and b in the domain of f. (a) One-to-many (b) One-to-one (c) Many-to-many (d) Many-to-one Answers: 1) (a) 2) (d) 3) (b) 4) (a) 5)(b) www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

SUMMARY 24 Let us recapitulate the important concepts discussed in this session: •If A and B are any two non-empty finite sets, then the set of all distinct ordered pairs whose first member (or coordinate) belongs to A and the second member (or coordinate) belongs to B is called the Cartesian product of A and B and is denoted by A × B. •A relation in a set A is said to be universal relation provided R = A×A, In other words, universal-relation is the relation if each element of set A is related to every element of A. • We defined types of relations like Inverse relation, Identity relation, Universal Relation, etc. •Let A and B be any two non-empty sets, not necessarily distinct. If there exists a rule or correspondence, denoted by f, which relates (or associates) each element xϵA, to a unique (one and only one) element y ϵ B, then such a rule is called a function from A to B. •An inverse function or an anti-function is defined as a function, which can reverse into another function. In simple words, if any function f takes x to y then, the inverse of f. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

FREQUENTLY ASKED QUESTION 25 Q:1 Define Relation. Explain the types of relation. Ans: A relation is a correspondence between two sets (called the domain and the range) such that to each element of the domain, there is assigned one or more elements of the range. For Further details please refer to the SLM Unit 2. Q2: Define Equivalence relation. The set of straight line in a plane the relation is defined as “ is parallel to” is an equivalence relation. Ans: A relation R on a set A is called an equivalence relation if and only if R is reflexive, symmetric and transitive. The set of straight line under the relation is parallel to is an equivalence relation. For Further details please refer to the SLM Unit 2. Q3. What is meant by Function? Find the difference between relation and function. Ans: A and B be any two non-empty sets, not necessarily distinct. If there exists a rule or correspondence, denoted by f, which relates (or associates) each element xϵA, to a unique (one and only one) element yϵ B, then such a rule is called a function from A to B. every function is relation but every relation need not a function. For Further details please refer to the SLM Unit 3. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

REFERENCES 26 CU-IDOL’s “Mathematics” SLM. Seymour Lipschutz, Marc Lars Lipson, “Discrete Mathematics”, Publisher: McGraw Hill Education (India) Private Limited.  J.K. Sharma, “Discrete Mathematics”, Publisher: MacMillan India Limited. K. Chandrasekhara Rao, “Discrete Mathematics”, Publisher: Narosa Publishing House. Dr. Abhilasha S. Magar, “Applied Mathematics – I”, Publisher: Himalaya Publishing House. Dr. Abhilasha S. Magar, “Business Mathematics”, Publisher: Himalaya Publishing House. Dr. Abhilasha S. Magar, “Quantitative Methods – II”. Publisher: Himalaya Publishing House. www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL

27 THANK YOU For queries Email: [email protected] www.cuidol.in Unit-2, 3 (BCA114) All right are reserved with CU-IDOL