Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Formal Proof

  1. Jul 31, 2003 #1
    In general, what is the conventional method of proving a theorem? What makes a proof valid? I hope that question is clear enough.
     
  2. jcsd
  3. Jul 31, 2003 #2
    i think (and i might be wrong) but a proof should be prooved by Deductive reasoning first you have the premesis which is the data you have in hand in order to proove the theorem after that you conclude from the data the conclusion (theorem).

    i hope the explanation is ok.

    edit:
    here is link to an article about the origins of proof there you might find the answer you were looking:http://plus.maths.org/issue7/features/proof1/
     
    Last edited: Jul 31, 2003
  4. Jul 31, 2003 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    A "proof" consists of statements starting from something you KNOW is true, either "given" or an axiom. Then produce a series of statements, each following from the previous statements by a logical connector ending with the conclusion.
     
  5. Jul 31, 2003 #4

    marcus

    User Avatar
    Science Advisor
    Gold Member
    2015 Award
    Dearly Missed

    that looks like a good answer
    "data" can mean "what is given" (going by the Latin)
    and in a mathematical proof the givens
    include the axioms of whatever theory is being developed
    IIRC most of modern math rests on the axioms of "set theory"
    because the fundamental objects are defined in terms of sets.

    a common practice is to refer to previously proven, widely known basic facts (which somebody earlier proved using the axioms of set theory) and this saves a lot of trouble.

    so one almost never sees the bare roots of the tree---in an actual proof one rarely sees the axioms of set theory invoked explicitly----instead the proof will depend on well-known facts which could if necessary be verified by going back to the most basic principles.

    edit: oops I see Halls of Ivy already said essentially the same thing, so this is redundant
     
    Last edited: Jul 31, 2003
  6. Jul 31, 2003 #5
    btw if we are already disscusing about proof in maths i have a question about metamaths.
    according to wikipedia: Metamathematics is mathematics used to study mathematics.
    now isnt this definition paradoxical?
    here is the link:http://www.wikipedia.org/wiki/Metamathematics
     
  7. Jul 31, 2003 #6
    For some reason, I thought there might be more rigid rules. I remember sophomore year when we learned trig identities we were required to show proofs. My teacher told us that you should only work on one side of the equation throughout the proof. You couldn't move items to the other side or manipulate the other side at all.

    This just an example of why I fret about formal rules.
    Prove that addition is not distributive over multiplication (domain=natural numbers).
    .............
    P(n): a+(b*n)=(a+b)*(a+n)

    P(1):
    a+(b*1)=(a+b)*(a+1)
    =((a+b)*a)+((a+b)*1) left.dis.mult.
    =((a*a)+(b*a))+(a+b) right.dis.mult., axiom k*1=k
    =(a+b)+((a*a)+(b*a)) comm.add.
    =(a+(b*1))+((a*a)+(b*a)) axiom k*1=k
    Clearly this can only be true if a=0 and zero is not a natural number. But how do I prove this (or is this proof enough)?

    I can go through and get a similar proof for P(k+1). I get,
    a+(b*(k+1))=a+(b*(k+1))+(a*(a+b+k))
    Again, only true if a=0. The difficult part of this proof is that I have to show that P(k+1) is false whenever P(k) is false.
    Anyway, I was wondering about the formalities of proof.

    EDIT: Actually, there is an axiom that might cover this problem. It states that exactly one of the following is true for all elements of N:
    a=b, a+x=b or a=b+y
    So since a=b, a cannot equal b+y
     
    Last edited: Jul 31, 2003
  8. Jul 31, 2003 #7
    no. why would you say it is paradoxical?
     
  9. Jul 31, 2003 #8
    to show that something is not true, it is sufficient, and usually easier, to simply provide a counterexample.

    if addition were distributive over multiplication, then 1+1*1 would equal (1+1)*(1+1). but 2 does not equal 4.

    that is all one needs to do.
     
  10. Jul 31, 2003 #9
    a logical system is a collection of axioms about objects in our system. each axiom takes the form P⇒Q. there is a set of allowed rules for combining statements of this form, which includes rules like ((P⇒Q)&(Q⇒R))⇒(P⇒R) which is just the transitive rule in logic.

    formally then, a proof of a statement is just a chain of logical implications, constructed using these rules, which starts with some of the axioms and ends at the statement to be proved.

    another common format for proof is to start with the axioms plus the negation of that which is to be proved, and construct a chain of implications, again using the rules of logic, that ends in the negation of an axiom. this is called proof by contradiction. it is very common.
     
  11. Jul 31, 2003 #10
    Well that was much too easy!
     
  12. Jul 31, 2003 #11

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yeah, it's really annoying when something is easy!



    By the way- proof of identities is often through what is called "synthetic proof"- you start with what you WANT to prove is true and algebraically reduce to something you KNOW is true.

    Of course, in a normal proof you are not allowed to ASSUME what you want to prove!

    The point of synthetic proof is that everything you do has to be REVERSIBLE. What you are really doing is deciding HOW to prove the identity. The true proof is gotten by now starting from the equation you know is true and working back. As long as you are sure everything yhou did is reversible, you don't have to actually do that.
     
  13. Aug 1, 2003 #12
    never mind my idea was a wrong one.
     
  14. Aug 1, 2003 #13
    Stephen, maybe it might help to make a list of common types of proofs. Here's some examples that I remember from scratch:

    - Direct proof.
    Using all the assumptions, you make implications until you arrive at the theorem.

    - Indirect proof (or proof by contradiction, see lethe's post).
    You assume that the theorem is false. From this you conclude that at least one of the assumptions must be false.

    - Proof by complete induction.
    You show that the theorem is true in one case, and using all the assumptions you show that from this follows that the theorem is true in all cases. This is a typical method for series and sums. (BTW, complete induction is, in fact, deduction. See loop quantum gravity's post).

    I think these are the most important types. Anybody know more?
     
    Last edited: Aug 1, 2003
  15. Aug 1, 2003 #14
    Don't forget universal proof. Prove an arbitrary instance of a theorem and from that it follows that all cases are true.
     
  16. Aug 2, 2003 #15
    How would you show uniqueness? I've seen some proofs that assume whatever we're talking about is not unique and show that this is a contradiction. Is this generally how this type of proof is done?
     
  17. Aug 2, 2003 #16

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That is one way. Another typical way is to prove any two objects satisfying the conditions are equal.

    For example, in a group, if y and z are both multiplicative inverses of x, then

    y x = 1
    (y x) z = 1 z
    y (x z) = z
    y 1 = z
    y = z

    so the multiplicative inverse of x is unique.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?