Notices
Results 1 to 50 of 50

Thread: pure mathematics, proofs

  1. #1 pure mathematics, proofs 
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Hi there,

    I've started reading the book, "A concise introduction to pure mathematics", which I'm finding a great read so far. I'm on the first chapter on sets and proofs, and have come across the following example:

    Prove that

    The author goes on to give a non-proof:







    Why is this a non-proof? I'm not sure I understand fully? He says that we have shown that if P is the statement we want to prove, and Q is the statement that 48 < 49, then P implies Q; but this tells us nothing about the truth or otherwise of P.

    Instead, he says the correct way to prove the above is method by contradiction, as follows:







    which is obviously a contradiction, but I don't understand why the first method (the non-proof) isn't actually a proof itself?

    Hope someone can help explain this to me, thanks!


    Reply With Quote  
     

  2.  
     

  3. #2 Re: pure mathematics, proofs 
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by rgba
    Hi there,

    I've started reading the book, "A concise introduction to pure mathematics", which I'm finding a great read so far. I'm on the first chapter on sets and proofs, and have come across the following example:

    Prove that

    The author goes on to give a non-proof:







    Why is this a non-proof? I'm not sure I understand fully? He says that we have shown that if P is the statement we want to prove, and Q is the statement that 48 < 49, then P implies Q; but this tells us nothing about the truth or otherwise of P.

    Instead, he says the correct way to prove the above is method by contradiction, as follows:







    which is obviously a contradiction, but I don't understand why the first method (the non-proof) isn't actually a proof itself?

    Hope someone can help explain this to me, thanks!
    The only thing wrong with the statements that you have related is that the second train of logic is not THE correct way to construct the proof, but is A correct way to prove the assertion.

    I cannot think of any way to be more clear than was the author as to the fallacy in the first argument. You need to consider what he said and understand it. He is making a very fundamental point of logic, in terms of what is assumed to be true and what can be concluded from that assumption. You must either come to terms with what he has said and understand it, internalize that logic, or I suggest that you take up some study other than abstract mathematics.

    You perhaps need to study the book and not treat it as "a great read". Mathematics books are not novels. It is quite common, particularly in the early stages of study, for a page or two to require an hour or more of study to truly understand what is going on.


    Reply With Quote  
     

  4. #3  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    You cannot assume that which you are trying to prove in the attempt to prove it. Can you see why?
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  5. #4  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Thanks for the replies guys!

    Quote Originally Posted by DrRocket
    in terms of what is assumed to be true and what can be concluded from that assumption.
    From the above quote, this is what came out most; "what can be concluded from that assumption", I'm assuming we are refering to the statement , we have an assumption (that is, 48 is less than 49), but we cannot conclude anything from it (in terms of the original statement we are trying to prove ), is that right?

    Quote Originally Posted by river_rat
    You cannot assume that which you are trying to prove in the attempt to prove it. Can you see why?
    Hopefully I'm understanding what you are saying here, we cannot make assumptions about a statement we are trying to prove during the process of proving it, is that what you are saying?

    So, from my understanding, we have the following statements:




    and from above, we can deduce that

    So, (hopefully I'm getting this right), we know that P implies (could we say equals in this case?) Q, so we have only proved the value of statement P, is that right?

    In the proof by contradiction, we have no implication, therefore we have a proof.

    Hoepfully I'm on the right track?
    Reply With Quote  
     

  6. #5  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Basically:

    In the first statement, , we come up with the implication that the result is , so we have only proved that is equal to ; we have not actually proved the truth/falsity of the first statement.

    With the proof by contradiction, we have , from which we deduce that , obviously false, so we are not actually proving anything, we are just disproving the truth\falsity, so therefore we have a proof.

    Hopefully I'm getting there?
    Reply With Quote  
     

  7. #6  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    Starting with a statement you don’t know is true or not and deducing from it a true statement does not prove anything.

    However, you can start with a statement known to be true, and deduce what you want to prove from it by logical steps.

    So here is another way you can do it. You can start with what which you know to be true, and work backwards.

    _____









    Reply With Quote  
     

  8. #7  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Hi JaneBennet,

    Thanks for your reply!

    Quote Originally Posted by JaneBennet
    Starting with a statement you don’t know is true or not and deducing from it a true statement does not prove anything.
    Ah, that's obviously where I was getting lost! It makes sense now, we don't know whether the statement is true or false, so if we deduce a true statement from it, we still don't know anything about the original statement. Only until we disprove this, i.e. deduce a false statement, can we make assumptions about the statment itself.

    So all-in-all, we can only prove a statement if we know it to be true itself?

    Am I on the right track now?

    EDIT: we need solid facts on which to derive proofs, correct?
    Reply With Quote  
     

  9. #8  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Reading the exercises of the same chapter:

    Which of the arguments are valid?
    (a) I eat chocolate if I am depressed. I am not depressed. Therefore I am not eating chocolate.

    The statement I eat chocolate if I am depressed is a fact that if I am depressed I will be eating chocolate. However, it says nothing about the condition in which I am not depressed so the statement Therefore I am not eating chocolate is false.

    (b) I eat chocolate only if I am depressed. I am not depressed. Therefore I am not eating chocolate.

    I eat chocolate only if I am depressed is a solid fact that I only eat chocolate if I am depressed so the final statement is therefore true.

    So we have to have solid facts on which to derive proofs. Without facts we cannot make assumptions. Correct?
    Reply With Quote  
     

  10. #9  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    Yes, your answers to both (a) and (b) are correct. Just a minor point:

    Quote Originally Posted by rgba
    Therefore I am not eating chocolate is false.
    What you mean is that the argument is not valid, not that the statement is false. The statement can still be true – you can still be happy and eating chocolates. It is the deductive steps leading to that conclusion that are faulty.
    Reply With Quote  
     

  11. #10  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Yeah, that's what I meant! True! Thanks!
    Reply With Quote  
     

  12. #11  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    I've been working through the excercises, currently stuck on a particular exercise that I'm struggling to solve. Since there are no answers included in the book, nor on the website, I was hoping I could post my answers here so anyone could tell me if any are wrong. I know it's alot to ask, but hoepfully some of you don't mind helping me out!

    Thanks!

    Herewith questions, and my answers. Not complete, will post the rest when I'm finished:

    1. Let be the set . Which of the following statements are true and which are false?
    a. true
    b. true
    c. true
    d. false
    e. false
    f. true
    g. false
    h. false
    i. true

    2. Let be the following sets:






    a. Which pair of these sets has the property that neither is contained in the other?
    Sets and

    b. You are given that is one of the sets but you do not know which one. You are also given that and . What can you deduce about ?
    contains the element 1. . cannot be as . Therefore we can deduce that can be either one of or .

    3. Which of the following arguments are valid? For the valid ones, write down the argument symbolically.

    a. I eat chocolate if I am depressed. I am not depressed. Therefore I am not eating chocolate.
    This is not a valid argument as the first statement says nothing about the cases in which I am not depressed.

    b. I eat chocolate only if I am depressed. I am not depressed. Therefore I am not eating chocolate.
    This is valid as the first statement has exhausted all the possibilities, that is, I only eat chocolate if I am depressed
    I eat chocolate I am depressed
    CHECK: This is not a two-way implication, as the statement does not say that I always eat chocolate when depressed, is that correct?

    c. If a movie is not worth seeing then it was not made in England. A movie is worth seeing only if critic Ivor Smallbrain reviews it. The movie The Good, the Bad and the Mathematician was not reviewed by Ivor Smallbrain. Therefore, The Good, the Bad and the Mathematician was not made in England.


    Propose the following statements:
    W = movie is worth seeing
    E = movie was made in England
    C = movie was reviewed by Ivor Smallbrain

    We can then form the following implications:




    I'm lost in how to construct the proof using statements, hope you can help me with proper construction of statments to conclude the statement.

    BUT, I can tell that since a movie is only good if Ivor Smallbrain reviews it, the movie is not good. However, the statement a movie is not worth seeing then it was not made in England does not exhaust all the possibilities, so we have an invalid argument.


    4. and are two statements. Which of the following statements about and implies one or more of the other statements?
    a. Either is true or is true.
    answer:



    b.
    answer:


    c.
    answer:


    d.
    answer:


    e.
    answer:


    5. Which of the following statements are true, and which are false?
    a. only if
    false, roots are {3,-1}

    b. only if
    false, roots are {3,-1}

    c. If then
    true, 3 is one of the roots

    d. For integers and , is a square only if both and are squares.
    true

    e. For integers and , is a square if both and are squares.
    true
    Reply With Quote  
     

  13. #12  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Another shot at 3c.


    Propose the following statements:

    W = movie is worth seeing
    E = movie was made in England
    C = Ivor Smallbrain reviews movie


    We then have the following implications:





    Thus, we can deduce that the movie was not made in England by the following implication:



    Reply With Quote  
     

  14. #13  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    There are a lot of exercises there, so I’ll look at the questions one by one.

    1. This is what you actually wrote

    Quote Originally Posted by rgba
    You had though my instinct tells me it might actually be just . Are you sure it’s correct? :?

    For now, I’ll just assume that it is as you have typed: .

    Your answers to (c), (d), (f) and (g) are incorrect; the rest are correct.

    Remember:




    etc
    Reply With Quote  
     

  15. #14  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Hi JaneBennet,

    Thanks for the reply!

    Yeah, that's how the set was presented in the text, no typos there.

    Cool, got it now, thanks!

    Corrections:

    c. false as and - to be true it would have to be - is that correct?

    d. true as and

    f. false as

    g. true as

    I was missing the concept of the subset entirely; I guess the notation was confusing me a little! Makes much more sense now!
    Reply With Quote  
     

  16. #15  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    Yes, you got it now. For (c) though, you could just say



    For #2, you missed another pair of sets in (a). Your answer to (b) is correct. 8)

    For #3. I’ll have a look at it in detail in a moment. I’ll just point out now that “only if” means (it’s not a two-way implication): “I eat chocolates only if I am depressed” means “if I eat chocolates, then I am depressed”.
    Reply With Quote  
     

  17. #16  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Cool

    As for 2a, I'm not quite sure why my answer is incorrect. I assumed that:

    gives us in the range .

    gives us in the range .

    gives us only one solution for , that is, .

    gives us only being .

    So, thus, since we know and both contain and , I assumed that and satisfied the argument as neither is contained within the other?

    Unless you mean to say that for it is equivalent to the empty set as it has as it's only element?

    I understand what you are saying about the two-way implication.

    i.e.



    but not



    And I just want to say thanks! Your great help is greatly appreciated!
    Reply With Quote  
     

  18. #17  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    6. Write down careful proofs of the following statements:

    a. .
    answer:




    which is a contradiction, therefore the statement is true.


    b. If is an integer such that is even, then is even.
    We assume to be equal to , for some integer , an even number.

    Thus;






    as is an even number (for some integer ), we can then conclude that the argument is true.


    c. If for some integer , then is a multiple of .
    I'm really struggling with this one I have put together the following:

    FACTS:

    and , for some .
    If is not a multiple of , then we know that if we take the quotient of and , we will get remainders of .

    I've tried getting ideas for proof by contradiction, but I guess I just don't understand enough to derive a proof for the above. Hope someone can help!


    I'm not going to try and attempt the next questions, I have had a look at them, and I don't feel confident enough, not until I understand how to prove 6c.

    Looking forward to a response!
    Reply With Quote  
     

  19. #18  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    I haven't looked closely at the rest, but you need to be careful in 6a. When you square two sides of an equation, you have to square everything on both sides at once. If that's hard to keep up with, you can try putting parenthesis around each side first.
    Reply With Quote  
     

  20. #19  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    Quote Originally Posted by rgba

    b. If is an integer such that is even, then is even.

    We assume to be equal to , for some integer , an even number.
    This seems to be circular. By assuming you are already asserting that is even. which is what you want to prove

    c. If for some integer , then is a multiple of .
    I see a coupla ways to show this; from context it looks like you are being asked for a parity argument. That is, the third power preserves parity; if is even, then so is , and if is odd, then so is (can you show this?).

    Then it follows that must be even (show), that is is a multiple of , or to put it another way, Your task is now to show that also, since if then
    Reply With Quote  
     

  21. #20  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    Quote Originally Posted by Guitarist
    c. If for some integer , then is a multiple of .
    I see a coupla ways to show this; from context it looks like you are being asked for a parity argument. That is, the third power preserves parity; if is even, then so is , and if is odd, then so is (can you show this?).

    Then it follows that must be even (show), that is is a multiple of , or to put it another way, Your task is now to show that also, since if then
    Not like that. Factorize it.



    Thus is a product of three consecutive integers; any sequence of three consecutive integers must contain a multiple of 3 and at least one multiple of 2.
    Reply With Quote  
     

  22. #21  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Hey guys, thanks for the replies!

    MagiMaster: True, I'll be more careful next time! Should have put it this

    way - I know I don't need to

    put in, but it adds clarity I guess...

    Guitarist: Thanks! Will have another shot at 6b and try 6c!

    JaneBennet: Cool, that looks pretty neat! :P

    6b. We know that is an even number, so take for some integer . Then we have:




    which is an even number. Hopefully I got it correct now?


    As for 6c, I'm gonna have a look at your posts, think about it, then I'll post back!

    I seem to be having a lot of trouble with logic itself, it's kind of hard for me to feel comfortable with! Guess I need more practise!

    Thanks guys!

    EDIT: added 6c.

    Ok, heres my attempt:


    By Guitarists suggestion:

    Assume is even, then we have:

    for some integer .
    , a multiple of 2, so is even.
    , again a multiple of 2, so is even.

    Assume is odd, then we have:
    for some integer (as added to an even number is odd).
    , which is added to an

    even number, so is odd.
    , which is more than an even number, so is odd.


    Thus we have established that is even if is even, and odd if otherwise.

    So, then, since is a multiple of (i.e. an even multiple), we then know that is even, as the following proof shows:

    Let be and let be for some integers and . We use as a multiple as we know that is a multiple of .

    We then have:

    , which is an even number. i.e .

    Therefore we know that is a multiple of . Hopefully got that right?

    By JaneBennets suggestion:



    Integers are consecutive, , ah, yeah, makes total sense!

    So we conclude that since we have three consecutive integer factors, has to be a multiple of 6.


    The way you guys have solved the proofs isn't even close to how I was thinking. I mean, how do you come up with very obvious solutions to the proof? Like Guitarists parity and JaneBennets consecutive integers idea? All of those make complete sense, but the idea of using them for proofs just seems very hard to grasp intuitively :/
    Reply With Quote  
     

  23. #22  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    Actually, I think you did pretty well. There were a coupla gaps in your argument (plus a very worryingly inappropriate "since" - can you spot it?), but you put Jane's and my suggestions together pretty well.

    As to how to dream up proofs, the trite answer is practice, which I am pleased to see you are doing. The hardest part of any exercise is finding a way in, though you may be reasonably sure that, usually, you will never be asked to prove something that you have not already been given the tools for (Aaargh - grammar!). It is also my belief, not universally shared, that, while it's always pleasing to get the right answer, we learn more by trying than by succeeding.

    Let me also say say that I think your approach to asking for help on this forum could serve as a model for all others seeking help. Keep plugging away!
    Reply With Quote  
     

  24. #23  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    Okay, now I have time to look at some of your earlier questions.

    #2(a)
    You missed out the pair and . −1 is in but not in , while 2 is in but not in .

    #3(c)
    The argument is valid.

    #4
    You’ve done it all wrong. You are given these

    (a) Either is true or is true
    (b)
    (c)
    (d)
    (e)

    and you’re supposed to say, e.g. (a) (b) or (b) (c), etc.

    The answers are:
    (a) (d)
    (a) (e)
    (d) (a)
    (d) (e)
    (e) (a)
    (e) (d)

    ((a), (d) and (e) are in fact logically equivalent statements.)

    #5
    (a) is true (remember: “only if” means ).

    (c) is false.

    (d) is false (e.g. )

    Remember: “X only if Y” means “if X, then Y”! You seem to have trouble remembering this.

    I’ll look at the rest later.
    Reply With Quote  
     

  25. #24  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Hey people!

    Guitarist: Ah, I get it, the "since" part is not correct as we are attempting to prove that is a multiple of , so we cannot say, "since", perhaps "as is apparently a multiple of " would be more appropriate? Yeah, I totally agree that the process of trying is often more benficial than the "gotchas!". I'm lucky to be able to ask questions on a forum with lots of extremely helpful people, it's encouraging!

    JaneBennet: Thanks!

    2a. Ah yes, silly me! Should have checked more carefully! So we then have two pairs of sets not contained within the other.

    3c. Cool, if you look at my post #12, I had reworked 3c, and hopefully the implications I have laid out are correct? That also means that the argument is valid.

    4. I'm a little confused, have to run out and do something quickly then I'll be back to look at this and the rest

    Thanks guys for all the great help! Greatly appreciated!

    Be back just now!



    EDIT:

    Back!

    Ah, on 4, I understand now! I obviously misunderstood the question. In this case, (b) implies none of the others, as with (c). (d) implies (a) and (e), and so on, ok, no problem, got it now!

    Ah yeah, I see here. 5a. , so the statement is true, as we know is concrete.

    5c. , in this case the implying statement says so and so, but the implied statement doesn't say really say anything about the implying statment, so in this case it is false, as the solution set is .

    5d. Yes! True, so obvious... invalidates this...

    Thanks!
    Reply With Quote  
     

  26. #25  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Next question:

    7. Disprove the following statements:
    a. if and are positive integers, then is always divisible by .

    I would assume that proof by contradiction would be the way to go, as proof by counterexample seems not to work. So then, we need to prove that is not divisible by .

    As usual, I'm gonna have to think about this for a lot longer!!! Wow, this is pretty exhausting work, but it's really satisfying!

    EDIT: can I use proof by induction for 7a?

    b. every positive integer is the sum of three squares (the squares being 0,1,4,9,16,etc.).

    Proof by counterexample would work here, as we can produce the counterexample , i.e. there are no three squares that can be summed to produce .

    As for 7a. I'm still struggling. It's evident I'm not good at this
    Reply With Quote  
     

  27. #26  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Your methodology for 7b will work for 7a as well, and, expect for rare cases (see Cantor), for most other disproofs.
    Reply With Quote  
     

  28. #27  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Hey MagiMaster, cool, thanks! Guess I then have to find a counterexample! Will do that now :P
    Reply With Quote  
     

  29. #28  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    Quote Originally Posted by rgba
    I would assume that proof by contradiction would be the way to go, as proof by counterexample seems not to work. So then, we need to prove that is not divisible by .
    For a counterexample try n = 2 and k a number slightly larger then that

    You need to be careful here though, the negation of a "for all statement" is a "there exists" statement. Which brings me to your next question

    EDIT: can I use proof by induction for 7a?
    Induction is only useful when you are dealing with "for all" type statements (when you see a statement like "prove X for all natural numbers" induction should be a hammer near by).
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  30. #29  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Thanks for the reply river_rat!

    I'm confused by this:

    Quote Originally Posted by river_rat
    For a counterexample try n = 2 and k a number slightly larger then that
    By slightly larger, something like ? cause that doesn't work: take which is divisible by

    If you meant something like , then I'm really confused because the question says and must be integers???

    Or have I got everything upside down?!

    Thanks for clarifying the use of induction, it does actually make sense!
    Reply With Quote  
     

  31. #30  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    OK, here's a massive hint. In return for which, I will ask a supplementary.

    Try . Write this another way to find out what is

    If this turns out to be a counterexample for some , is this true for any ?

    Why (not)? Another hint: divides implies for some integer P.S It's slightly tricky, so take care
    Reply With Quote  
     

  32. #31  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Hey Guitarist, thanks for the reply!

    Uh, sorry, I'm really confused:

    Quote Originally Posted by Guitarist
    Try . Write this another way to find out what is k
    Did you by any chance mean ?

    I'm really confused, I don't think I understand what you are trying to say?

    Perhaps I have to read up on number theory or something like that? Because I'm simply not getting any connections to the numbers, I look at them, I see this and that, but I just can't build a connection! It's a little depressing, but hey, I don't have low self-esteem! I'm just a little sad that I struggle to work out proofs for things like:

    If for some integer , then is a multiple of .

    I would think that I would be able to see a lot easier, I mean I know I'm not stupid, but maybe I'm not intelligent in a mathematical sense?

    That's not to say I don't appreciate all the help I've gotten here, it is much appreciated! Maybe I'm just missing some general (in a mathematical sense) knowledge?
    Reply With Quote  
     

  33. #32  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    Quote Originally Posted by rgba
    Did you by any chance mean ?
    Nope. Look up the laws of exponents. Ah well, rather don't, I'll tell you (though by your problem set, you really ought to know). .

    What if ? Say it out loud!

    Then show us what you get when in your exercise.
    Reply With Quote  
     

  34. #33  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Hey Guitarist,

    Oh ok, no it's cool, I know the exponent laws, I was just pretty confused!

    Well
    Quote Originally Posted by Guitarist
    Try . Write this another way to find out what is
    would imply:



    So that would mean we have the following chain of implications:

    , so we can give a counterexample , as this is not an integer?

    So for and equal to , we have proved the counterexample , so thus have disproved the theorem?

    I'm off to hide in the bushes! Sorry, I'm pretty sure I'm testing everyones patience, but honestly I'm really trying! I really am! And I'm pretty frustrated too
    Reply With Quote  
     

  35. #34  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    Eeek! Look, You seem to be over-thinking the hints you were given.

    , agreed? Then , agreed? So does the exponent divide ?

    If not (as I believe) you have that, for and then the claim that divides is not true in general.
    Reply With Quote  
     

  36. #35  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Generally, the first step in attempting to disprove something like this is to just plug in small numbers until you get tired of it. In this case, that should be enough to find a counterexample (such as Guitarist's).
    Reply With Quote  
     

  37. #36  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    Quote Originally Posted by rgba
    Thanks for the reply river_rat!

    I'm confused by this:

    Quote Originally Posted by river_rat
    For a counterexample try n = 2 and k a number slightly larger then that
    By slightly larger, something like ? cause that doesn't work: take which is divisible by

    If you meant something like , then I'm really confused because the question says and must be integers???

    Or have I got everything upside down?!

    Thanks for clarifying the use of induction, it does actually make sense!
    I think you must be a bat (you're so upside down). Ok enough of that lol

    Try n = 2 and k = 4...

    which is not divisible by 4
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  38. #37  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Hey guys, thanks for the replies!

    Guitarist: Ah man, that was all so simple!!! :? What was I missing there??!?!?! Man, I mean, all I needed was for the case where ! Lol, why, I must have been so confused for some reason! Cool, so the counterexample is then , so therefore we have a disproof as is not divisible by . You must be relieved to hear that your point finally hit home

    MagiMaster: Lol, alright, noted

    river_rat: Maybe a cross between a bat and a sloth Yup, got it now!

    Phew! Wow, thanks guys! I know I have been a major pain, wow, that was so simple, what had me so confused???? Lol!
    Reply With Quote  
     

  39. #38  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    OK, since you were more-or-less handed that on a plate, I am going to foreclose on your debt!

    For we see that doesn't divide . Is this true for any positive ?

    Use the following notation: means divides ;

    means doesn't divide ;

    Note that , and .

    This is slightly tricky, so don't lose sleep over it. Good luck.
    Reply With Quote  
     

  40. #39  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Actually, that last point should be IIRC, since if , then you'd have divisibility again.
    Reply With Quote  
     

  41. #40  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    Yes, you're right - "my bad", as they so inelegantly say.

    In fact, actually one only requires that , but when this introduces an irrelevant complication.

    So let's introduce our young friend to the following piece of math gobbledygook:

    "Without loss of generality", abbreviated WLOG.

    Since we must have that we may assume WLOG that
    Reply With Quote  
     

  42. #41  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Ok Guitarist, I'll have a look at that starting tomorrow! Should be a challenge

    Cheerio!
    Reply With Quote  
     

  43. #42  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    I'm really going to get around to doing this, but had so much on my plate today, just got a chance to sit down, but not for long... Will start tomorrow, should have time then

    Cheerio!
    Reply With Quote  
     

  44. #43  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    Right, now I have time again.

    6a.
    Quote Originally Posted by rgba

    Nooo!!

    The correct steps should be





    Then you’ll need to square again; in the end you should arrive at the contradiction .

    Also, when you square both sides of an inequality, make sure that both sides are nonnegative. In this case, both and 1 are positive, so everything is fine – but it is good practice to check just to make sure.

    6b.
    Use method of contradiction. Assume that is odd, and show that cannot then be even.

    6c.
    Quote Originally Posted by rgba
    By JaneBennets suggestion:



    Integers are consecutive, , ah, yeah, makes total sense!

    So we conclude that since we have three consecutive integer factors, has to be a multiple of 6.
    I think you need to do some more work there. You are almost there, but not quite.

    7a and 7b should be easy. You are not trying to prove the statements but to disprove them. So just look for counterexamples.
    Reply With Quote  
     

  45. #44  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    Quote Originally Posted by Guitarist
    For we see that doesn't divide . Is this true for any positive ?
    I am still waiting - any one? (come on forum members, get in gear!)
    Reply With Quote  
     

  46. #45  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    Sorry, I didn’t see your question earlier.

    will divide every integer, including 0.
    Reply With Quote  
     

  47. #46  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Hi there,

    Been a little demotivated, had a long week so just spent the weekend taking off...

    Ok, back to it now!

    Thanks for the reply JaneBennet!

    6a. Ah bugger, I didn't complete the equation hey! Ok, here goes:











    I'm getting and not ???

    Quote Originally Posted by JaneBennet
    Also, when you square both sides of an inequality, make sure that both sides are nonnegative. In this case, both and 1 are positive, so everything is fine – but it is good practice to check just to make sure.
    Cool, got that. Thanks for the reminder! One could also reverse the sign of the equality accordingly.

    Quote Originally Posted by JaneBennet
    6b.
    Use method of contradiction. Assume that is odd, and show that cannot then be even.
    6b. If is an integer such that is even, then is even.

    Proof by contradiction:
    Assume that is odd. We then have:

    for some integer




    Thus we can see that is more than a multiple of , which is an odd number. This is a contradiction (as is said to be an even number).


    Quote Originally Posted by JaneBennet
    I think you need to do some more work there. You are almost there, but not quite.
    Ok, thanks for pointing that out. Will have another look!

    Quote Originally Posted by JaneBennet
    7a and 7b should be easy. You are not trying to prove the statements but to disprove them. So just look for counterexamples.
    Looks like it wasn't that easy for me But I'm trying!

    Quote Originally Posted by Guitarist
    I am still waiting - any one? (come on forum members, get in gear!)
    I'm gonna do this! I've just been pretty blue the last couple of days! Getting to it now!!!

    Cheerio!
    Reply With Quote  
     

  48. #47  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Ok, getting onto Guitarists problem first.

    For we see that doesn't divide . Is this true for any positive ?

    Notation:

    means divides
    means does not divide




    Oooook, starting...



    EDIT:

    Quote Originally Posted by JaneBennet
    Sorry, I didn’t see your question earlier.

    n=1 will divide every integer, including 0.
    Missed it...

    Sorry if you guys think I'm not really interested and wasting your time. It's really not like that, I'm really eager to learn - it's just hard when life gets in the way...

    Maybe I should be reading up on some specific stuff? Maybe logic? Any suggestions would be greatly appreciated!

    And hey, all the help has been greatly appreciated!
    Reply With Quote  
     

  49. #48  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Working on the next lot:

    8. For each of the following statements, form its negation, and either prove that the statement is true, or prove that its negation is true:

    a. such that is a prime number, is odd.

    negation is: such that is a prime number, is even.

    We can prove this by giving a counter example of , which is a prime number and is not odd.


    b. such that .

    negation is: such that .

    I have tried to solve this one by giving proof by counterexample, but have failed for all attempts up to . So I'm not really sure how to do this one??? It seems there is a more sophisticated way to do this one, that I'm obviously not aware of. I realise that in attempting any of the proofs, I immediately try to find a solution by proof by counterexample, which obviously shows that my ability to use the other methods of proof is very bad.


    c. such that .

    negation is: such that

    We can prove this with the single counterexample . i.e. there is no such that , since this implies:

    , not an integer.


    d. such that

    negation is: such that

    Proving the negation, using proof by contradiction:

    where

    which is a contradiction. I realise this doesn't really make sense, but I'm really struggling with the whole proof thing, I'm gonna look on the net for any resources on proofs and stuff, hopefully I can gain a better understanding...


    I can see that I'm really struggling with the proof methods, the easiest one for me would be proof by counterexample. Proof by contradiction, direct proofs and stuff like that aren't really ringing a bell for me I realise that the proofs depend alot on a solid understanding of logic/reasoning and general math. I guess I should try find more resources on logic/reasoning and proofs in general.
    Reply With Quote  
     

  50. #49  
    Forum Sophomore
    Join Date
    Jan 2008
    Posts
    130
    Found this free ebook: http://www.fecundity.com/codex/forallx.pdf

    Looks good, starting reading it now...

    But first I'm gonna read the Wikipedia page http://en.wikipedia.org/wiki/Mathematical_logic first...

    Any suggestions/comments would be great! Thanks!
    Reply With Quote  
     

  51. #50  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    You made a mistake here:

    Quote Originally Posted by rgba

    RHS in the first line is 1, not 0.

    Have no time to look at the rest at the moment; later perhaps.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •