Validity of proof method - error in book?

[RespeckKnuckl]

Validity of proof method -- error in book?

Hey guys, I'm going through a book on category theory (not homework, not for a class) and I'm having trouble following a provided proof, I think there's something wrong with his reasoning. You don't necessarily need to know category theory to understand my question. Essentially he wants to prove that every monomophism in Set is an injective function. So he starts by proving that if f is an injective function, then it is a monomorphism (part 1). Then he tries to prove that if f is a monomorphism, it is an injective function (part 2). There is no problem with part 1, so I will just write part 2 here:

"...let f:B->C be a monomorphism. If f is not injective, then there are distinct elements b,b' in B for which f(b)=f(b'). Let A be the one-element set {a}, and let g:A->B map a to b while h:A->B maps a to b'. Then f(g(a)) = f(h(a)), contradicting the assumption that f is a monomorphism."

Something seems very wrong to me here. He wants to show that for all f: f being a monomorphism ( m(f) ) implies that f is injective ( i(f) ), and he goes about it with a proof by contradiction: it is impossible for m(f) and not i(f) to be true. But rather than showing it happens in call cases, he then defines a very specific example (the set A) and shows that in that particular case, m(f) and not i(f) lead to a contradiction. But from that you can't extrapolate that for ALL f, m(f) and not i(f) lead to contradictions. Am I missing something here? Or should I abandon this book and find a better one?

 

[Norwegian]

I can't tell you if the rest of the book is good, but the part that you refer to is, and you are missing that the author does indeed prove part two for any monomorphisms, and in the most standard way.

 

[RespeckKnuckl]

Thank you, but what I'm concerned with is the logical justification of his argument. Particularly the part where, as I described, he goes from making the argument about a particular case that leads to a contradiction, to saying that all such cases will cause that contradiction. I may be missing something simple, but if someone could actually find it and point it out it would help out tremendously.

 

[Norwegian]

He starts by saying "let f:B-->C be a(ny) monomorphism.." then proceeds to show that f is injective. QED. There is no argument about a particular case in there, and he doesn't need to make a contradiction more than once.

 

[RespeckKnuckl]

That's not entirely clear, and here's why. He starts by saying:

"let f:B->C be a monomorphism. If f is not injective, then there are distinct elements b,b' in B for which f(b)=f(b')."

So far, those properties are true of all such f that are monomorphisms that are not injective. Then:

Let A be the one-element set {a}, and let g:A->B map a to b while h:A->B maps a to b'.

Here he is no longer describing ALL monomorphisms that are not injective, but a single special case in which A is a one-element set and g and h map to different objects in B.

Then f(g(a)) = f(h(a)), contradicting the assumption that f is a monomorphism.

But if this conclusion relies on the additional assumption that A is a one-element set, then the proof only works for one-element sets. It is not clear to me why the argument still applies if A is not a one-element set. Where am I wrong?

 

[Deveno]

you are leaving out the definition of what a monomorphism IS. this is KEY.

a monomorphism is a morphism f:B→C such that:

fg = fh → g = h (where g,h: A→B).

in other words, f is left-cancellative.

now the above should hold for ANY morphisms g,h for which fg = fh.

now if f is not injective, then for SOME b ≠ b' in B, f(b) = f(b').

(otherwise, f would be injective).

now if we let g,h:{a}→B be the PARTICULAR morphisms g(a) = b, h(a) = b',

then fg:{a}→C is the mapping fg(a) = f(g(a)) = f(b), and

fh:{a}→C is the mapping fh(a) = f(h(a)) = f(b') = f(b).

and since f IS (by assumption) a monomorphism,

fg = fh, and so g = h.

but g does NOT equal h, because g = {a} x {b} = (a,b), while

h = {a} x {b'} = (a,b'), and these are distinct elements of AxB.

since assuming f a monomorphism but not injective leads to a contradiction,

we cannot have BOTH f a monomorphism AND f NOT injective,

so f a monomorphism implies f injective.

in logical terms this is:

(~(A&(~B)))<=> (A→B)

which is always true.

("it is never raining and not wet outside, therefore if it is raining outside, it must be wet outside").

when proving "not something", it is perfectly ok to give a single counter-example, which is why it does not affect the generality of the proof to use a specific g and h contrived for this situation.

 

[RespeckKnuckl]

Thanks! I see where I went wrong. For future googlers' sake, the book is "Basic Category Theory for Computer Scientists", and the part which confused me was that he used the wording "Let A be the one-element set". That wording does not make it clear that he is only proving a contradiction for that limited case, which as I mentioned, logically would not be sufficient. But as Deveno explained,

now if f is not injective, then for SOME b ≠ b' in B, f(b) = f(b').

This makes the obvious point I missed: A does not need to be a one-element set, it only needs to have at least one element. The consequence that follows from this and f's being injective is what we then use to complete the proof. It seems obvious to me now, but the wording made me focus on the logical justification behind the proof. Thanks guys.

I do believe I'll be switching books anyway though, since I think small omissions like this will bother me and make arguments harder to follow.