DARTMOUTH COSC 030 - 02functions (5 pages)

Unformatted text preview:

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