Register to reply

What {in,sur}jectivity of composite map implies for components

by Rasalhague
Tags: components, composite, implies, surjectivity
Share this thread:
Rasalhague
#1
Feb5-12, 10:22 PM
P: 1,402
I'm looking at Munkres: Topology Problems 1.2.4(c), 1.2.4(e), and 1.2.5(a). Problem 1.2.4(c) asks, "If [itex]g\circ f[/itex] is injective, what can you say about the injectivity of f and g?" Problem 1.2.4(e) asks, "If [itex]g\circ f[/itex] is surjective, what can you say about the surjectivity of f and g?"

I concluded [itex]g\circ f[/itex] injective implies that both f and g are injective, and that [itex]g\circ f[/itex] surjective implies both f and g surjective.

But Problem 1.2.5(a) is worded in a way which suggests my conclusion might be too strong: "Show that if f has a left inverse, then f is injective; and if f has a right inverse, then f is surjective."

Am I mistaken?

Let [itex]f:A\rightarrow B[/itex] and [itex]g:B\rightarrow C[/itex]. According to Munkres' definition of function composition, [itex]g\circ f[/itex] is only defined if f is surjective; so clearly [itex]g\circ f[/itex] surjective implies f is surjective.

For Problem 1.2.4(c), I reasoned as follows. If [itex]g\circ f[/itex] is injective, then

[tex]f[a_1]=f[a_2][/tex]

[tex]\Rightarrow (g\circ f)[a_1]=(g\circ f)[a_2][/tex]

[tex]\Rightarrow a_1 = a_2,[/tex]

so f is 1-1 too.

And if [itex]g[b_1]=g[b_2][/itex], then

[tex](\exists a_1,a_2\in A)[(b_1=f[a_1])\&(b_2=f[a_2])][/tex]

and, for this [itex]a_1,a_2[/itex],

[tex](g\circ f)[a_1]=(g\circ f)[a_2][/tex]

[tex]\Rightarrow a_1 = a_2[/tex]

[tex]\Rightarrow b_1 = b_2,[/tex]

so g is 1-1.

For Problem 1.2.4(e), I reasoned as follows. As mentioned above, f is surjective. So for all b in B, there exists some a in A such that b = f[a]. Suppose for all c in C, there exists some a in A such that g[f[a]] = c, and let b = f[a]. Then for all c in C, there exists some b in B, namely f[a], such that g[b] = c; so g is surjective too.
Phys.Org News Partner Science news on Phys.org
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
Rasalhague
#2
Feb6-12, 09:28 AM
P: 1,402
Quote Quote by Rasalhague View Post
According to Munkres' definition of function composition, [itex]g\circ f[/itex] is only defined if f is surjective; so clearly [itex]g\circ f[/itex] surjective implies f is surjective.
Aaaaaah, could this be what was confusing me? Munkres uses the word "range" to mean what, in my experience, is normally called "codomain". He writes, "Note that [itex]g \circ f[/itex] is only defined when the range of f equals the domain of g." Given f:A-->B and g:B-->C, he defines the composition [itex]g\circ f[/itex] as a function having a rule of the form a in A maps to c in C such that, for some b in B, b=f[a] and c=g[b]. Specifically, he defines the rule of a function as the set of pairs of (in this case) the form (a,c) = (a,[itex]g\circ f[/itex][a]). So there must be at least one such element of B, but I don't think he's making any requirement that the domain of g equal the image set of f. I also don't see how we can conclude from his definition that the domain of g equals the codomain of f.

Elsewhere (Bishop & Goldberg: Tensor Analysis on Manifolds, 0.1.4), I've seen composition defined without even the requirement that the domain of g intersect, let alone equal, the codomain of f. If they don't intersect, the result of composition is what they call the empty function. As far as I can see, Munkres' definition in terms of pairs allows nonequality, but not non-intersection.
Deveno
#3
Feb6-12, 10:06 AM
Sci Advisor
P: 906
Quote Quote by Rasalhague View Post
I'm looking at Munkres: Topology Problems 1.2.4(c), 1.2.4(e), and 1.2.5(a). Problem 1.2.4(c) asks, "If [itex]g\circ f[/itex] is injective, what can you say about the injectivity of f and g?" Problem 1.2.4(e) asks, "If [itex]g\circ f[/itex] is surjective, what can you say about the surjectivity of f and g?"

I concluded [itex]g\circ f[/itex] injective implies that both f and g are injective, and that [itex]g\circ f[/itex] surjective implies both f and g surjective.

But Problem 1.2.5(a) is worded in a way which suggests my conclusion might be too strong: "Show that if f has a left inverse, then f is injective; and if f has a right inverse, then f is surjective."

Am I mistaken?

Let [itex]f:A\rightarrow B[/itex] and [itex]g:B\rightarrow C[/itex]. According to Munkres' definition of function composition, [itex]g\circ f[/itex] is only defined if f is surjective; so clearly [itex]g\circ f[/itex] surjective implies f is surjective.

For Problem 1.2.4(c), I reasoned as follows. If [itex]g\circ f[/itex] is injective, then

[tex]f[a_1]=f[a_2][/tex]

[tex]\Rightarrow (g\circ f)[a_1]=(g\circ f)[a_2][/tex]

[tex]\Rightarrow a_1 = a_2,[/tex]

so f is 1-1 too.

And if [itex]g[b_1]=g[b_2][/itex], then

