Composition of functions

50 %
50 %
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. Deﬁne 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 ﬁnd 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}. Deﬁne g ◦ f = {(0, 6), (1, 7)}, which is onto. Deﬁne 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. Deﬁne some sets A, B, C. A = {0, 1, 2}. B = {3, 4}. C = {6, 7, 8}. Deﬁne f : A → B as f = {(0, 3), (1, 3), (2, 4)}. Note that f is onto. Deﬁne 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 deﬁne 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

 User name: Comment:

Related presentations

PHP Industrial Training Institute in Bareilly - Co...

November 20, 2017

Get Hands on Best PHP Training In Indore

November 21, 2017

1128_Presentatie_GroepB_Presentatie3

November 24, 2017

What Is Nitrous Oxide and Is It Safe

November 24, 2017

JavaScript training in Noida

November 23, 2017

BUS 499 STUDY Possible Is Everything - bus499study

November 24, 2017

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.

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 ...

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.

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.

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

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 ...

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 ...