2 PETE L CLARK, Example 1 6 Let X Y Z Then divisibility is a relation between Z and Z. we say xRy if x y, Example 1 7 Let X Y Z Then having the same parity is a relation. between Z and Z, In many of the above examples we have X Y This will often but certainly not. always be the case and when it is we may speak of relations on X. 1 2 The formal definition of a relation, We still have not given a formal definition of a relation between sets X and Y In. fact the above way of thinking about relations is easily formalized as was suggested. in class by Adam Osborne namely we can think of a relation R as a function from. X Y to the two element set TRUE FALSE In other words for x y X Y. we say that xRy if and only if f x y TRUE, This is a great way of thinking about relations It has however one foundational. drawback it makes the definition of a relation depend on that of a function whereas. the standard practice for about one hundred years is the reverse we want to de. fine a function as a special kind of relation c f Example 5 above The familiar. correspondence between logic and set theory leads us to the official definition. Definition A relation R between two sets X and Y is simply a subset of the. Cartesian product X Y i e a collection of ordered pairs x y. Thus we have replaced the basic logical dichotomy TRUE FALSE with the basic. set theoretic dichotomy is a member of is not a member of Note that this new. definition has some geometric appeal we are essentially identifying a relation R. with its graph in the sense of precalculus mathematics. We take advantage of the definition to adjust the terminology rather than speaking. slightly awkwardly of relations from X to Y we will now speak of relations on. X Y When X Y we may but need not speak of relations on X. Example 1 8 Any curve in R2 defines a relation on R R E g the unit circle. is a relation in the plane it is just a set of ordered pairs. 1 3 Basic terminology and further examples, Let X Y be sets We consider the set of all relations on X Y and denote it. by R X Y According to our formal definition we have. R X Y 2X Y, i e the set of all subsets of the Cartesian product X Y. Example 1 9 a Suppose X Then X Y and R X Y 2, That is if X is empty then the set of ordered pairs x y for x X and y Y is. empty so there is only one relation the empty relation. b Suppose Y Again X Y and the discussion is the same as above. LECTURE NOTES ON RELATIONS AND FUNCTIONS 3, Example 1 10 a Suppose X consists of a single element Then X Y. y y Y in other words X Y is essentially just Y itself since the first. coordinate is always the same Thus a relation R on X Y corresponds to a subset. of Y formally the set of all y Y such that Ry, b Suppose Y consists of a single element The discussion is analogus to that. of part a and relations on X Y correspond to subsets of X. Example 1 11 Suppose X and Y are finite sets with X m and Y n. Then R X Y 2X Y is finite of cardinality,2X Y 2 X Y 2 X Y 2mn. The function 2mn grows rapidly with both m and n and the upshot is that if X and. Y are even moderately large finite sets the set of all relations on X Y is very. large For instance if X a b and Y 1 2 then there are 22 2 16 relations. on X Y It is probably a good exercise for you to write them all down However. if X a b c and Y 1 2 3 then there are 23 3 512 relations on X Y and. with apologies to the Jackson 5 it is less easy to write them all down. Exercise 1 1 Let X and Y be nonempty sets at least one of which is infinite. Show R X Y is infnite, Given two relations R1 and R2 between X and Y it makes sense to say that. R1 R2 this means that R1 is stricter than R2 or that R2 is more permis. sive than R1 This is a very natural idea for instance if X is the set of people. in the world R1 is the brotherhood relation i e x y R1 iff x and y are. brothers and R2 is the sibling relation i e x y R2 iff x and y are siblings. then R1 R2 if x and y are brothers then they are also siblings but not conversely. Among all elements of R X Y there is one relation R which is the strictest. of all namely R 1 that is for no x y X Y do we have x y R In. deed R R for any R R X Y At the other extreme there is a relation which. is the most permissive namely RX Y X Y itself that is for all x y X Y. we have x y RX Y And indeed R RX Y for any R R X Y. Example 1 12 Let X Y The equality relation R x x x X can be. thought of geometrically as the diagonal of X Y, The domain2 of a relation R X Y is the set of x X such that there exists. y Y with x y R In other words it is the set of all elements in x which relate. to at least one element of Y, Example 1 13 The circle relation x y R2 x2 y 2 1 has domain 1 1. Given a relation R X Y we can define the inverse relation R 1 Y X by. interchanging the order of the coordinates Formally we put. R 1 y x Y X x y R, Geometrically this corresponds to reflecting across the line y x. 1The notation here is just to emphasize that we are viewing as a relation on X Y. 2I don t like this terminology But it is used in the course text and it would be confusing to. 4 PETE L CLARK, Example 1 14 Consider the relation R R R attached to the function f x. R x x2 x R, The graph of this relation is an upward opening parabola it can also be described. by the equation y x2 The inverse relation R 1 is x2 x x R which. corresponds to the equation x y 2 and geometrically is a parabola opening right. ward Note that the domain of the original relation R is R whereas the domain of. R 1 is 0 Moreover R 1 is not a function since some values of x relate to. more than one y value e g 1 1 and 1 1 are both in R 1. Example 1 15 Consider the relation attached to the function f x x3 namely. R x x3 x R, This relation is described by the equation y x3 certainly it is a function and its. domain is R Consider the inverse relation,R 1 x3 x x R. which is described by the equation x y 3 Since every real number has a unique. real cube root this is equivalent to y x 3 Thus this time R 1 is again a function. and its domain is R, Later we will study functions in detail and one of our main goals will be to under. stand the difference between Examples 1 14 and 1 15. 1 4 Properties of relations, Let X be a set We now consider various properties that a relation R on X. i e R X X may or may not possess,Reflexivity For all x X x x R. In other words each element of X bears relation R to itself Another way to. say this is that the relation R contains the equality relation on X. Exercise 1 2 Which of the relations in Examples 1 1 through 1 15 are reflexive. Anti reflexivity For all x X x x 6 inR, Certainly no relation on X is both reflexive and anti reflexive except in the silly. case X when both properties hold vacuously However notice that a rela. tion need not be either reflexive or anti reflexive if there are x y X such that. x x R and y y,R then neither property holds,Symmetry For all x y X if x y R then y x R. Again this has a geometric interpretation in terms of symmetry across the diagonal. y x For instance the relation associated to the function y x1 is symmetric. since interchanging x and y changes nothing whereas the relation associated to the. function y x2 is not Looking ahead a bit a function y f x is symmetric iff. it coincides with its own inverse function, Exercise 1 3 Which of the relations in Examples 1 1 through 1 15 are symmetric. LECTURE NOTES ON RELATIONS AND FUNCTIONS 5, Example 1 16 Let V be a set A simple loopless undirected graph in. the sense of graph theory not graphs of functions is given by a relation E on V. which is irreflexive and symmetric Thus for x y V we say that x and y are. adjacent if x y E Moreover x is never adjacent to itself and the adjacency. of x and y is a property of the unordered pair x y if x is adjacent to y then y is. adjacent to x, Anti Symmetry for all x y X if x y R and y x R then x y. Exercise 1 4 Which of the relations in Examples 1 1 through 1 16 are anti. Transitivity for all x y z X if x y R and y z R then x z R. Being a parent of is not transitive but being an ancestor of is transitive. Exercise 1 5 Which of the relations in Examples 1 1 through 1 15 are transitive. Worked Exercise 1 6, Let R be a relation on X Show the following are equivalent. i R is both symmetric and anti symmetric,ii R is a subrelation of the equality relation. Solution Suppose that we have a relation R on X which is both symmetric and. anti symmetric Then for all x y R if x y R then by symmetry we have. also y x R and then by anti symmetry we have x y Thus we ve shown. that if i holds the only possible elements x y R are those of the form x x. which means that R is a subrelation of the equality relation Conversely if R is. a subrelation of equality and x y R then y x so y x R Similarly if. x y R and y x R then x y So R is both symmetric and anti symmetric. Now we makes two further defintions of relations with possess certain combinations. of these basic properties The first is the most important definition in this section. An equivalence relation on a set X is a relation on X which is reflexive sym. metric and transitive, A partial ordering on a set X is a relation on X which is reflexive anti symmetric. and transitive, Exercise 1 7 Which of the relations in Examples 1 1 through 1 16 are equivalence. relations Which are partial orderings, We often denote equivalence relations by a tilde x y and read x y as x. is equivalent to y For instance the relation having the same parity on Z is an. equivalence relation and x y means that x and y are both even or both odd. Thus it serves to group the elements of Z into subsets which share some common. property In this case all the even numbers are being grouped together and all. the odd numbers are being grouped together We will see shortly that this is a. characteristic property of equivalence relations every equivalence relation on a set. X determines a partition on X and conversely given any partition on X we can. define an equivalence relation, The concept of a partial ordering should be regarded as a generalized less than. 6 PETE L CLARK, or equal to relation Perhaps the best example is the containment relation on. the power set P S of a set S This is a very natural way of regarding one set as. bigger or smaller than another set Thus the insight here is that containment. satisfies many of the formal properties of the more familiar on numbers However. there is one property of on numbers that does not generalize to and hence. not to an arbitrary partial ordering namely given any two real numbers x y we. must have either x y or y x However for sets this does not need to be the case. unless S has at most one element For instance in the power set of the positive. integers we have A 1 and B 2 so neither is it true that A B or that. B A This is a much stronger property of a relation. Totality For all x y X either x y R or y x R, A total ordering or linear ordering on a set X is a partial ordering satis. fying dichotomy, Example 1 17 The relation on R is a total ordering. There is an entire branch of mathematics order theory devoted to the study. of partial orderings 3 In my opinion order theory gets short shrift in the standard. mathematics curriculum especially at the advanced undergraduate and graduate. levels most students learn only a few isolated results which they apply frequently. but with little context or insight Unfortunately we are not in a position to combat. this trend partial and total orderings will get short shrift here as well. 1 5 Partitions and Equivalence Relations, Let X be a set and let be an equivalence relation on X. For x X we define the equivalence class of x as, For example if is the relation having the same parity on Z then. 2 4 2 0 2 4,i e the set of all even integers Similarly. is the set of all odd integers But an equivalence class in general has many repre. sentatives For instance the equivalence class 4 is the set of all integers having. the same parity as 4 so is again the set of all even integers 4 2 More gen. erally for any even integer n we have n 0 and for any odd integer n we have. n 1 Thus in this case we have partitioned the integers into two subsets the. even integers and the odd integers, We claim that given any equivalence relation on a set X the set x x X. forms a partition of X Before we proceed to demonstrate this observe that we. are now strongly using our convention that there is no multiplicity associated to. membership in a set e g the sets 4 2 2 11 30 21 and 4 are equal The. 3For instance there is a journal called Order in which a paper of mine appears. LECTURE NOTES ON RELATIONS AND FUNCTIONS 7, above representation x x X is highly redundant for instance in the above. example we are writing down the set of even integers and the set of odd integers. infinitely many times but it only counts once in order to build the set of subsets. which gives the partition, With this disposed of the verification that P x x X gives a partition. of X comes down to recalling the definition of a partition and then following our. noses There are three properties to verify, i That every element of P is nonempty Indeed the element x is nonempty. because it contains x This is by reflexivity x x so x y X y x. ii That the union of all the elements of P is all of X But again the union is. indexed by the elements x of X and we just saw that x x so every x in X is. indeed in at least one element of P, iii Finally we must show that if x y 6 then x y i e any two elements. of P which have a common element must be the same element So suppose that. there exists z x y Writing this out we have z x and z y By symmetry. we have y z from this and z x we deduce by transitivity that y x i e. y x We claim that it follows from this that y x To see this take any. w y so that w y Since w x we conclude w x so w x Rerunning the. above argument with the roles of x and y interchanged we get also that y x. so x y This completes the verification, Note that the key fact underlying the proof was that any two equivalence classes. x and y are either disjoint or coincident Note also that we did indeed use all. three properties of an equivalence relation, Now we wish to go in the other direction Suppose X is a set and P Ui i I is a. partition of X here I is just an index set We can define an equivalence relation. on X as follows we say that x y if there exists i I such that x y Ui In other. words we are decreeing x and y to be equivalent exactly when they lie in the same. piece of the partition Let us verify that this is an equivalence relation First let. x X Then since P is a partition there exists some i I such that x Ui and. then x and x are both in Ui so x x Next suppose that x y this means that. there exists i I such that x and y are both in Ui but then sure enough y and x. are both in Ui and is commutative so y x Similarly if we have x y z such. that x y and y z then there exists i such that x and y are both in Ui and a. possibly different index j such that y and z are both in Uj But since y Ui Uj. we must have Ui Uj so that x and z are both in Ui Uj and x z. Moreover the processes of passing from an equivalence relation to a partition and. from a partition to an equivalence relation are mutually inverse if we start with. an equivalence relation R form the associated partition P R and then form the. associated equivalence relation P R then we get the equivalence relation R. that we started with and similarly in the other direction. 1 6 Examples of equivalence relations,8 PETE L CLARK. Example 1 18 Congruence modulo n Let n Z There is a natural partition. of Z into n parts which generalizes the partition into even and odd Namely we put. Y1 2n n 0 n 2n kn k Z,the set of all multiples of n. Y2 2n 1 n 1 1 n 1 2n 1 kn 1 k Z,and similarly for any 0 d n 1 we put. Yd 2n d n d d n d 2n d kn d kinZ, That is Yd is the set of all integers which upon division by n leave a remainder of. d Earlier we showed that the remainder upon division by n is a well defined integer. in the range 0 d n Here by well defined I mean that for 0 d1 6 d2 n. the sets Yd1 and Yd2 are disjoint Recall why this is true if not there exist k1 k2. such that k1 n d1 k2 n d2 so d1 d2 k2 k1 n so d1 d2 is a multiple of. n But n d1 d2 n so the only multiple of n it could possibly be is 0 i e. d1 d2 It is clear that each Yd is nonempty and that their union is all of Z so. d 0 gives a partition of Z, The corresponding equivalence relation is called congruence modulo n and writ. ten as follows, What this means is that x and y leave the same remainder upon division by n. Proposition 1 19 For integers x y the following are equivalent. i x y mod n, Proof Suppose that x y mod n Then they leave the same remainder say d. upon division by n there exist k1 k2 Z such that x k1 n d y k2 n d so. x y k1 k2 n and indeed n x y Conversely suppose that x k1 n d1. y k2 n d2 with d1 and d2 distinct integers both in the interval 0 n 1 Then. if n divides x y k1 k2 n d1 d2 then it also divides d1 d2 which as. above is impossible since n d1 d2 n, Example 1 20 Fibers of a function Let f X Y be a function We define a. relation R on X by x1 x2 R iff f x1 f x2 This is an equivalence relation. The equivalence class of x is called the fiber over f x. 1 7 Extra composition of relations, Suppose we have a relation R X Y and a relation S Y Z We can define a. composite relation S R X Z in a way which will generalize compositions. of functions Compared to composition of functions composition of relations is. much less well known although as with many abstract concepts once it is pointed. out to you you begin to see it in nature This section is certainly optional reading. The definition is simply this,S R x z X Z y Y such that x y R and y z S. In other words we say that x in the first set X relates to z in the third set Z if. there exists at least one intermediate element y in the second set such that x relates. LECTURE NOTES ON RELATIONS AND FUNCTIONS 9,to y and y relates to z. In particular we can always compose relations on a single set X As a special. case given a relation R we can compose it with itself say. R 2 R R x z X X y X such that xRy and yRz, Proposition 1 21 For a relation R on X the following are equivalent. i R is transitive, Exercise 1 8 Show that the composition of relations is associative. Exercise 1 9 Show S R 1 R 1 S 1, Exercise 1 10 Let X 1 N To a relation R on X we associate its. adjacency matrix M M R if i j R we put M i j 1 otherwise we. put M i j 0 Show that the adjacency matrix of the composite relation R2 is. the product matrix M R M R in the sense of linear algebra. 2 Functions, Let X and Y be sets A function f X Y is a special kind of relation between. X and Y Namely it is a relation R X Y satisfying the following condi. tion for all x X there exists exactly one y Y such that x y R Because. element of y attached to a given element x of X is unique we may denote it by f x. Geometrically a function is a relation which passes the vertical line test ev. ery vertical line x c intersects the graph of the function in exactly one point In. particular the domain of any function is all of X, Example 2 1 The equality relation x x x X on X is a function f x x. for all x We call this the identity function and denote it by 1X. Example 2 2 a Let Y be a set Then Y so there is a unique relation. on Y This relation is vacuously a function, b Let X be a set Then X so there is a unique relation on X with. domain If X then we get the empty function f If X 6 then. the domain is not all of X so we do not get a function. If f X Y is a function the second set Y is called the codomain of f Note the. asymmetry in the definition of a function although every element x of the domain. X is required to be associated to a unique element y of Y the same is not required. of elements y of the codomain there may be multiple elements x in X such that. f x y or there may be none at all, The image of f X Y is y Y such that y f x for some x X 4. In calculus one discusses functions with domain some subset of R and codomain R. Moreover in calculus a function is usually but not always given by some rela. tively simple algebraic analytic expression and the convention is that the domain. is the largest subset of R on which the given expression makes sense. 4Some people call this the range but also some people call the set Y what we called the. codomain the range so the term is ambiguous and perhaps best avoided. 10 PETE L CLARK,Example 2 3, a The function y 3x is a function from R to R Its range is all of R. b The function y x2 is a function from R to R Its range is 0. c The function y x,is a function from R to R Its range is all of R. d The function y x is a function from 0 to R Its range is 0. e The arctangent y arctan x is a function from R to R Its range is. 2 1 The set of all functions from X to Y, Let X and Y be sets We denote the set of all functions f X Y by Y X. Why such a strange notation The following simple and useful result gives the. motivation Recall that for n Z we put n 1 2 n and we also put. 0 Thus n n for all n N,Proposition 2 4 Let m n N Then we have. In words the set of all functions from 1 n to 1 m has cardinality mn. Proof To define a function f 1 n 1 m we must specify a sequence. of elements f 1 f n in 1 m There are m possible choices for f 1 also. m possible choices for f 2 and so forth up to m possible choices for f n and these. choices are independent Thus we have m m n times mn choices overall. 2 2 Injective functions, From the perspective of our course the most important material on functions are. the concepts injectivity surjectivity and bijectivity and the relation of these prop. erties with the existence of inverse functions, A function f X Y is injective if every element y of the codomain is asso. ciated to at most one element x X That is f is injective if for all x1 x2 X. f x1 f x2 implies x1 x2, Let us meditate a bit on the property of injectivity One way to think about it. is via a horizontal line test a function is injective if and only if each horizontal line. y c intersects the graph of f in at most one point Another way to think about. an injective function is as a function which entails no loss of information That is. for an injective function if your friend tells you x X and you tell me f x Y. then I can in principle figure out what x is because it is uniquely determined. Consider for instance the two functions f x x2 and f x x3 The first. function f x x2 is not injective if y is any positive real number then there are. two x values such that f x y x y and x y Or in other words if. f x x2 and I tell you that f x 1 then you are in doubt as to what x is it. could be either 1 or 1 On the other hand f x x3 is injective so if I tell you. that f x x3 1 then we can conclude that x 1, How can we verify in practice that a function is injective One way is to con. struct an inverse function which we will discuss further later But in the special. case when f R R is a continuous function the methods of calculus give useful. criteria for injectivity,LECTURE NOTES ON RELATIONS AND FUNCTIONS 11. Before stating the result let us first recall the definitions of increasing and de. creasing functions A function f R R is strictly increasing if for all. x1 x2 R x1 x2 f x1 f x2 Similarly f is strictly decreasing if. for all x1 x2 R x1 x2 f x1 f x2 Notice that a function which is. increasing or decreasing is injective The problem is that a function need not be. either increasing or decreasing although well behaved functions of the sort one. encounters in calculus have the property that their domain can be broken up into. intervals on which the function is either increasing or decreasing For instance the. function f x x2 is decreasing on 0 and increasing on 0. Theorem 2 5 Let f R R be a continuous function, a If f is injective then f is either increasing or decreasing. b If f is differentiable and either f 0 x 0 for all x R or f 0 x 0 for all. x R then f is injective, It is something of a sad reflection on our calculus curriculum that useful and basic. facts like this are not established in a standard calculus course However the full. details are somewhat intricate We sketch a proof below. Proof We prove part a by contraposition that is we assume that f is continuous. and neither increasing nor decreasing and we wish to show that it is not injective. Since f is not decreasing there exist x1 x2 such that f x1 f x2 Since f is. not increasing there exist x3 x4 such that f x3 f x4 If f x3 f x4 We. claim that it follows that there exist a b c such that either. Case 1 f b f a and f b f c or,Case 2 f b f a and f b f c. This follows from a somewhat tedious consideration of cases as to in which order the. four points x1 x2 x3 x4 occur which we omit here Now we apply the Intermediate. Value Theorem to f on the intervals a b and b c In Case 1 every number smaller. than f b but sufficiently close to it is assumed both on the interval a b and again. on the interval b c so f is not injective In Case 2 every number larger than f b. but sufficiently close to it is assumed both on the interval a b and again on b c. so again f is not injective, As for part b we again go by contraposition and assume that f is not injective. that is we suppose that there exist a b such that f a f b Applying the. Mean Value Theorem to f on a b we get that there exists c a c b such that. contradicting the assumption that f 0 x is always positive or always negative. Remark The proof shows that we could have replaced part b with the apparently. weaker hypothesis that for all x R f 0 x 6 0 However it can be shown that this. is equivalent to f 0 always being positive or always being negative a consequence of. the Intermediate Value Theorem For Derivatives, Example 2 6 a Let f R R by f x arctan x We claim f is injective. Indeed it is differentiable and its derivative is f 0 x 1 x. 2 0 for all x R, Therefore f is strictly increasing hence injective. b Let f R R by f x x3 x We claim f is injective Indeed it is. 12 PETE L CLARK, differentiable and its derivative is f 0 x 3x2 1 3x2 1 0 for all x R. Therefore f is strictly decreasing hence injective. Example 2 7 Let f R R be given by f x x3 One meets this function in. precalculus and calculus mathematics and one certainly expects it to be injective. Unfortunately the criterion of Theorem 2 5 falls a bit short here the derivative is. f 0 x 3x2 which is always non negative but is 0 at x 0. We will show by hand that f is indeed injective Namely let x1 x2 R and. suppose x31 x32 Then,0 x31 x32 x1 x2 x21 x1 x2 x22. Seeking a contradiction we suppose that x1 6 x2 Then x1 x2 6 0 so we can. divide through by it getting,0 x21 x1 x2 x22 x1 x2. Because each of the two terms in the sum is always non negative the only way the. sum can be zero is if,x1 2 x22 0, The second equality implies x2 0 and plugging this into the first inequality gives. x21 0 and thus x1 0 So x1 0 x2 contradiction, We gave a proof of the injectivity of f x 7 x3 to nail down the fact that Theorem. 2 5 gives a sufficient but not necessary criterion for a differentiable function to be. injective But we would really like to able to improve Theorem 2 5 so as to handle. this example via the methods of caclulus For instance let n be a positive integer. Then we equally well believe that the function f R R by f x x2n 1 should. be injective It is possible to show this using the above factorization method but. it is real work to do so The following criterion comes to the rescue to do this and. many other examples easily, Theorem 2 8 Let f R R be a differentiable function. a Suppose that f 0 x 0 for all x and that there is no a b such that f 0 x 0. for all x a b Then f is strictly increasing hence injective. b Suppose that f 0 x 0 for all x and that there is no a b such that f 0 x 0. for all x a b Then f is strictly decreasing hence injective. Proof We prove part a the proof of part b is identical Again we go by con. trapositive suppose that f is not strictly increasing so that there exists a b. such that f a f b If f a f b then applying the Mean Value Theorem we. get a c in between a and b such that f 0 c 0 contradiction So we may assume. that f a f b Then by exactly the same MVT argument f 0 x 0 for all x. implies that f is at least weakly increasing i e x1 x2 f x1 f x2 But. a weakly increasing function f with f a f b must be constant on the entire. interval a b hence f 0 x 0 for all x in a b contradicting the hypothesis. Worked Exercise 2 1 We will show that for any n Z the function f R R. given by x 7 x2n 1 is injective Indeed we have f 0 x 2n 1 x2n which is non. negative for all x R and is 0 only at x 0 So Theorem 2 8a applies to show. that f is strictly increasing hence injective,LECTURE NOTES ON RELATIONS AND FUNCTIONS 13. 2 3 Surjective functions A function f X Y if its image f X is equal to. the codomain Y More plainly for all y Y there is x X such that f x y. In many ways surjectivity is the dual property to injectivity For instance it. can also be verified by a horizontal line test a function f is surjective if and only. if each horizontal line y c intersects the graph of f in at least one point. Worked Exercise 2 2 Let m and b be real numbers Is f x mx b surjective. Solution It is surjective if and only if m 6 0 First if m 0 then f x b. is a constant function it maps all of R to the single point b and therefore is at the. opposite extreme from being surjective Conversely if m 6 0 write y mx b. and solve for x x y bm Note that this argument also shows that if m 6 0 f is. injective given an arbitary y we have solved for a unique value of x. By the intermediate value theorem if a continuous function f R R takes on. two values m M then it also takes on every value in between In particular if. a continuous function takes on arbitrarily large values and arbitrarily small values. then it is surjective, Theorem 2 9 Let a0 an R and suppose an 6 0 Let P R R by. P x an xn a1 x a0, Thus P is a polynomial of degree n Then P is surjective if and only if n is odd. Proof Suppose that n is odd Then if the leading term an is positive then. lim P x lim P x,whereas if the leading term an is negative then. lim P x lim P x, so either way P takes on arbitarily large and small values By the Intermediate. Value Theorem its range must be all of R, Now suppose n is even Then if an is positive we have. lim P x lim P x, It follows that there exists a non negative real number M such that if x M. P x 0 On the other hand since the restriction of P to M M is a continuous. function on a closed interval it is bounded below there exists a real number m. such that P x m for all x M M Therefore P x m for all x so it is not. surjective Similarly if an is negative we can show that P is bounded above so is. not surjective,2 4 Bijective functions, A function f X Y is bijective if it is both injective and surjective. Exercise 2 3 Show or any set X the identity function 1X X X by 1X x x. is bijective, Exercise 2 4 Determine which of the functions introduced so far in this section. are bijective,14 PETE L CLARK, A function is bijective iff for every y Y there exists a unique x X such that. The following result is easy but of the highest level of importance. Theorem 2 10 For a function f X Y the following are equivalent. i f is bijective, ii The inverse relation f 1 Y X f x x x X is itself a function. Proof Indeed we need f to be surjective so that the domain of f 1 is all of Y and. we need it to be injective so that each y in Y is associated to no more than one x. 2 5 Composition of functions, Probably the most important and general property of functions is that they can. under the right circumstances be composed 5 For instance in calculus complicated. are built up out of simple functions by plugging one function into another. e g x2 1 or esin x and the most important differentiation rule the Chain Rule. tells how to find the derivative of a composition of two functions in terms of the. derivatives of the original functions, Let f X Y and g Y Z that is the codomain of f is equal to the. domain of g Then we can define a new function g f X Z by. Remark Note that g f means first perform f and then perform g Thus function. composition proceeds from right to left counterintuitively at first There was a. time when this bothered mathematicians enough to suggest writing functions on. the right i e x f rather than f x But that time is past. Remark The condition for composition can be somewhat relaxed it is not neces. sary for the domain of g to equal the codomain of f What is precisely necessary. and sufficient is that for every x X f x lies in the domain of g i e. Range f Codomain g, Example The composition of functions is generally not commutative In fact if. g f is defined f g need not be defined at all For instance suppose f R R. is the function which takes every rational number to 1 and every irrational number. to 0 and g 0 1 a b is the function 0 7 b 1 7 a Then g f R a b is. defined it takes every rational number to a and every irrational number to b But. f g makes no sense at all, Remark Those who have taken linear algebra will notice the analogy with the. multiplication of matrices if A is an m n matrix and B is an n p matrix then. the product AB is defined an m p matrix But if m 6 p the product BA is not. defined In fact this is more than an analogy since an m n matrix A can be. viewed as a linear transformation LA Rn Rm Matrix multiplication is indeed. 5This is a special case of the composition of relations described in X X but since that was. optional material we proceed without assuming any knowledge of that material. LECTURE NOTES ON RELATIONS AND FUNCTIONS 15,a special case of composition of functions. Even when g f and f g are both defined e g when f g R R they need not. be equal This is again familiar from precalculus mathematics If f x x2 and. g x x 1 then,g f x x2 1 whereas f g x x 1 2 x2 2x 1. On the other hand function composition is always associative if f X Y. g Y Z and h Z W are functions then we have,h g f h g f. Indeed the proof is trivial since both sides map x X to h g f x 6. Exercise Let f X Y,a Show that f 1X f,b Show that 1Y f f. 2 6 Basic facts about injectivity surjectivity and composition. Here we establish a small number of very important facts about how injectivity. surjectivity and bijectivity behave with respect to function composition First. Theorem 2 11 Let f X Y and g Y Z be two functions,a If f and g are injective then so is g f. b If f and g are surjective then so is g f,c If f and g are bijective then so is g f. Proof a We must show that for all x1 x2 X if g f x1 g f x2 then. x1 x2 But put y1 f x1 and y2 f x2 Then g y1 g y2 Since g is. assumed to be injective this implies f x1 y1 y2 f x2 Since f is also. assumed to be injective this implies x1 x2, b We must show that for all z Z there exists at least one x in X such that. g f x z Since g Y Z is surjective there exists y Y such that g y z. Since f X Y is surjective there exists x X such that f x y Then. g f x g y z, c Finally if f and g are bijective then f and g are both injective so by part a. g f is injective Similarly f and g are both surjective so by part b g f is. surjective Thus g f is injective and surjective i e bijective qed. Now we wish to explore the other direction suppose we know that g f is injective. surjective or bijective What can we conclude about the factor functions f and g. The following example shows that we need to be careful. Example Let X Z 0 let Y R Define f X Y be f 0 or, your favorite real number it would not change the outcome and let f be the con. stant function which takes every real number y to 0 note that this is the unique. function from R to 0 We compute g f g f 0 g 0 Thus g f is the. identity function on X in particular it is bijective However both f and g are far. 6As above this provides a conceptual reason behind the associativity of matrix multiplication.

