DARTMOUTH COSC 030 - 02functions (5 pages)

A Very Special Type of Relation CS 30 Discrete Mathematics Amit Chakrabarti Winter 2017 Examples Class exercises 3 2 and 3 3 Equality the most important example Functions High school Viewpoint y x2 y sin x 40 1 5 35 Let S be a set A relation R on S that is re9lexive symmetric and transitive is called an equivalence relation Functions CS Viewpoint def square n return n n 1 30 0 5 25 20 0 15 0 5 10 5 1 0 0 2 4 6 1 5 def factorial n if n 0 return 1 else return n factorial n 1 Python function len s gives length of string s Functions Intuition Functions Definition Intuitively a function takes an input produces an output thus connects set of inputs with set of outputs thus is a kind of relation a very special kind A function from a set A to a set B is a relation f A B with the following property For every a A there exists one and only one b B such that a b f i e for every input there is an output and there is only one output ALERT This disagrees with Lehman Leighton Meyer book LLM agrees with the Rosen book Ros We write f a b instead of a b f Note that f a is always uniquely de9ined Functions Pictorial Functions Pictorial 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 6 6 6 The function f a a 1 from 1 2 3 4 to 1 2 3 4 5 6 The function f a a from 1 2 3 4 5 6 to itself Functions Pictorial Functions Pictorial 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 The function f a a 2 from 1 2 3 4 5 6 to itself A function from 1 2 3 4 5 6 to itself that has no obvious algebraic formula Not a Function Not a Function 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 Output unde9ined for input 2 Mathematically there is no pair 2 x in this relation More than one output for input 4 There should be only one pair of the form 4 x Functions More Definitions Suppose f is a function from A to B The notation to express this is f A B The set A is called the domain of f The set B is called the co domain of f The subset of B given by f x x A is called the range of f Note that the range is the set of all actual outputs of f whereas B is only a set of potential outputs Injective Functions Suppose we have a function f A B If no two elements of A produce the same output i e for every x y A if x y then f x f y i e arrows from different elements of A lead in to different elements of B then we say that f is injective f is an injection f is one to one Surjective Functions Suppose we have a function f A B If every element of B occurs as an actual output of f i e for every b B there exists an a A such that f a b i e there is an arrow leading in to every element of B then we say that f is surjective f is a surjection f is onto A Surjective Function 1 1 2 2 3 3 4 4 5 5 6 But not injective because f 3 f 5 An Injective Function 1 2 2 3 3 4 4 5 More Examples Let Z be the set of all integers Is the function f Z Z given by f x 2x injective Is it surjective Injective but not surjective How about f Z Z given by f x x 1 Both injective and surjective 5 How about f Z Z given by f x x 5 6 How about f Z Z given by f x x But not surjective because there is no x such that f x 3 Surjective but not injective Neither injective nor surjective Bijections Concepts Functions domain codomain range Surjective injective bijective A function that is both surjective and injective is called a bijective function or a bijection Examples Lots of examples of all the concepts we ve de9ined today Study them carefully Think up more examples Exercise Let f A B be a function where A and B are 9inite sets Can you say something interesting about A and B if f is surjective f is injective f is bijective Hint think about A and B Study Bee