Functions on Sets

Return to List of Lectures

Previous Lecture

Misc

Colloquium

• “Precision Medicine in the Age of ‘Big Data’: Leveraging Machine Learning and Genomics for Drug Discoveries”
• Katie Gayvert, Geneseo math alumna, class of 2012.
• Monday, April 17, 2:30, Newton 203.
• Extra credit for writing up connections you make to the colloquium, as usual.

Problem set re functions

• See handout for details

Questions?

Functions on Sets

Section 6.6

The Idea

Let A = { -3, -2, -1, 0, 1, 2, 3 }, B = { -1, 0, 3, 8 }, and f : A → B be f(x) = x² - 1.

What is f( {1,2,3} )? What is f^-1( {-1,3} )?

Relevant ideas or questions from the reading?

• If f : S → T is a function and A ⊆ S then the image of A under f = f(A) = { f(x) | x ∈ A }.
• If f : S → T is a function and C ⊆ T then the preimage of C under f = f^-1(C) = { x ∈ S | f(x) ∈ C } = { x ∈ S | for some y, (x,y) ∈ f and y ∈ C }.

Solutions

• f( {1,2,3} ) = { 0, 3, 8 }
• f^-1( {-1,3} ) = { 0, -2, 2 }

Comments

• The idea of applying a function to a value scales up to applying the function to a set of values simply by applying it to each member of the set.
• The idea of a function’s inverse also scales up, but a little more elegantly because the idea of “applying” the inverse to a value is well defined when the inverse is a function but not so well defined when the inverse isn’t, whereas the idea of a set of values that f maps to a set within the codomain is well-defined in both cases.

Theorem 6.34 Part 2

Prove that if f : S → T is a function and A and B are subsets of S then f(A ∪ B) = f(A) ∪ f(B)

Relevant ideas or questions from the reading?

• Examples of theorems about how subsets of the domain relate to subsets of the codomain in the presence of set operations.
  • For example, Theorem 6.34 says f(A∩B) ⊆ f(A) ∩ f(B) and f(A ∪ B) = f(A) ∪ f(B), but Sundstrom only proves the first
• Generally you can prove set equality as a biconditional, x ∈ A if and only if x ∈ B.

Proof:

• Show that f(A ∪ B) and f(A) ∪ f(B) are subsets of each other.
• First direction: for any y in f(A ∪ B), y = f(x) where x ∈ A ∪ B, so x ∈ A or x ∈ B. Case 1, if x ∈ A, then f(x) = y is in f(A) so y ∈ f(A) ∪ f(B). Case 2, if x ∈ B, f(x) = y is in f(B) so y ∈ f(A) ∪ f(B).
• Second direction: for any y in f(A) ∪ f(B), y ∈ f(A) or y ∈ f(B). Case 1, y ∈ f(A), so y = f(x) for some x in A, and so x ∈ A ∪ B. Case 2, y ∈ f(B) so y = f(x) for some x in B, so x ∈ A ∪ B. In both cases x ∈ A ∪ B so f(x) = y is in f(A ∪ B).

Comments:

• This proof demonstrates an element-chasing style of proof that works well for many theorems about functions on subsets of domains/codomains.

Subsets

Many of the theorems in this section involve set equalities, e.g., f(A ∪ B) = f(A) ∪ f(B); f^-1(C∩D) = f^-1(C) ∩ f^-1(D); f^-1(C∪D) = f^-1(C) ∪ f^-1(D). But 3 involve subsets instead: f(A∩B) ⊆ f(A) ∩ f(B), A ⊆ f^-1(f(A)); f(f^-1(C)) ⊆ C. Is it really possible for these subsets to be proper?

We’ll look at this question at the beginning of Monday’s class.

Overall Comments

The main point here is that functions and inverse functions scale from individual values to sets of values, but the consequences for how function application works with set operations aren’t always the “natural” ones.

Next

Finish looking at the subset question from above.

Relations, and particularly equivalence relations.

Read textbook sections 7.1 and 7.2

Next Lecture