Composition of functions

50 %
50 %
Information about Composition of functions
Education

Published on March 12, 2014

Author: tylerisaacmurphy

Source: slideshare.net

Description

an exposition of homework problem 3.2.24 for BSU's math 189 - discrete math for CS majors.

Working with composition of functions and onto. Tyler Murphy March 12, 2014 Working with composition of functions and onto. Let’s consider an example problem that was in the book. Problem 3.2.24. 3.2.24 (a) Prove that the composition of onto functions is onto. (b) Show, by example, that the converse of (a) is not true. (c) Show that if g ◦ f is onto, then g must be onto. 3.2.24.a (a) Prove that the composition of onto functions is onto. Proof. Let f and g be onto functions, and A, B, C are sets. Define f : A → B and g : B → C. WTS: g ◦ f is onto. This means we want to show that for every element in the target of g, there is an element in the domain of g ◦ f that goes to it. So we want to show that for any element, say z ∈ C, there is an element, say x ∈ A that get moved over to it. Let z ∈ C. Since g is onto, then every element in C can be written to as g(y) for some element y in B. So, z = g(y). Since f is onto, then every element in B can be written as f(x) for some element x ∈ A. So y = f(x). By subsitution, we have that z = g(f(x)) which is (g ◦ f)(x) = z. So, every element in C gets hit by some element in A by g ◦ f. So, g ◦ f is onto. 1

3.2.24.b Here, we just want to find a counterexample to the claim that if g ◦ f is onto, then f is onto AND g is onto. Consider the sets: A = {0, 1}. B = {3, 4, 5}. C = {6, 7}. Define g ◦ f = {(0, 6), (1, 7)}, which is onto. Define g = {(3, 6), (4, 6), (5, 7)} is onto. But f = {(0, 3), (1, 4)} is not onto. BAM. DONE. 3.2.24.c Prove that if g ◦ f is onto, then g must be onto. First, let’s consider some incorrect thought processes. Define some sets A, B, C. A = {0, 1, 2}. B = {3, 4}. C = {6, 7, 8}. Define f : A → B as f = {(0, 3), (1, 3), (2, 4)}. Note that f is onto. Define g : B → C as g = {(3, 6), (4, 7)}. Note that g is not onto. Now here’s where you have to be careful. You cannot define g◦f as {(0, 6), (1, 7), (2, 8)}. Now, this set does represent some onto function from A → C, but this function is not g ◦f. Consider what it means to be in g ◦ f. This is g(f(x)) for some x in the dom(f). So g ◦ f is {(x, g(f(x))) | x ∈ A. So g ◦ f = {(0, g(f(0)), (1, g(f(1)), (2, g(f(2))}. So, g ◦ f is {(0, g(3)), (1, g(3)), (2, g(4))} So, g ◦ f is {(0, 6), (1, 6), (2, 7)}. Now you can see that g◦f is not onto Be careful when you are composing your functions that you don’t just go from the domain of f directly to the range of g. You have to stop in the middle at the ran(f) which is the dom(g). Now, let’s get to the proof. Claim: if g ◦ f is onto, then g must be onto. Proof. Let f and g be functions and g ◦ f be an onto function. Let A, B, C be sets such that f : A → B and g : B → C. Now, since g ◦ f is onto, we know that every element in C gets hit by some element in f mapped through g. Suppose g is not onto. Then there is some element, say z ∈ C such that g(y) = z, y ∈ B. Now we need to consider what happens when f is onto and when f is not onto. 2

Case1: Suppose f is onto. If f is onto, then we have every element in B can be written as f(x) for some x ∈ A. So y = f(x). So, g(f(x) = z. So g ◦ f is not onto, a contradiction. So, if f is onto, and g ◦ f is onto, then g must be onto. Case2: Suppose f is not onto. So there is some element in B, say y, such that f(x) = y for any element x ∈ A. Since g is not onto, then there is some element, say z ∈ C such that g(y) = z, y ∈ B. So, then for some element x ∈ A, f(x) = y and g(y) = z, so not everything in C gets hit. So g ◦ f is not onto, a contradiction. So, If g ◦ f is onto, then g must be onto. 3

Add a comment

Related presentations

Related pages

Composition of Functions: Composing Functions with Functions

Uses worked examples to demonstrate how to compose functions formulaically; that is, how to plug one function into another function.
Read more

Function composition - Wikipedia, the free encyclopedia

In mathematics, function composition is the pointwise application of one function to the result of another to produce a third function. For instance, the ...
Read more

Composition of Functions: Composing with Sets of Points

Explains the notation and terminology of function composition, and demonstrates how to compose functions given lists or graphs of their points.
Read more

Composition of Functions - Math is Fun - Maths Resources

Domains. It has been easy so far, but now you must consider the Domains of the functions. The domain is the set of all the values that go into a function.
Read more

Composition of Functions - YouTube

Composition of Functions ... Function Compositions - Duration: 6:50. Bill Witte 57,012 views. 6:50 Alternating Series - Duration: 6:01.
Read more

Intro to composing functions | Composing functions | Khan ...

Sal explains what it means to compose two functions. He gives examples for finding the values of composite functions given the equations, the graphs, or ...
Read more

Composition of Functions - Oswego City School District ...

Composition of functions can be thought of as a series of taxicab rides for your values. The example below shows functions f and g working ...
Read more

Composition of Functions - YouTube

I introduce composition of functions and discuss domain. Check out http://www.ProfRobBob.com, there you will find my lessons organized by class ...
Read more

Composition of Functions in Math-interactive lesson with ...

Composition of functions . Explained with interactive diagrams, examples and several practice problems!
Read more

Composition of Functions - AlgebraLAB: Making Math and ...

It is possible to combine two functions by adding, subtracting, multiplying or dividing two given functions. You can learn more about those operations by ...
Read more