[Discrete Math] f: A->B; surjective? find necessary & sufficient condition.

[Servo888]

[Discrete Math] f: A-->B; surjective? find necessary & sufficient condition.

Ok in practice for my discrete exam, I have the following problem.

Let f : A->B be a function.
a) Show that if f is surjective, then whenever g o f = h o f holds for the functions g,h : B -> C, then g =h.

b) Find a necessary and sufficient condition for f such that for any set C and any functions g,h:B->C, if g o f = h o f, then g = h


I need help at starting this problem. How do I start on a)? Here's what I know,

g o f : A -> C , so (g o f)(a) = g(f(a)),

such that (a,c) are elements in g o f <=> [tex]\exists b \in B:(a,b)\in f[/tex], [tex](b,c)\in g[/tex]

I hope that latex stuff comes out right. Anyways I've got 3 hours to figure this out. I just need a push forward, maybe some hints, or suggestions.

 

[0rthodontist]

For the first one, prove it by contradiction. If g, h are unequal then there must be some element (b, c) of g that is not an element of h (without loss of generality; it could be the other way around but in that case simply rename h g and rename g h). But since f is onto, what can you say about g o f that you can't say about h o f with regards to (b, c)?

 

[Servo888]

Here's what I don't understand... When you have g(f)=h(f), obviously g = h...

As far as proving it by contradiction... If g,h are unequal, then there must be some element (b,c) of g that is not an element of h. But since f is onto, you can say that (b, c) [tex] \in [/tex] g(f), and you can't say (b, c) [tex] \in [/tex] h(f) (I think).

 

[0rthodontist]

No, you're wrong. Here's the problem:

Here's what I don't understand... When you have g(f)=h(f), obviously g = h...

Let A = {1, 2}, let B = {3, 4}, and let C = {5, 6}
Let f = {(1, 3), (2, 3)}
g = {(3, 5), (4, 5)}
h = {(3, 5), (4, 6)}
Now is it true that g o f = h o f here? And is it true that g = h? Do you understand why not?

 

[Servo888]

No, you're wrong. Here's the problem:

Let A = {1, 2}, let B = {3, 4}, and let C = {5, 6}
Let f = {(1, 3), (2, 3)}
g = {(3, 5), (4, 5)}
h = {(3, 5), (4, 6)}
Now is it true that g o f = h o f here? And is it true that g = h? Do you understand why not?

What's g(f) and h(f), I don't understand how to show g(f) and h(f) using sets.

g != h

 

[0rthodontist]

Do you know about the definition of functions as sets of ordered pairs?

 

[Servo888]

Do you know about the definition of functions as sets of ordered pairs?

(a,b) in f, is f(a)=b? like that?

 

[0rthodontist]

Yes, so can you figure out what functional composition looks like for ordered pairs?

 

[Servo888]

Yes, so can you figure out what functional composition looks like for ordered pairs?

Something like
g(f(a))=g(b)=c (a,c)
But somebody is going to have to give me an example of using the sets A, B, C, because I'm drawing a blank as to how the hell to get g(f(a))=g(b)=c by replacing the a's, b's, c's with the numbers in the sets...

 

[AKG]

No need to look at it as ordered pairs. Work by contradiction though. Suppose g and h are unequal, even though f is surjective and (g o f) = (h o f). Then by definition of equality of functions, there is some b in B such that:

g(b) != h(b)

But for all b in B, there is an a in A such that f(a) = b, since f is surjective, so there is some a in A such that:

g(f(a)) != h(f(a))

By definition of composition, this means that there is some a such that:

(g o f)(a) != (h o f)(a)

By definition of equality of functions, this means that

(g o f) != (h o f)

contradiction.

For part ii), look at why a surjective f makes [(g o f) = (h o f)] imply [g = h]. It's because if f weren't surjective, then there could be some element of B, call it b, which f doesn't reach, but which g and h differ on. If g and h differ on b, then g != h, but if f never reaches b, then as long as g and h agree on Im(f), (g o f) = (h o f). So what is the necessary and sufficient condition on f such that (g o f) = (h o f) implies g = h? It's that g and h don't differ on B - Im(f). So either Im(f) = B (that is, f is surjective), or |C| < 2, making it impossible to differ no matter how big B is and no matter how small Im(f) is.

 

[matt grime]

I would go further than AKG: please don't think about functions as ordered pairs, I implore you.

As for the second part of the question, think about it as word association.

Right cancellation is to surjective as left cancellation is to...

can only be one thing, really. Now prove it.

Can I give another example?

Suppose that f maps into the set {0,1}, and suppose that it isn't surjective, well, that just means that f(x)=0 for all x (or f(x)=1 for all x, doesn't matter which).

Now, I can make g and h whatever the hell I feel like and gf(x)=g(0) and hf(x)=h(0) for all x.

So I am free to make g(0)=h(0) and we get gf=hf, and I'm free to make g(1) and h(1) completely different. (This is AKG's 'parts that f doesn't reach').

This shows that right cancellation implies f is surjective, it is up to you to prove the opposite thing.

 

[0rthodontist]

By definition of equality of functions, this means that

Well, you're saying the same thing. Equality of functions is just equality of sets.

There is sometimes an advantage to looking at functions as ordered pairs. I am taking formal language theory and we see that an automaton Q, sigma, delta, q0, F can be represented as a graph where the edges correspond to ordered pairs in the function delta. function = ordered pairs = edges of a graph. That would not have been as clear without the ordered pair concept.

 

[AKG]

Of course it is technically saying the same thing, but the whole point is that looking at them as ordered pairs is a poor way to look at them. Looking at them as edges of a graph is an even worse way to look at them. The goal here was to prove some property of surjective functions, not to think up all possible ways to regard functions.

 

[0rthodontist]

In finite automata it seems that visualization as graphs is really the best way to think about the automata, from an intuitive perspective. I'm not saying you need to explicitly think about ordered pairs in this problem but it is not entirely useless. It seems to me that the best way to think about easy function problems like this is in terms of domain-codomain diagrams, where the idea of images and preimages gets close to ordered pairs.

Anyway, it's simple to give counterexamples in the notation of ordered pairs. You could organize it as a table, but why bother. The notation is there, it only takes a minute to learn if he doesn't already know it, and he may run into it later.

 

[AKG]

I agree that thinking in terms of domain-codomain diagrams with pictures of images and preimages is a good, if not natural way to think about these problems. If you believe that ordered pairs, graphs, or automata (whatever those may be) are somehow easier, more intuitive, more effective, or at all necessary, then go ahead and believe it, but I don't think you'll convince me. It's simple to give a counterexample in any notation, I would bet, but in which "notation" is it easiest to think of a counterexample?

 

[matt grime]

If you think only in terms of ordered pairs to describe functions then the number of functions you can actually work with reasonably is vanishingly small.