MFCS UNIT 2 PDF

# Unit-2 ## Relations & Functions ### Relations * A collection of ordered pairs containing one object from each set, i.e; the relation shows the relationship between I/p's of O/p's. * Any set of ordered pairs in which the first member has some definite relationship to the second is called Relation. Let A & B be two non-empty sets. * Then AXB = {(a,b) | a∈A & b∈B} be a Cartesian product of A & B. A relation 'R' from A to B is a subset of AXB. * If R ≤ AXB & (a,b) ∈ R we say that a is related to b by R. * If a is not related to b by R we write aRb (a not related to b). * We can write a relation from set A to set B by R:A→B & read a relation R from A to B. Ex:- A = {1,2,3,4,5}, B={1,2,3,4,5} Write down the relation set R here R is less than if & only if A <B R: A→B [aRb <=> a<b] AXB = { (1,1) (1,2) (1,3) (1,4) (1,5) (2,1) (2,2) (2,3) (2,4) (2,5) (3,1) (3,2) (3,3) (3,4) (3,5) (4,1) (4,2) (4,3) (4,4) (4,5) (5.1) (5,2) (5,3) (5,4) (5,5)} R = { (1,2) (1.3) (1,4) (1.5) (2,3) (2,4) (2,5) (314) (3,5) (415)} ### Properties of Relations := 1. **Reflexive Property**: A relation R on set A is reflexive if (a,a)∈R + a∈A i.e.; a R a. Ex:- '≤' in the set of real numbers is reflexive but '<' is not reflexive. 2. **Symmetric Property**: A relation R on set A is symmetric if whenever, aRb then bRa. i.e, R is symmetric in A aRb => bRa (or) + (a,b)∈R ⇒ (b,a)∈R Ex- 1) The relation of similarities of triangles in the set of triangles in a plate. Ex:- 27 { (1,2) (1,2) (1,3) (1,4) 2 (211) (3.1) (411)} 3. **Anti-symmetric Property**: A relation R on set A is a symmetric of whenever aRb then bRa if (a,b) & R then (b,a)∈R Ex:- 1) '<' is a symmetric relation & also 1>' is a symmetric relation. 4. **Transitive Property**: A relation R on a set A is transitive whenever aRb, bRc Then aRc i.e; (a,b) (b,c)∈R ⇒ (a,c)∈R Ex: <, > relations in the set of real numbers. 5. **Irreflexive Property**: A relation R on a set A is irreflexive. If a∈A (a, a)∉R Ex: The Relations <,> are irreflexive in the set of real numbers. 6. **Anti Symmetric Property**: A relation R on a set A is Anti symmetric if aRb ∈ R ⇒ bRa ∈ R then a = b Ex: 1) Division is anti symmetric in set of real numbers. aRb, bRa then a = b ### Domain & Range of a Relation:- * Let R be a relation from a to b then the domain of R is set to be D(R) of elements A which are related to some elements in B. In other words, D(R) subset of A is the set of all elements in the ordered pairs. ### Range:- The range of a relation R denoted by R(r) be the set of in elements in B which are and elements of ordered pairs in R which are related to some retements in A D(R) = {a | such (a,b) ER, a∈A} R(R) = {b | (a,b) ER , b∈B} Ex:- Consider the relation 's' defined as a set of ordered pairs as s = {(a,13), (b, 4), (Rama,sita), (Radha, krishna)} D(s) = {(a,b), Rama, Radha} R(S) = { 3, 4, Sita, krishna}. ### Binary relation on set! A Binary Relation on the set A is a relation from A to A * In other words a relation on a set A is a subset of AXA. Ex:- D A = {a,b,c} R =∈ AXA R = { (a,a), (a,b) (a, c)} a binary relation of A 2) A = {1,2,3,4} R = {(a,b) / a < b} {(1,2), (1,1), (1,3),(1,4),(2,2),(2,4), (3,3) C (414)} ### A binary relation R from a set A to a set B is a subset of AXB. RCAXB * We can represent relations graphically or a using table. Ex: Let A = {0,1,2} B = {a,b} R = {Co,a), Co,b), (1,a), (2,b)} is a relation from A to B <img src="https://i.imgur.com/6x65a8l.png" alt="Table with heading R and two columns with labels 'a' and 'b' and rows 0,1,2. The first row has an 'x' in both columns, the second row has an 'x' in the column labelled 'a' and the third row has an 'x' in the column labelled 'b'."/> ### Equivalent Relation:- * A relation R on a set A is called an Equivalence relation if it is * (i) reflexive * (ii) Symmetric * (iii) Transitive. Ex- A1 = {1,2,3,4,5,6,7} R = {(a,b) a mod 2 = b modz } Ans:- R = S (1,3), (2,4), (3,5), (1,5), (1,7),(2,6), (4,6), { (3,7), (3,1), (4,2), (5,3), (5,1) (7,1), (5,7) (E) CC (6,2), (5,4), (713), (715) (1,1) (2,2), (3,3) (4,4) (5,5) (616) (7.7)} * Here it satisfies, reflexive, symmetric and Transitive * It is an Equivalent Relation. ### Modulo Operation :- Abbreviated "mod" or ""%" * in many programming languages is the remainder when dividing. Ex:- 5 mod 3 = 2 ### Equivalence Class:- * Let's be an Equivalence Relation on a set' A'. * The set [a]s (a subset of A) is defined by [a]s = {blb∈A and (a,b) Es} is called 's' Equivalence class generated by a∈ A. i.e; * Every equivalence relation on a set generates a unique partition of the set. The blocks of this partition are nothing but the 's' equivalence class. Ex:- A Let A = {a,b,c} then R = {(a,a), (bib). (c,c) (a,b) (b,a)} The equivalence Classes are [a] = {a,b} [b] = {a,b} [c] = {c} {[a], [b], [c]} forms a partition for A = {a,b,c} * Let A = {0,1,2,3,4}. S. T the relation R as R = {(0,0), (0,4), (1,1) (1,3),(2,2), (3,1) (3,3) (410) (4,4)} is an Equivalence Relation. Find the distinct Equivalent classes of R ### Proof:- Given, * A = {0,1,2,3,4} and R Now, we have to prove reflexive, symmetric & transitive properties 1. **(i)** + 0,1,2,3,4 ∈A J(0,0), (1,1),(2,2), (3,3) (4.4) ∈R * reflexive properties satisfied [∀ac∈A] (a, a)∈R] 2. **(ii)** for (0,4) there existed (410) for (1.3) there existed (311) * Symmetric property satisfied (∀ (a,b) ∈ R ⇒ (b,a) ∈ R) 3. **(iii)** for, (0,0), (0,4) ∈ R then (0,4) ∈ R *(0,0) (0,4)→(0,4)* *(0,4) ) (4,0)→(0,0)* *(1,1) (1,3)→(1,3)* *(1,3) (3,1)→(1,1)* *(1,3) (3,3) → (1,3).* *(4.0) (014)→(414)* *(3.3) (3.1) (113) → (3.3). * *Transitive property satisfied* *[∀ (a,b), (b, c)∈R then (a, c)∈R]* Hence R is an equivalence relation [0]R = {014} = [4]R [1]R= {1,3} = [3]R [2] = {2} ### (Binary Relation of/sctix) * Prove that R = {(x,y) ∈ zxz | x - y is divisible by 3} is an equivalence relation? Sol:- An equivalence is binary relation which is * → reflexive * → Symmetric * → transitive * i-e; R = {(x,y)∈zxz/(x-y) mod 3 = 0}.. * We need to prove R is an equivalence relation by proving it as (i) reflective (ii) Symmetric (iii) transitive. * **(i)** Reflexive - * let 5 ∈ z * -7∈z * let (x-x) mod 3 * (5-5) mod 3=0 mod 3 = 0. * Similarly (-7-(-7)) mod 3 = (-7+7) mod 3= * omod 3=0. * : ∀aez J (a,a) ∈ z*z (since 5 ∈Z, (5,5)∈ zxz, ' - 7∈z then (-7,7)∈ zxz) * That is R is reflexive. * **(ii)** Symmetrix- * Let 8,14 ∈ z * (x-y) mod3 = (8-14) mod 3 = - 6mod 3 * =0 * Similarly 11,14 * (x-y) mod 3 = (11-14) mod3 = - 3 mod 3 = 0 * (y-x) mod 3 = (14-11) mod 3 = 3mod 3= 0 * (x,y) ∈ zxz ⇒ (y,x)∈ zxz * :: ∀ (x,y)∈ zxz , R is symmetric * **(iii)** transitive:- * * x y z * 5 11 17 * (x-y) mod 3 = (5-11) mod 3 = - 6 mod 3 = 0 * (y-z) mod 3 = (11-17) mod 3 = - 6 mod 3 = 0 * (x-z) mod 3 = (5-17) mod 3 = - 12 mod 3 = 0 * ∴ (x,y), (y,z) ∈ zxz * Then 7 (x,z) ∈ zxz * .. R is transitive. * From (i), (ii) (iii) R is an equivalence relation. ### * Partical Order Relation * A relation R on a set A is called partial order Relation if R is reflexive, Anksymmetric & transitive. * The sets with a partial order R is called a partial ordered set poset & it denoted by {A,R} * In general a partial order on a set is denoted by <, ≥ or > or ≤. * Eg: Let A = 2⁺ the set all positive integers then ≤ or ≥ or < or > is partial order relation. Ex 2:- Let X be a power of A then define R on X as S₁.R S2 if and only if S₁.C S2 for S₁, S₂ ∈ X. Then the relation inclusion ≤ is a Partial order Relation * **Power set:** Power set is the set of elements which are all subset of a given set. P(A) = 2^n n is no. of element in A ### Total Order Relation:- * A partial order relation defined on aset is said to be a Total Order Relation . Ifhe order provides a method of comparision btw any two elements in the set. Hence in addition to being a partial order, a total order also has the property that ∀ x, y ∈ S either x Ry or yRx holds. * Hence a total orders gives us a way to compare and rank all elements of the set. * Consider two real no.'s x and y if * if x-y ≤ 0, then x ≤ y * if y-x ≤ 0, then y ≤ x * **Partial Order Vs Total Order relations** * Every total order relation is a partial order relation but converse is not always true. Ex:- S={1,2,3} power set. ps = {.{1}, {2}{3}, {1, 2}, {1,3},{2,3}, {1,2,3}} * **①** x = {1,2,3 } and relation R = {(1,1),(2,2), (3,3), (1,2), (1, 3)}. Is R a total order relation? Soli- For total order relation, we need to check 4 properties: * (i) reflexive * (ii) Anti-Symmetric * (ii) Transitive * (iv) Compatability. 1. **(i) Reflexive:-** * We have 1,2,3 ∈ X and (1,1), (2,2), (3,3) ∈R * ∴∴ R is reflexive. 2. **(ii) Anti-symmetric:-** * We have (1,1), (2,2), (3,3) ∈ R * But (2,1) (311) ∉ R for (1,2) (1.3) ∈ R * i-e; if (a,b), (b,a) ∈ R then a=b * .. R is Anti-symmetric. 3. **(iii) Transitive:-** * (1,1) (1,2)⇒ (1,2) * (1, 1) (1,3) => (1,3) * (1,3) (3,3) => (1,3). * (1,2) (2,2) => (1,2) * ∴∴ R is Transitive. 4. **(iv) Comparability:-** * for 1,2 ∈ X ⇒ (1,2) ∈ R * for 1,3 ∈ X ⇒ (1,3) ∈ R * for 2,3 ∈ X ⇒ (2,3) ∉ R & (3,2) ∉ R. * :: R is not comparable relation. * .. It is not a Total Order Relation. ### Image Set * The image of the set is all about values it may produce of the elements of the set. The set of images of the elements of the set under a function f is called the image of the set s under f and is denoted by f(s) i.e; f(s) = { f(a) | a∈s } where s is a subset of the domain A of f. The image of the domain f is called the Range of f. ### Pre-Image:- * A Group of elements of the input set which are passed to a function to obtain some elements of the output set. ### Function:- * A function is a relation which describes that there should be only one output for each input. i.e; every x value should be associated with only one y value is called a function. Exp *(i)* <img src="https://i.imgur.com/mB8e4rT.png" alt = "A diagram with four circles that are numbered 1, 2, 3, and 4, and connected via arrows to three circles labelled 'a', 'b', and 'c'. Circle 1 is connected by arrow to 'a', circle 2 is connected to 'b', circle 3 is connected by double arrows to 'a', circle 4 is connected to 'b'." /> * Not a function. *(ii)* <img src="https://i.imgur.com/6E431lU.png" alt = "A diagram with four circles that are numbered 1, 2, 3, and 4, and connected via arrows to three circles labelled 'a', 'b', and 'c'. Circle 1 is connected by arrow to 'a', circle 2 is connected to 'b', circle 3 is connected by double arrows to 'c', circle 4 is connected to 'c'." /> * a Function *(iii)* <img src="https://i.imgur.com/h2s3G4R.png" alt = "A diagram with four circles that are numbered 1, 2, 3, and 4, and connected via arrows to three circles labelled 'a', 'b', and 'c'. Circle 1 is connected by arrow to 'a', circle 2 is connected by arrows to 'b' and 'c', circle 3 is connected by arrow to 'b', circle 4 is connected to 'c'." /> * Not a function. *(iv)* <img src="https://i.imgur.com/y2K5H6z.png" alt = "A diagram with four circles that are numbered 1, 2, 3, and 4, and connected via arrows to three circles labelled 'a', 'b', and 'c'. Circle 1 is connected by arrow to 'a', circle 2 is connected to 'b', circle 3 is connected by double arrows to 'c', circle 4 is connected to 'c'." /> * a function *(v)* <img src="https://i.imgur.com/93YpKgU.png" alt = "A diagram with four circles that are numbered 1, 2, 3, and 4, and connected via arrows to three circles labelled 'a', 'b', and 'c'. Circle 1 is connected by double arrow to 'a', circle 2 is connected by arrow to 'b', circle 3 is connected by arrows to 'a' and 'b', circle 4 is connected to 'c'." /> * a function. *(vi)* <img src="https://i.imgur.com/c1o2L4S.png" alt = "A diagram with four circles that are numbered 1, 2, 3, and 4, and connected via arrows to three circles labelled 'a', 'b', and 'c'. Circle 1 is connected by double arrow to 'a', circle 2 is connected by arrow to 'a', circle 3 is connected by arrow to 'c', circle 4 is connected by arrow to 'c'." /> * Not a function. ### If f from A→B is a function, then A is called Domain and the elements in B which are mapped in the elements of A are called as Co-domain. * Codomain is subset of range. <img src="https://i.imgur.com/0sA1M7W.png" alt = "A diagram with four circles that are numbered 1, 2, 3, and 4, and connected via arrows to four circles labelled 'a', 'b', 'c', and 'd. Circle 1 is connected by arrow to 'a', circle 2 is connected to 'b', circle 3 is connected by arrow to 'c', circle 4 is connected to 'd'." /> ### Types of functions:- 1. **Onto function (surjective function)**: A function f from A to B f: A B is said to be an Onto function, if every element of B has a pre-image in A under f. * That is Range = Co-domain. * f(A) = B Ex: <img src="https://i.imgur.com/X52RjY0.png" alt = "Two diagrams each with four circles numbered 1,2,3, and 4, and connected via arrows to three circles labelled 'a', 'b', and 'c'. In the first diagram, circle 1 is connected by arrow to 'a', circle 2 is connected to 'b', circle 3 is connected to 'c', circle 4 is connected to 'c'. In the second diagram, circle 1 is connected to 'b', circle 2 is connected by double arrows to 'a', circle 3 is connected to 'c', circle 4 is connected to 'c'. " /> * onto <img src="https://i.imgur.com/y1yVkCw.png" alt = "A diagram with four circles that are numbered 1, 2, and 3, and connected via arrows to three circles labelled 'a', 'b', and 'c'. Circle 1 is connected to 'a', circle 2 is connected to 'b', circle 3 is connected to 'c'." /> * its a function but not an onto function. 2. **One-one (Injective function)**: * A function -f : A→B is said to be one - one function, if diff clements of A have different images in B. That is, if a1, a2∈A with a1 ≠ a2 then f(a1)≠f(a2) * ⇒ If a1, a2∈ A with a₁ = a2 then f (a1) = f(a2) <img src="https://i.imgur.com/r2jHqWZ.png" alt = "Two diagrams each with four circles numbered 1,2, and 3, and connected via arrows to four circles labelled 'a', 'b', 'c', and 'd'. In the first diagram, circle 1 is connected by arrow to 'a', circle 2 is connected to 'b', circle 3 is connected to 'c'. In the second diagram, circle 1 is connected to 'a', circle 2 is connected to 'a', circle 3 is connected to 'b', circle 4 is connected to 'c'." /> * one-one <img src="https://i.imgur.com/z11T2rD.png" alt = "Two diagrams each with four circles numbered 1,2, and 3, and connected via arrows to four circles labelled 'a', 'b', 'c', and 'd'. In the first diagram, circle 1 is connected by arrow to 'a', circle 2 is connected to 'b', circle 3 is connected to 'c'. In the second diagram, circle 1 is connected to 'a', circle 2 is connected to 'b', circle 3 is connected to 'c', circle 4 is connected to 'c'." /> * not a one-one function 3. **Bijective function:-** A function f:A→B is said to be a Bijective function if it is an onto function as well as a one-one function ① The function f:RR and g:RR are defined by f(x) = 3x + 7 + x∈R and g(x) = x(x³-1) + x∈R to the verify that f is one-one and g is not. Sol:- * Let x1, x2∈R * Assume f(x1) = f(x2). * f(x1) = 3x1+7. * f(x2) = 3x2+7 * if f(x1) = f(x2) * 3x1+7 = 3x2+7 * x1 = x2. * i-e; If f(a1) = f(a2) then a1=a2 * .. f is one-one * Assume g(x1) = g(x2). * g(x1) = x1(x1³-1) * g(x2) = x2(x2³-1) * If g(x1) = g(x2). * x1(x1-1)=x2(x2³-1) * here clearly x1 = x2. * let x1=0, x2 = 1 * g(0) = 0(0³-1)=0 * g(1) = 1(1³-1) = 1(0) = 0 * But we got * g(0) = g(1) for 0 ≠ 1. * g is not a one-one function * from ① & 2. f is oneone and g is not * ⊕ Let f : ℤ → ℤ be defined by f(a) = a +1 for a∈ℤ. Find whether f is one-one or onto or both or neither. Sol:- * Let Given * f(a) = a + 1 * one-one * Let a1, a2 ∈ ℤ. * assume f(a1) = f(a2). * a1+1 = a2+1 * a1=a2 * :: if f(x1) = f(x2) then x1 = x2 * i.e; f is one-one function * onto * let b, b-1 ∈ ℤ * f(b-1) = (b-1)+1 * = b ∈ ℤ , * 9.e; ∀ b ∈ ℤ ∃ b∈ℤ b-1∈ℤ. * Such that f(a) = a + 1 * ⇒ every element in B has a preimage in A. * .. f is an onto * .. f is a bijective function. ### Special function:- 1. **Identity function:-** * Identity function A function f : A→ A such that f(a) = f(a) ∀ a ∈ A. is called the Identity function on a set A * That is a function f on a set A is an Identity function if the image of every element of A is itself f(A) = A <img src="https://i.imgur.com/zO4M3pE.png" alt = "A diagram with three circles numbered 1, 2, and 3, and connected via arrows to three circles labelled 'a', 'b', and 'c'. Circle 1 is connected by arrow to 'a', circle 2 is connected to 'b', circle 3 is connected to 'c'." /> 2. **Constant function:-** * A function f : A→B such thatf (a) = c for every a ∈ A where C is a fixed element of B is called Constant function <img src="https://i.imgur.com/7WRYZ8n.png" alt = "A diagram with three circles numbered 1, 2, and 3, and connected via arrows to three circles labelled 'a', 'b', and 'c'. Circle 1 is connected by arrow to 'a', circle 2 is connected to 'b', circle 3 is connected to 'c'." /> * In other words, a function f : A→B. iS a constant function if all elements of A have tu same Image in B. * f(A) = {c}. 3. **Linear Function:-** * A linear function is a function which forms a straight line on a graph. It is generally a polynomial function whose degree is atmost 1. * y = f(x) = px+q. 4. **Absolute value function:-** * An Absolute value function is a function that contains an Algebraic expression within absolute sys value symbols. * Ex: The Absolute value of a number is its distance from 0 on the number line. <img src="https://i.imgur.com/XvC363X.png" alt = "A diagram with circles labelled 0, 1, 2, 3, and 4. The circles labelled 0.8624, 1.23, 1.58, and 3.4 are connected via arrows to the circles labelled 0, 1, 2, 3, and 4 respectively." /> 5. **Flooring and ceiling functions :-** * A function σ: ℤ→ℤ + such that σ(x) = x+1 is called the Peano's successor function. Here σ(1) = 2, σ(2) = 3, σ(n) = n+1. * The range of σ is the set {2,3,4---} * For any real number x, we define the floor of x as * [x] = the greatest integer less than or equal to e * = max { n / n ≤ x, n is an integer} * = min [max] * = 2 * For any real number x, we define the ceiling of x as * [x] = the least integer greater than or equal to x * = min { n / n ≥ x, n is an integer}. Example:- x= 4.5 * [4.5] = 4 (flooring] * ⌈4.5⌉ = 5 [ceiling] * ① The function f : (ℤ×ℤ)→ ℤ is defined by f(x,y) = 2x+3y verify that f is onto but not one-one. Sol:- Given, * f(x,y) = 2x + 3y * Weneed to prove f as onto but not one-one * **To prove f is an onto :-** * Let n∈ℤ. * we can write * n = 4n-3n. * = 2(2n) + 3(-n) * Consider x = 2n, y=-n. * = f (2n,-n) * : ∀ n∈ℤ J f(2n,-n)∈ℤ×ℤ as a primary pre-image * ∴∴ f is an onto. * **To prove f is not one-one-** * Let two element in a set ℤ×ℤ (0,2) & (3,0) and also (0,4) (6,0) * f (0,2) = (2×0)+(3x2) = 0+6=6 * f(310) = (2×3)+(3x0) = 6+0=6 * f(014) = (2x0) + (3x4)=0+12=12 * f(6,0) = (2x6) + (3x0) = 12+0=12. * ∴∴ f (0,2) = f (3.0) but (0,2) ≠ (310) * :: Jf(a1) = f (a2) but a1 ≠ a2 * **Example problem on Equivalence Relation** ① Show that the relation R is an Equivalence relation A = {1,2,3,4,5}. Given by the relation R = {(a,b): |a-b| is Even} sol.- Given, A = {1,2,3,4,5}. R = {(a,b): |a-b| is Even} where a,b ∈ A. * We need to prove R is Equivalence relation. So we need to prove three properties. * 1. Reflexive * 2. symmetric * 3. Transitive * **To prove reflexive** * A = {1,2,3,4,5}. * R = {(1,3),(3,1), (2,4) (412), (3,5), (513) (115), (5,1), (111) (2,2) (3,3), (4,4) (515)} * ∀a∈A (a,a)∈R * .. R is Reflexive. * **To prove Symmetric** * for (1,3) ∈ R ⇒ (3,1) ∈ R. * for (214) ∈ R ⇒ (412) ∈ R * for (3,5) ∈ R ⇒ (5,3) ∈ R. * for (1,5) ∈ R ⇒(5,1)∈R. * i.e (a,b)∈R ⇒ (b,a) ∈ R * .. R is symmetric. * **To prove Transitive:** * (1,3) (3,1) = (1,1) * (2,4) (4,2) => (2,2) * (3,5) (5,3)=>(3,3) * (1,5) (5,1) => (1, 1) * (1,1) (1,3)= (1,3) * (2,2) (2,4)=>(2,4) * (3,3) (3,1)=>(3,1) * (4

Document Details

Tags

Related

Summary

Full Transcript