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

[Rasalhague]

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 $g\circ f$ is injective, what can you say about the injectivity of f and g?" Problem 1.2.4(e) asks, "If $g\circ f$ is surjective, what can you say about the surjectivity of f and g?"

I concluded $g\circ f$ injective implies that both f and g are injective, and that $g\circ f$ 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 $f:A\rightarrow B$ and $g:B\rightarrow C$. According to Munkres' definition of function composition, $g\circ f$ is only defined if f is surjective; so clearly $g\circ f$ surjective implies f is surjective.

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

$$f[a_1]=f[a_2]$$

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

$$\Rightarrow a_1 = a_2,$$

so f is 1-1 too.

And if $g[b_1]=g[b_2]$, then

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

and, for this $a_1,a_2$,

$$(g\circ f)[a_1]=(g\circ f)[a_2]$$

$$\Rightarrow a_1 = a_2$$

$$\Rightarrow b_1 = b_2,$$

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 = c; so g is surjective too.

 

[Rasalhague]

According to Munkres' definition of function composition, $g\circ f$ is only defined if f is surjective; so clearly $g\circ f$ 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 $g \circ f$ 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 $g\circ f$ 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. Specifically, he defines the rule of a function as the set of pairs of (in this case) the form (a,c) = (a,$g\circ f$[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]

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 $g\circ f$ is injective, what can you say about the injectivity of f and g?" Problem 1.2.4(e) asks, "If $g\circ f$ is surjective, what can you say about the surjectivity of f and g?"

I concluded $g\circ f$ injective implies that both f and g are injective, and that $g\circ f$ 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 $f:A\rightarrow B$ and $g:B\rightarrow C$. According to Munkres' definition of function composition, $g\circ f$ is only defined if f is surjective; so clearly $g\circ f$ surjective implies f is surjective.

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

$$f[a_1]=f[a_2]$$

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

$$\Rightarrow a_1 = a_2,$$

so f is 1-1 too.

And if $g[b_1]=g[b_2]$, then

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

and, for this $a_1,a_2$,

$$(g\circ f)[a_1]=(g\circ f)[a_2]$$

$$\Rightarrow a_1 = a_2$$

$$\Rightarrow b_1 = b_2,$$

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 = c; so g is surjective too.

f need not be surjective for $g \circ f$ to be defined.

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

note that $g \circ f$ 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 $g \circ f(-2)$.

because of this, $g \circ f$ 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]

f need not be surjective for $g \circ f$ 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.

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

note that $g \circ f$ 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.)

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 $g \circ f(-2)$.

By Bishop & Goldberg's definition, there's no problem with the composite being ill-defined in this case; for them, the domain of $g \circ f$ 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 $g \circ f$. Munkres' definition appears similar: "Formally $g \circ f : A \rightarrow C$ is the function whose rule is

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

except that he requires the domain of the composite, $g \circ f$, 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.

because of this, $g \circ f$ 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.

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 $g\circ f$ 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!

 

[blue_raver22]

For Problem 1.2.5(a), the wording is slightly misleading. The statement should be "If f has a left inverse, then f is injective; and if f has a right inverse, then f is bijective." This is because a left inverse of f is a function g:B\rightarrow A such that g\circ f = id_A, and a right inverse is a function h:B\rightarrow A such that f\circ h = id_B. In both cases, f is bijective, which implies that it is both injective and surjective. So your conclusion is correct, but the wording of the problem may have caused confusion.