Functions Section 2 3 of Rosen Fall 2008 CSCE 235 Introduction to Discrete Structures Course web page cse unl edu cse235 Questions cse235 cse unl edu Outline Definitions terminology function domain co domain image preimage antecedent range image of a set strictly increasing strictly decreasing monotonic Properties One to one injective onto surjective one to one correspondence bijective Exercices 5 Inverse functions examples Operators Composition Equality Important functions identity absolute value floor ceiling factorial CSCE 235 Fall 2008 Functions 2 Introduction You have already encountered function f x y x y f x x f x sin x Here we will study functions defined on discrete domains and ranges We will generalize functions to mappings We may not always be able to write function in a neat way as above CSCE 235 Fall 2008 Functions 3 Definition 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 Each and every element of A has a single mapping Each element of B may be mapped to by several elements in A or not at all CSCE 235 Fall 2008 Functions 4 Terminology Let f A B and f a b Then we use the following terminology A is the domain of f denoted dom f B is the co domain of f b is the image of a a is the preimage antecedent of b The range of f is the set of all images of elements of A denoted rng f CSCE 235 Fall 2008 Functions 5 Function Visualization Range Preimage Image f a b f a b B A Domain Co Domain A function f A B CSCE 235 Fall 2008 Functions 6 More Definitions 1 Definition Let f1 and f2 be two functions from a set A to R Then f1 f2 and f1f2 are also function from A to R defined by f1 f2 x f1 x f2 x f1f2 x f1 x f2 x Example Let f1 x x4 2x2 1 and f2 x 2 x2 f1 f2 x x4 2x2 1 2 x2 x4 x2 3 f1f2 x x4 2x2 1 2 x2 x6 3x2 2 CSCE 235 Fall 2008 Functions 7 More Definitions 2 Definition Let f A B and S A The image of the set 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 Note there that the image of S is a set and not an element CSCE 235 Fall 2008 Functions 8 Image of a set Example Let A a1 a2 a3 a4 a5 B b1 b2 b3 b4 b5 f a1 b2 a2 b3 a3 b3 a4 b1 a5 b4 S a1 a3 Draw a diagram for f What is the Domain co domain range of f Image of S f S CSCE 235 Fall 2008 Functions 9 More Definitions 3 Definition A function f whose domain and codomain are subsets of the set of real numbers R is called strictly increasing if f x f y whenever x y and x and y are in the domain of f strictly decreasing if f x f y whenever x y and x and y are in the domain of f A function that is increasing or decreasing is said to be monotonic CSCE 235 Fall 2008 Functions 10 Outline Definitions terminology Properties One to one injective Onto surjective One to one correspondence bijective Exercices 5 Inverse functions examples Operators Important functions CSCE 235 Fall 2008 Functions 11 Definition Injection Definition A function f is said to be one to one or injective or an injection if x and y in in the domain of f f x f y x y Intuitively an injection simply means that each element in the range has at most one preimage antecedent It may be useful to think of the contrapositive of this definition x y f x f y CSCE 235 Fall 2008 Functions 12 Definition Surjection Definition A function f A B is called onto or surjective or an surjection if b B a A with f a b Intuitively a surjection means that every element in the codomain is mapped i e it is an image has an antecedent Thus the range is the same as the codomain CSCE 235 Fall 2008 Functions 13 Definition Bijection Definition A function f is a one to one correspondence or a bijection if is both one to one injective and onto surjective One to one correspondences are important because they endow a function with an inverse They also allow us to have a concept cardinality for infinite sets Let s look at a few examples to develop a feel for these definitions CSCE 235 Fall 2008 Functions 14 Functions Example 1 A a1 b1 a2 b2 a3 a4 b3 b4 B Is this a function Why No because each of a1 a2 has two images CSCE 235 Fall 2008 Functions 15 Functions Example 2 A a1 b1 a2 b2 a3 a4 b3 b4 B Is this a function One to one injective Why Onto surjective Why CSCE 235 Fall 2008 Functions No b1 has 2 preimages No b4 has no preimage 16 Functions Example 3 A a1 b1 a2 b2 a3 b3 b4 B Is this a function One to one injective Why Onto surjective Why CSCE 235 Fall 2008 Functions Yes no bi has 2 preimages No b4 has no preimage 17 Functions Example 4 A a1 b1 a2 b2 a3 a4 b3 B Is this a function One to one injective Why Onto surjective Why CSCE 235 Fall 2008 Functions No b3 has 2 preimages Yes every bi has a preimage 18 Functions Example 5 A a1 b1 a2 b2 a3 a4 b3 b4 B Is this a function One to one injective Onto surjective CSCE 235 Fall 2008 Thus it is a bijection or a one to one correspondence Functions 19 Exercice 1 Let f Z Z be defined by f x 2x 3 What is the domain codomain range of f Is f one to one injective Is f onto surjective Clearly dom f Z To see what the range is note that b rng f b 2a 3 with a Z b 2 a 2 1 b is odd CSCE 235 Fall 2008 Functions 20 Exercise 1 cont d Thus the range is the set of all odd integers Since the range and the codomain are different i e rng f Z we can conclude that f is not onto surjective However f is one to one injective Using simple algebra we have f x1 f x2 2x1 3 2x2 3 x1 x2 QED CSCE 235 Fall 2008 Functions 21 Exercise 2 Let f be as …
View Full Document
Unlocking...