Notes Functions Slides by Christopher M Bourke Instructor Berthe Y Choueiry Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 1 8 of Rosen cse235 cse unl edu Introduction Notes You ve already encountered functions throughout your education f x y x y f x x f x sin x 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 Definition Notes Function 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 Definitions Notes Terminology 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 of b I The range of f is the set of all images of elements of A denoted rng f Definitions Notes Visualization Preimage Range Image f a b f a b A B Domain Codomain A function f A B Definition I Notes More Definitions 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 Notes More Definitions Let f1 x x4 2x2 1 and f2 x 2 x2 then f1 f2 x f1 f2 x 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 f S f s s S Definition III Notes More Definitions 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 Definition Definition IV More Definitions 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 Notes Injections Surjections Bijections I Notes Definitions Definition A function f is said to be one to one or injective if 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 A uniquely maps to an element in b It may be useful to think of the contrapositive of this definition x 6 y f x 6 f y Injections Surjections Bijections II Notes 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 Injections Surjections Bijections III Definitions 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 Notes Function Examples Notes A Non function A B a1 b1 a2 b2 a3 b3 a4 b4 This is not a function Both a1 and a2 map to more than one element in B Function Examples Notes A Function Neither One To One Nor Onto A B a1 b1 a2 b2 a3 b3 a4 b4 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 Notes One To One Not Onto A B a1 b1 a2 b2 a3 b3 b4 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 Function Examples Notes Onto Not One To One A B a1 b1 a2 b2 a3 b3 a4 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 Notes A Bijection A B a1 b1 a2 b2 a3 b3 a4 b4 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 Exercises I Notes Exercise I Example Let f Z Z be defined by f x 2x 3 What is the domain and range of f Is it onto One to one Clearly dom f Z To see what the range is note that b rng f b 2a 3 a Z b 2 a 2 1 b is odd Exercises II Notes Exercise I 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 However f is one to one To prove this note that f x1 f x2 2x1 3 2x2 3 x1 x2 follows from simple algebra Exercises Notes Exercise II Example Let f be as before f x 2x 3 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 Exercises I Notes Exercise III Example Define f Z Z by f x x2 5x 5 Is …
View Full Document
Unlocking...