Proving a Theorem: Validity & Methodology

[StephenPrivitera]

In general, what is the conventional method of proving a theorem? What makes a proof valid? I hope that question is clear enough.

 

[MathematicalPhysicist]

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/

 

[HallsofIvy]

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.

 

[marcus]

Originally posted by loop quantum gravity
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/

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

 

[MathematicalPhysicist]

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 isn't this definition paradoxical?
here is the link:http://www.wikipedia.org/wiki/Metamathematics

 

[StephenPrivitera]

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

 

[lethe]

Originally posted by loop quantum gravity

now isn't this definition paradoxical?

no. why would you say it is paradoxical?

 

[lethe]

Originally posted by StephenPrivitera

Prove that addition is not distributive over multiplication (domain=natural numbers).

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.

 

[lethe]

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.

 

[StephenPrivitera]

Originally posted by lethe
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.

Well that was much too easy!

 

[HallsofIvy]

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.

 

[MathematicalPhysicist]

Originally posted by lethe
no. why would you say it is paradoxical?

never mind my idea was a wrong one.

 

[arcnets]

Originally posted by StephenPrivitera
In general, what is the conventional method of proving a theorem? What makes a proof valid? I hope that question is clear enough.

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?

 

[drnihili]

Don't forget universal proof. Prove an arbitrary instance of a theorem and from that it follows that all cases are true.

 

[StephenPrivitera]

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?

 

[Hurkyl]

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.