[tex](\exists a_1,a_2\in A)[(b_1=f[a_1])\&(b_2=f[a_2])][/tex]

and, for this [itex]a_1,a_2[/itex],

[tex](g\circ f)[a_1]=(g\circ f)[a_2][/tex]

[tex]\Rightarrow a_1 = a_2[/tex]

[tex]\Rightarrow b_1 = b_2,[/tex]

so g is 1-1.

For Problem 1.2.4(e), I reasoned as follows. As mentioned above, f is surjective. So for all b in B, there exists some a in A such that b = f[a]. Suppose for all c in C, there exists some a in A such that g[f[a]] = c, and let b = f[a]. Then for all c in C, there exists some b in B, namely f[a], such that g[b] = c; so g is surjective too.
f need not be surjective for [itex]g \circ f[/itex] to be defined.

consider f(x) = x2, g(x) = x+1.

note that [itex]g \circ f[/itex] makes sense for all real x, even though f never takes on any negative values.

on the other hand, if f(x) = x+1, and g(x) = √x, THEN we have a problem, for it's not clear what value to give to [itex]g \circ f(-2)[/itex].

because of this, [itex]g \circ f[/itex] might be injective, even if g isn't:

let A = {a,b,c}, B = {w,x,y,z} C = {s,t,u} with f:A→B, g:B→C

f(a) = x
f(b) = y
f(c) = z

g(w) = s <--
g(x) = s <--g not injective
g(y) = t
g(z) = u

then gof(a) = g(f(a)) = g(x) = s
gof(b) = g(f(b)) = g(y) = t
gof(c) = g(f(c)) = g(z) = u

gof is clearly injective, but g is not. why? because im(f) < dom(g).

a similar situation holds when gof is surjective, g has to be surjective, but f need not be.

Rasalhague
#4
Feb6-12, 03:52 PM
P: 1,402
What {in,sur}jectivity of composite map implies for components

Quote Quote by Deveno View Post
f need not be surjective for [itex]g \circ f[/itex] to be defined.
Thanks, Deveno. I get it now. Good examples. I forgot that Munkres uses the word "range" to mean "codomain", and I hadn't yet thought through all those consequences.

Quote Quote by Deveno View Post
consider f(x) = x2, g(x) = x+1.

note that [itex]g \circ f[/itex] makes sense for all real x, even though f never takes on any negative values.
(I guess you're implicity defining the codomain of this f to be R.)

Quote Quote by Deveno View Post
on the other hand, if f(x) = x+1, and g(x) = √x, THEN we have a problem, for it's not clear what value to give to [itex]g \circ f(-2)[/itex].
By Bishop & Goldberg's definition, there's no problem with the composite being ill-defined in this case; for them, the domain of [itex]g \circ f[/itex] is the preimage of the intersection of the image of f with the domain of g. So in this example, negative numbers aren't in the domain of [itex]g \circ f[/itex]. Munkres' definition appears similar: "Formally [itex]g \circ f : A \rightarrow C[/itex] is the function whose rule is

[tex]\left \{ (a,c) | \text{For some }b \in B \text{, f(a)=b} \text{ and } g(b)=c \right \},[/tex]

except that he requires the domain of the composite, [itex]g \circ f[/itex], to equal the domain of the inner component, f. So, using his definition, and assuming all these functions are real-valued, the composition of a pair of functions with the rules of assignment you give in your "on the other hand" paragraph would not be defined unless the codomain of f was a subset of the positive reals.

Rereading Munkres more carefully, I see it is true he's defined composition in a way that specifiers that the codomain of f is equal to the domain of g, but now that I realize Munkres is not making any stipulation about the image of f, it seems to me that it wouldn't make much difference if this requirement was omitted from the definition, as Bishop & Goldberg do.

Quote Quote by Deveno View Post
because of this, [itex]g \circ f[/itex] might be injective, even if g isn't:
"Because of this" = "Because of the problem"? I don't quite follow that. But nice example. Makes me think I should play around more trying to come up with simple examples to test the reasobableness of things I'm trying to prove.

Quote Quote by Deveno View Post
let A = {a,b,c}, B = {w,x,y,z} C = {s,t,u} with f:A→B, g:B→C

f(a) = x
f(b) = y
f(c) = z

g(w) = s <--
g(x) = s <--g not injective
g(y) = t
g(z) = u

then gof(a) = g(f(a)) = g(x) = s
gof(b) = g(f(b)) = g(y) = t
gof(c) = g(f(c)) = g(z) = u

gof is clearly injective, but g is not. why? because im(f) < dom(g).

a similar situation holds when gof is surjective, g has to be surjective, but f need not be.
Okay, I see, so if [itex]g\circ f[/itex] is surjective, then g must be, otherwise not every element in C would be "hit" by the composite function. And if f is not surjective, then it doesn't matter; it's still possible for every element in C to be mapped to by the composite from some element in A. Thanks again for your help!


Register to reply

Related Discussions
Lim f'(x)=0 implies lim f(x)/x = 0 Calculus & Beyond Homework 2
Logic: (p implies q) or (q implies r) Calculus & Beyond Homework 4
U(x,0)=0 implies u_x (x,0)=0 ? Calculus & Beyond Homework 3
F'(z)=0 implies f is not 1-1 near z Calculus 4
Show that ((p implies q) and (q implies r)) implies (p implies r) is a tautology Calculus & Beyond Homework 2