Saturday 29 November 2014

Proofs

How do we communicate truth?

We sometimes need to convince other people that what we know or understand is true. How do we do that? We need proof.

Direct proof

A direct proof essentially show that there is a link between an assumption and the result. To form this link, we can use previously proven statements and axioms (e.g. DeMorgan's Law). Each assumption about a claim has its own scope. For instance, in the claim that for all elements of x in set D, x with the property 'P' implies x with property 'Q', we assume x is an element of D, whereby no x is a none-D, and P(x) is assumed true, then P(x) implies Q(x).

Axiomatic Method

Before diving straight into proofs, we should look back to the axiomatic method, a method of establishing truths in mathematics invented by Euclid in C. 300 BCE. He began with simple assumptions that are seemingly undeniable from logic, which are called axioms, and proved many propositions from those assumptions. His proofs consisted of a sequence of logical deductions from previous axioms and previously-proved statements, which finally concludes with the proposition in question. Theorems are important propositions proved through this deductive process.

Lets go back to the direct proofs. A direct proof can prove implications, which are in the form "if P, then Q". One way to prove an implication is to first assume P is true, then show Q is somehow linked to this assumption. Finding this link is not trivial. To visualize this, a Venn Diagram can be helpful. For example, to prove P(x) implies Q(x), we can look for results that P(x) implies, and results that imply Q(x). Now, we can visualize the results that P(x) implies as sets that contain P, while the results that imply Q(x) are contained by Q. Now all we need is to find a patch of containment from to Q.

One thing to note is that before a structured proof can be written, one should first do some scratch-work while one figures out the logical links. Just keep in mind to keep the scratch-work separate from the final proof.

No comments:

Post a Comment