Introduction to Functions

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

(No.)

Problem Set 10

Problem set 10 isn’t technically assigned yet, but is available in Canvas if you want an early look at it.

Functions

Based on sections 6.1 and 6.2 in the textbook, and this functions discussion.

Any questions about the reading or discussion?

(No.)

Composition

Try to apply the ideas and terminology from the textbook to the idea of function compositions, and vice versa.

As context, consider these sets:

• A = {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,t,s,u,v,w,x,y,z}
• S = { β | β is a sequence of letters from A } (S is the set of all “strings over A”)
  • e.g., “hello” ∈ S

Are the following functions (using not-quite-ideal notation P(A) to denote the power set of A)?

• f : S → P(A) defined by f(β) = { α | α appears in β }
  • e.g., f(“hello”) = {e,h,l,o}
• g : P(A) → ℕ ∪ {0} defined by g(γ) = |γ| (this was originally g : P(A) → ℕ, but I realized while typing up these notes that P(A) includes the empty set which has size 0, so the codomain of g has to be at least the natural numbers and also 0.)
  • e.g., g( {e,h,l,o} ) = 4

A function is...

• A mapping from 1 set to another, that…
• …Applies to every element of 1st set, and…
• …For each, produces exactly 1 element of the second set.

Both of the above examples meet this definition, and so are functions. This is true even though they don’t have all the features you might associate with functions, e.g., they mostly aren’t numeric, there isn’t a formula that defines how to calculate them, etc.

What is g ○ f?

The notation means the “composition” of g with f, i.e., g( f(x) ).

Think about what sets it works with. First, any “input” to g ○ f has to be something that can be input to f, so presumably has to be a member of S. Then f will produce a member of P(A), to which g can apply, producing a natural number (or 0). So we can say that g ○ f : S → ℕ ∪ {0}

It’s getting awkward to talk about “inputs” to functions, the sets inputs can come from, etc. It would be nice to have short terms for those things. And, of course, we have them from the reading!

The set from which inputs come is the function’s domain, the set it maps those to is the codomain. But people can choose codomains somewhat arbitrarily, in particular a function doesn’t have to map something to every member of the codomain. For example, we could redefine function g above as g : P(A) → ℝ, even though only some real numbers are possible sizes of sets. The set of values that the function actually maps something to is the function’s range. Every element of the range is the image of some element of the domain. Note that range is a subset of codomain.

Rules about compositions of the form h ○ k:

• dom(h ○ k) = dom(k)…
• …as long as range( k ) ⊆ dom(h)
• codom(h ○ k) = codom( h )

Does range(h ○ k) = range( h )? We suspected that it doesn’t have to. The challenge is then to show a counter-example in which the range of the composition really isn’t equal to the range of h. Since we ran out of time at this point, this will be a topic for discussion between now and Monday, and we’ll wrap it up in Monday’s class.

Next

Find the counter-example to show range(h ○ k) ≠ range( h ).

Some special types of function: injections, surjections, and bijections.

Please read section 6.3 of the textbook.

Please also contribute to this discussion of function types.

Next Lecture