Elaborating on the idea of a proof

We refer to something as proof when there is no doubt that a claim given is supported with reason. The rationale for calling something a proof is worth further investigation, though. If two people talk about a proof, then even if person A has a proof, person B needs to thoroughly understand the reasoning to call it a proof.

The proof answers the question based on the axioms and definitions involved. For instance, the infinitude of primes could be proven with a sole definition of the prime number itself. As is, proof is always based on axioms and definitions. Both axioms and definitions might be disputable. It is trivial to show that an axiom might be disputable. When it comes to a definition, a definition is based on axioms, thus inheritance of being disputable.

If one person understands the proof, it means that it follows the line of argumentation (the path including the implications). Finding the path of argumentation by oneself might not be easy (for that person), though.

According to Wikipedia, a direct proof is one that takes advantage of a set of knowledge (including axioms) to deduce a new knowledge. Then, on the same level there are many different descriptions of proof types. Here I am going to tackle that.

For instance, a proof by induction is one where if something works for n, then if works for (n+1), then works for all integers, given that works for an initial condition. This is, as one might notice, a sequence of direct proofs, such an iteration of those n->n+1->n+2->n+3->… We could try to think about the exemplification of the aforementioned so that if something works for a first prime and prime p_n, then works for prime p_{n+1}.

Proof by transposition is also, again, yet another exemplification of the direct proof. In general, we again, even without the iteration involved, re-think the code coverage and try to prove the contrapositive statement. In case we face an obstace (i.e. we think that we would need, given one’s intelligence, deal with much data to tackle) with deducing on a set of direct knowledge, lets try to deduce from the opposite, in the same time minimizing the amount of data to grasp. As mentioned, again a proof based on a knowledge set.

Proof by contradiction is again just direct deduction, but with assumption of a certain element. Given the assumption, we deduce directly and find a cul-de-sac, thus such a way cannot exist, thus the very assumption cannot be true. Again, a way to minimize the amount of data via the assumption and contradictions. Here, we are not looking for additional knowledge ourselves, but just try to conjecture something and find a contradiction with axioms and current knowledge, resulting in minimizing the code coverage.

Proof by contruction is again one that simply via direct analysis shows how to create an entity with a proposed property(ies). Can be done for contrapositive, i.e. via showing that a contrapositive would not be able to exist due to potential contradiction with given axioms.

Proof by exhaustion is yet another, mostly used in computing, direct analysis without much deduction but instead with more direct checking for solutions.

Combinatorial proof, again direct either for a contrapositive (also direct in a sense), takes advantage of combinatorics to count two values in different way. As noted, direct again, using at least two elements of a knowledge set, i.e. two methods for counting something. The same applies to statistical proofs.

So, as we see, in general, we don’t need that many words to talk about proofs. Basically, we always use a knowledge set (including axioms) to deduce from and based on the knowledge we have built on the knowledge set, we either try to tackle the problem face on, from behind or break it into pieces. Finding a contradiction is just making assumptions to minimize the amount of analysis, ie. part of breaking into pieces, and it is more of a method rather than a general guideline. Via proof by contradiction, we can just spot the cul-de-sacs. Via the construction proofs, we just use direct (or any other combination (sequence) of methods) to show that the object with a property exists or cannot exist. Induction is just another direct approach, but takes advantage of iteration supported by the character of integers, i.e. that (n+1) is always the next integer after (n).


About misha

Imagine a story that one can't believe. Hi. Life changes here. Small things only.
This entry was posted in Mathematics. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s