# Functions

40 %
60 %
Education

Published on March 11, 2014

Author: tylerisaacmurphy

Source: slideshare.net

## Description

Functions and how to prove 1-1 and onto Tyler Murphy March 10, 2014 Before we get into these, let’s ﬁrst talk about some Deﬁnitions and notation. When we talk about a relation, R between two sets A and B, we can deﬁne R as a set of the ordered pairs in A x B. Now, IF for all ordered pairs in R, we have that for every a ∈ A, there is ONLY one b ∈ B paired with it, then we can say that R is a function from A to B. We can notate this as: R = f : A → B This simply states that R is a function that goes from the domain A to the target B. This is the vertical line test. For every x value, there is only one y associated with it. For the rest of the notes, we will refer to our function by the name f Terminology Deﬁnition 1-1 (one to one) The function passes the horizontal line test (hLT) Onto Everything in the target gets hit. That is, ran(f) = Target. Proving Onto In order to prove a function is a onto, we have to prove that: Target ⊆ Range. Dy deﬁnition we are given that Range ⊆ Target. Together these will give us that the Range = Target. Example Prove that f : R → R given the rule f(x) = x2 − x is onto. scratch work (not in ﬁnished proof): To be in the range, y must be equal to x2 − x. 1

So, y = x2 − x 0 = x2 − x − y x = 1 ± (−1)2 − (4)(1)(−y) 2(1) (by quadratic eq) x = 1 ± √ 1 + 4y 2 So this is the x value that gets mapped to any y in the target. Proof. WTS: ∀y ∈ R, ∃x ∈ R such that f(x) = y. That is, if we choose any element y of the target, we want to show that there is some element x in the domain that gets moved to that y. Let y ∈ R (target). Let x = 1 ± √ 1 + 4y 2 , which is in dom(f) = R. So, f(x) = f 1 ± √ 1 + 4y 2 = 1 ± √ 1 + 4y 2 2 − 1 ± √ 1 + 4y 2 . Now we just need to do some algebra. f( 1 ± √ 1 + 4y 2 ) = 1 ± 2 √ 1 + 4y + 1 + 4y 4 − 1 ± √ 1 + 4y 2 . = 2 + 4y ± √ 1 + 4y 4 − 2 ± 2 √ 1 + 4y 4 . = 2 + 4y ± √ 1 + 4y − 2 − ± √ 1 + 4y 4 . = 4y 4 . = y. So, since we have chosen y to be in the target and we have found some x in the domain that goes to our y, we have proven onto. Note: The key to proving onto is to take the rule of the function and work it backwards from the target to the domain. You have y = f(x) = ruled applied to x. If you solve for x, 2

it will give you the x you need to get to a y in the target. However, be careful that when you do this, the x value you get is still in the domain. Consider how this problem would have gone if f : N → R. Then when we found in the scratch work x = 1 ± √ 1 + 4y 2 , we would be outside the domain for all but a few values of y because 1 + 4y would have to be an odd perfect square or else you wouldn’t end up with a natural number for x. Proving 1-1 Proving 1-1 is much simpler than proving onto. First, think about what it means to be 1-1. It means for every value of x, there is only one associated y and for every y there is only one associated x. The ﬁrst of these we get for free when we are told it’s a function because all functions pass the vertical line test. So we only need to prove that the function satisﬁes the horizontal line test. Example 2 Prove that f : N → Z given by the rule f(x) = −2x + 10 is one to one. Proof. Remember that we are proving an if, then statement. If f(a) = f(b), then a = b. First, declare variables. Let f(a), f(b) ∈ ran(f). Now suppose that f(a) = f(b). Now, f(a) = −2a + 10 = −2b + 10 = f(b). So −2a + 10 = −2b + 10. So −2a = −2b by adding 10 to both sides. So a = b by dividing both sides by -2. So f is 1-1. If you can prove BOTH of these for a function, then you have proved that the function is a bijection. Having a bijection is extremely valuable. If you can create a bijection from a set to the natural numbers, then that set is countable, which is handy information. From that you also know that all subsets of your set are countable. Be careful though. Just because you can create a bijection from one set to another does NOT mean that those sets are countable. Consider f : R → R deﬁned by f(x) = x. This function is a bijection from the reals to the reals. However, the real numbers are not countable. This is because there is no possible bijection from the reals to the natural numbers. The key for countability is that the bijective function MUST go from a set to the natural numbers. 3

 User name: Comment:

January 26, 2020

January 26, 2020

January 25, 2020

January 25, 2020

January 25, 2020

January 25, 2020