1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Validity of proof method - error in book?

  1. Feb 12, 2012 #1
    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?
  2. jcsd
  3. Feb 12, 2012 #2
    Re: Validity of proof method -- error in book?

    I cant 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.
  4. Feb 12, 2012 #3
    Re: Validity of proof method -- error in book?

    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.
  5. Feb 12, 2012 #4
    Re: Validity of proof method -- error in book?

    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 doesnt need to make a contradiction more than once.
  6. Feb 12, 2012 #5
    Re: Validity of proof method -- error in book?

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

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

    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.

    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?
  7. Feb 12, 2012 #6


    User Avatar
    Science Advisor

    Re: Validity of proof method -- error in book?

    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.
  8. Feb 13, 2012 #7
    Re: Validity of proof method -- error in book?

    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,

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook