Introduction Functions Slides by Christopher M Bourke Instructor Berthe Y Choueiry You ve already encountered functions throughout your education f x y x y f x x f x sin x Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics Here however we will study functions on discrete domains and ranges Moreover we generalize functions to mappings Thus there may not always be a nice way of writing functions like above Section 2 3 of Rosen cse235 cse unl edu Definition Definitions Function Terminology Definition A function f from a set A to a set B is an assignment of exactly one element of B to each element of A We write f a b if b is the unique element of B assigned by the function f to the element a A If f is a function from A to B we write f A B This can be read as f maps A to B Note the subtlety I Each and every element in A has a single mapping I Each element in B may be mapped to by several elements in A or not at all Definition Let f A B and let f a b Then we use the following terminology I A is the domain of f denoted dom f I B is the codomain of f I b is the image of a I a is the preimage antecedent of b I The range of f is the set of all images of elements of A denoted rng f Definitions Definition I Visualization More Definitions Preimage Range Image f a b f a b A B Domain Codomain A function f A B Definition Let f1 and f2 be functions from a set A to R Then f1 f2 and f1 f2 are also functions from A to R defined by f1 f2 x f1 x f2 x f1 f2 x f1 x f2 x Example Definition II Definition III More Definitions More Definitions Let f1 x x4 2x2 1 and f2 x 2 f1 f2 x f1 f2 x x2 then x4 2x2 1 2 x2 x4 x2 3 x4 2x2 1 2 x2 x6 3x2 2 Definition Let f A B and let S A The image of S is the subset of B that consists of all the images of the elements of S We denote the image of S by f S so that Note that here an image is a set rather than an element Example Let I A a1 a2 a3 a4 a5 I B b1 b2 b3 b4 I f a1 b2 a2 b3 a3 b3 a4 b1 a5 b4 I S a1 a3 Draw a diagram for f The image of S is f S b2 b3 f S f s s S Definition Definition IV Injections Surjections Bijections I More Definitions Definitions Definition A function f is said to be one to one or injective if A function f whose domain and codomain are subsets of the set of real numbers is called strictly increasing if f x f y whenever x y and x and y are in the domain of f A function f is called strictly decreasing if f x f y whenever x y and x and y are in the domain of f f x f y x y for all x and y in the domain of f A function is an injection if it is one to one Intuitively an injection simply means that each element in B has at most one preimage antecedent It may be useful to think of the contrapositive of this definition x 6 y f x 6 f y Injections Surjections Bijections II Injections Surjections Bijections III Definitions Definitions Definition A function f A B is called onto or surjective if for every element b B there is an element a A with f a b A function is called a surjection if it is onto Again intuitively a surjection means that every element in the codomain is mapped This implies that the range is the same as the codomain Definition A function f is a one to one correspondence or a bijection if it is both one to one and onto One to one correspondences are important because they endow a function with an inverse They also allow us to have a concept of cardinality for infinite sets Let s take a look at a few general examples to get the feel for these definitions Function Examples Function Examples A Non function A Function Neither One To One Nor Onto A A B B a1 b1 a1 b1 a2 b2 a2 b2 b3 a3 b3 b4 a4 b4 a3 a4 This is not a function Both a1 and a2 map to more than one element in B This function not one to one since a1 and a3 both map to b1 It is not onto either since b4 is not mapped to by any element in A Function Examples Function Examples One To One Not Onto Onto Not One To One A B A B a1 b1 a1 b1 a2 b2 a2 b2 a3 b3 a3 b3 b4 a4 This function is one to one since every ai A maps to a unique element in B However it is not onto since b4 is not mapped to by any element in A This function is onto since every element bi B is mapped to by some element in A However it is not one to one since b3 is mapped to more than one element in A Function Examples Exercises I A Bijection Exercise I A B Example Let f Z Z be defined by a1 b1 a2 b2 a3 b3 What is the domain and range of f Is it onto One to one a4 b4 Clearly dom f Z To see what the range is note that This function is a bijection because it is both one to one and onto every element in A maps to a unique element in B and every element in B is mapped by some element in A f x 2x 3 b rng f b 2a 3 a Z b 2 a 2 1 b is odd Exercises II Exercises Exercise I Exercise II Therefore the range is the set of all odd integers Since the range and codomain are different i e rng f 6 Z we can also conclude that f is not onto Example Let f be as before f x 2x 3 However f is one to one To prove this note that f x1 f x2 2x1 3 2x2 3 x1 x2 but now define f N N What is the domain and range of f Is it onto One to one By changing the domain codomain in this example f is not even a function anymore Consider f 1 2 1 3 1 6 N follows from simple algebra Exercises I Exercises II Exercise III Exercise III Example Define f Z Z by f x x2 5x 5 It is also not onto The function is a parabola with a global minimum calculus exercise at 52 …
View Full Document
Unlocking...