The Marantz Tradition The name Marantz is, if anything, more prominent today than when Saul B. Marantz founded the company in 1953. Even in those early days, perhaps no one - and no company - was as recognized for the passionate pursuit of high quality sound reproduction.

dss monthly management report / page 1 glossary. definition of categories of assistance and types of mo healthnet services . aids acquired immune deficiency syndrome

Algebra 1 Midterm Review Packet 5 1.8-Interpreting Graphs of Functions Pick the graph that best represents each situation: 1. A family is taking a car trip. The family travels at a constant rate of speed for 2 hours. The family stops for lunch and 1 hour later, continues the trip. They drive for half an hour before being pulled over by a cop ...

ALGEBRA 1 JANUARY 2014 Review for MIDTERM EXAM Livingston High School Page 2 3. Insert grouping symbols to produce the given values for each: (a) (b) CHAPTER 2 1. State all number systems that apply for each. Choose from the following: N for NATURAL, W for WHOLE, I for INTEGER, Ra for RATIONAL, Irr for IRATIONAL, and R for REAL.

Simulation of Dynamic 3D Crack Propagation within the Material Point ... of methods are available for using fracture ... methods for stress analysis of ...

timely manner may be excluded from the final book. There is no word count or length restriction for your chapter. The average chapter runs between 15 and 25 template pages including references, tables, and artwork. It is strongly recommended that the chapter template should be used when creating your chapter.

Isogeometric boundary element methods for three dimensional fatigue crack growth ... (XFEM) [8 ], usually coupled ... which is crucial to fracture analysis and the ...

are developed and utilized in XFEM analysis of linear-elastic fracture mechanics of ... (EFG). Crack simulation in ... Mergheim et al. [34]: simulation of cohesive ...