Discrete! #30: Discrete Mathematics and Its Applications: 2.3B

2.3: Functions Part B (Starts with One-to-One and Onto functions)

One-to-One and Onto Functions

BOOK DEFINITION:

“A function f is said to be one-to-one, or injective, if and only if f(a) = f(b) implies that a=b for all a and b in the domain of f. A function is said to be an injection if it is one-to-one.”

Here’s a rule for math – the easier a concept is, the harder it is to grok the definition.

First, off, it’s slightly annoying that they use “a” and “b” here, since they were used earlier for domain (A) and codomain (B) elements. In this definition, the “a” and “b” are just elements of the domain.

Here’s a less rigorous way to say this definition: If the only way to get two of the same result after running a function is by having the inputs to the function be equal in the first place, that’s called one-to-one.

And more human friendly: If each input maps to exactly one output, your function is one-to-one.

Got it?

The book also supplies a nice symbolic logic definition of this, which I actually find a little easier to understand than the English language version:

∀a∀b(f(a) = f(b) → a=b)

For all a and all b, if the output of each is equal, the inputs must be equal too.

Practically, this means that if you put a point on the left for each domain member and a point on the right for each codomain member, and you draw arrows between preimages and images, every arrow points from exactly one point to exactly one other point. Importantly, there may be points in the codomain that cannot be reached by the function. This is okay. It’s still “one-to-one.” One-to-oneness is about one-to-one correspondence for each element of the domain with an element of the codomain.

The book goes on to give an example, the basic idea of which is this. If you have an “increasing” function, that means whenever you bump the input, you get an output that’s not smaller. Note, that such a function might not be one-to-one. Why? Because if the input increases, but the output stays the same, you have two inputs pointing to just one output. That’s not one-to-one correspondence. A similar rule applies for decreasing functions.

BUT, since the only problem is with cases where the output stays the same, we can eliminate that instance via the word “strictly.” A strictly increasing function is a function where bigger input means bigger output, period. In that case, you DO have a one-to-one function.

BOOK DEFINITION:

“A function f from A to B is called onto, or surjective, if and only if for every element b∈B there is an element a∈A with f(a) = b. A function f is called a surjection if it is into.”

Fuckin’ “onto.” Yes, from now on you’ll be using a preposition as an adjective.

Now then, here’s a less rigorous form of that definition: If for every output there’s at least one input, the function between them is called “onto.”

Going back to our “points on the left with arrows to points on the right” schema, in an onto function, nobody gets left out. You can think of people on the left as givers and people on the right as receivers and the function arrows as huge penises. For an onto function, everyone gets some amount of penis. You might get two or more penises (in which case, these trysts aren’t one-to-one), but no matter what, everyone on the right gets something.

This is different from one-to-one. Imagine in both cases we’re talking about sex parties. Instead of outputs, we have people already at the party, instead of inputs we have have people coming to the party to sex up the outputs.

At a party that’s one-to-one, everyone who comes to the party gets satisfied by exactly one person who was already at the party. That is, the people who come pick exactly one sex partner each. This is a one-to-one sex party. People who were already there may be left out, but so it goes.

At a party that’s onto, everyone who was already at the party gets to receive sex.

So, what happens if you want to combine these… what if you want the intimacy of the one-to-one party, but you also want to make sure everyone gets boned?

BOOK DEFINITION:

The function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto.

Okay, that’s pretty straightforward. In sex party terms: A bijection party is when everyone hooks up with exactly one other person.

The book gives a few examples of non-bijective functions. Let’s go through in sex party terms.

1) Only one-to-one, not onto: Every guest gets to bone exactly one person. Some hosts get left out.

2) Only onto, not one to one: No host goes unboned. And (so it’s not one-to-one) at least one host gets boned by more than one guest.

3) One-to-one AND onto: No host goes unboned and each guest pairs with exactly one host.

4) Neither one-to-one NOR onto: At least one host gets boned by more than one guest. Meanwhile, at least one host gets left out. Think of this as what would happen if Charlie Brown threw a sex party.

5) Not a function: At least one guest bones two different hosts. Remember, in our analogy, functions are the penises. Well, nobody has more than one penis. Or, if they do, they probably have problems getting them to… function.

OKAY THEN, not the best analogy, but you’ll remember it.

In case you don’t want to be thinking about orgies while figuring this out, I like to think about bijection using something I call “the ladder rule.”

It goes thus: If you have a bijection, and your points on left and right are in a certain order, and you think of the arrows in between as ladder rungs, you’ll have a perfect ladder.

If your function isn’t onto, you can have lots of straight rungs, but you’ll have gaps.

If your function isn’t one-to-one, you’ll have to have some diagonal rungs, because multiple left sides go to just one right side.

If your function is neither, you’ll have missing rungs AND diagonal rungs.

If your function is both, in the right order, there is exactly one rung between left and right. A perfect ladder.

OKAY, got it?

That took a bit longer than I expected, but this is very very important. So, I’ll leave it there for now, and we’ll finish this chapter next time.

Next stop: Inverse Functions and Compositions of Functions

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

2 Responses to Discrete! #30: Discrete Mathematics and Its Applications: 2.3B

1. Brian Howard says:

When you say, “If each input maps to exactly one output, your function is one-to-one” (or, “Every guest gets to bone exactly one person”), to me that sounds more like the requirement simply to be a function, not necessarily a one-to-one function. That is, a function gives exactly one output for each input (as opposed to a general relation, which might relate some inputs to several outputs and others to none at all).

A better informal description of one-to-one I think follows your less rigorous version of onto (“If for every output there’s at least one input, the function between them is called “onto””). You can flip this to get, “If for every output there’s at most one input, the function between them is called “one-to-one.”” Or, if you prefer, “no host gets boned by more than one guest.”

2. Ciaran says:

“And more human friendly: If each input maps to exactly one output, your function is one-to-one.”
You mean: “If each input maps to a different output, your function is one-to-one.” or “If each output maps to exactly one input, your function is one-to-one.” I think