# Discrete! #31: Discrete Mathematics and Its Applications 2.3, Part C

2.3: Functions Part C (Starts with Inverse Functions and Compositions of Functions)

Inverse Functions and Compositions of Functions

Inverse functions are pretty much what you’d guess. If you have a function that maps from A to B, inverse functions get you back.

BOOK DEFINITION:

“Let f be a one-to-one correspondence from the set A to the set B. The inverse function of f is the function that assigns to an element b belonging to B the unique element a in A such that f(a) = b. The inverse function of f is denoted by $f^{-1}(a)$. Hence, $f^{-1}(b)=a$ when f(a) = b.”

This may seem pretty straightforward, but there’s a bit of cleverness going on. Remember how we said that if a single element in a maps to two elements in b, it’s not a function? Well, for that functions inverse, things get flipped. You can’t have a single element in b map to more than one element in a. In other words, in order to have an inverse, a function must be onto. In addition, in order that all the elements in B can get to some element in A, the function must be one-to-one.

Perhaps now you’re getting a sense of why this stuff matters. You have now got the power to determine if a function has an inverse within certain bounds.

Thus, when you have one-to-one correspondence (a.k.a. bijection, a.k.a. it’s one-to-one AND onto), we say the function is “invertible.” Now you understand why. If it is not in one-to-one correspondence, it is not invertible.

Note, that invertibility is not JUST about the functions. For example, f(a) = |b| is not invertible because, for example, -1 and 1 have the same absolutely value. BUT, if we restrict it so that we only ever use positive numbers, it IS invertible. It’s also a quite boring function, but that’s fine. So, you see, invertibility is about specific functions, specific domains, and specific codomains. This is why problems of this sort will specify a domain using a big letter, like R (reals) or Z (integers).

Compositions

Now, suppose you have a function that maps from A to B and another function that maps from B to C. We’ll call that first function g and the second one f. When you do both operations, we express that as f(g(a)) or f∘g(a). Personally, I prefer the former notation, annoyingly large amount of parens notwithstanding.

The book makes a quick note that’s very important: “Note that the composition of f∘g cannot be defined unless the range of g is a subset of the domain of f.”

That is, you start with the stuff in A, then you run g on it. If the output of g is not in the domain of f, you can’t run f on it.

Or, think of it like this:

Input 1 turns into Output 1 via function g.

Output 1 is now the Input for a new function, f. So, let’s call Output 1 “Input 2.”

If f can’t deal with “Input 2” (for example, if input 2 is zero and the function is 1/x), then shit don’t work. And, in the case of shit not working halfway through, you’ve got no composite function f∘g. For that matter, if you have a longer composite string, like f∘g∘h∘q∘n∘x, if it breaks down somewhere in the middle, you’re hosed.

(Sidenote: I feel like a deserve some applause for not mentioning “Human Centipede” even once here)

You can also just combine f(g(a)) into a brand new function. For example if running g means “add 2″ and running f means “multiply by 6″ then f(g(a)) = h(a) = 6*(a+2).

Graphs

Uh… yeah. If you don’t know what a graph of a function looks like, get off my Internet lawn.

Some Important Functions

Can you round up to the nearest integer? Can you round down to the nearest integer? Then you can do ceiling and floor functions.

Next stop: Interesting Problems in 2.3

This entry was posted in Autodidaction, Discrete Math. Bookmark the permalink.

### 5 Responses to Discrete! #31: Discrete Mathematics and Its Applications 2.3, Part C

1. OmniZ says:

Personally, I really don’t like it when text treat functions and total functions as the same thing. Partial functions exist and are important in computability theory, dammit!

2. Stephan says:

It seems to me that you’re mixing up onto and one-to-one in your explanation just after the book definition. For a function to have an inverse, it needs to be one-to-one, not necessarily onto.

• ZachWeiner says:

My understanding is that if it’s not onto, you’ll have elements in the new domain that don’t connect with anything in the new codomain any more, so you can’t simply invert.

• Stephan says:

Sure, but what you said was: “You can’t have a single element in b map to more than one element in a. In other words, in order to have an inverse, a function must be onto.”

But if a single element in b maps to more than one element in a, that means the original function f(a) = b was not one-to-one. It could still be onto.

Take f(x) = y defined on the domain a={1, 2} and codomain b={1}:
f(1) = 1
f(2) = 1
f is not one-to-one, but it is onto. There is no inverse for f, because the inverse would not be a function.

Conversely, take g(x) = y defined on the domain a={1,2} and codomain b={1,2,3}:
g(1) = 2
g(2) = 1
Now g is one-to-one, but not onto. You still don’t have an inverse because 3 in the new domain would not map to anything, but there’s no single element in b mapping to more than one element in a. (You could even invert g if you just get rid of that pesky 3 in b. It’s not doing anything anyway.)

That was a little bit more verbose than I intended but hopefully it explains what I meant by my original comment.

• Stephan says:

Ah, I just reread my comment. My bad. It does need to be both one-to-one and onto for the inverse to be defined over the entire domain (which was the codomain of the original function; damn, math in words is complicated).

The point I was trying to make was that your arguments seem to mix around onto and one-to-one. Still, I think one-to-one is a little more important than onto.