Misc
Problem Set
Problem set on sets and functions: see handout for details.
GROW STEM Talk
“Status of Women and Under-Represented Groups in various fields of STEM”
Led by Provost Stacey Robertson
Thursday, April 19, 5:00 pm
Newton 204
Questions?
Composition of Functions
Section 6.4.
Basic Idea
Based on Progress Check 6.18. Pick one of the functions given and see how many different ways you can express it as a composition of 2 functions. How about as compositions of 3 or more functions?
For example, g(x) = cos( (2x-3) / (x2+1) ) could be written as a( b(x), c(x) ) where a(x,y) = cos( x/y ), b(x) = 2x-3, and c(x) = x2+1. This makes a neat example of composition being used with a combination of 1- and 2-variable functions.
As another example, f(x) = |x2-3| could be written as a(b(x)) where a(x) = |x| and b(x) = x2-3. Or a bit more interesting, c(d(x)) where c(x) = |x-3| and d(x) = x2.
Reasoning about Composition
Suppose f : A → B, g : B → C.
Ranges
Is it possible for range(g ○ f) to be a proper subset of range(g) (i.e., to have range(g ○ f) ⊂ range(g))?
Yes. Consider this example: f : ℝ →ℝ defined by f(x) = x2, g : ℝ →ℝ defined by g(x) = x3. Then range(g) = ℝ, but range( g ○ f ) = ℝ* where ℝ* = [0,∞), i.e., the non-negative reals.
Implications
If it’s possible to have range(g ○ f) ⊂ range(g), what does having it happen tell you about f?
That codom(f) ≠ range(f), i.e., f is not a surjection.
Conjecture
State any implication deduced above as a conjecture/theorem and prove it.
Theorem: Let A, B and C be sets, and f : A → B, g : B → C be functions. Then if range(g ○ f) ⊂ range(g) then f is not a surjection.
Proof: We use the contrapositive to prove that if range(g ○ f) ⊂ range(g) then f is not a surjection. So assume that f is a surjection and use element chasing to show that range(g ○ f) = range(g). In particular, suppose x is in range(g ○ f) , i.e., x = g( f(y) ) for some y in A. But what’s important about this is that x is the result of g applied to anything, because that shows that x is in range( g ). We thus have that range(g ○ f) ⊆ range(g). In the other direction, suppose x is in range(g). Then x = g(y) for some y in B. Further, since f is a surjection, y = f(z) for some z in A. Thus x = g(f(z)), i.e., x is in range(g ○ f). So we have that range(g) ⊆ range(g ○ f). We have now shown both that range(g ○ f) ⊆ range(g) and that range(g) ⊆ range(g ○ f), so we have proven that if f is a surjection then range(g ○ f) = range(g). This also establishes the contrapositive, namely that if range(g ○ f) ≠ range(g) then f is not a surjection. Finally, note that range(g ○ f) must be a proper subset of range(g) or equal to it, so if range(g ○ f) isn’t equal to range(g), it must be a proper subset. QED.
Key Points
Concrete examples of compositions and the notation for them.
Prove things about compositions by element-chasing through the appropriate function applications.
Next
Inverse functions.
Read section 6.5.