Proof Methods

What is a proof?

A proof is a logical argument that tries to show that a statement is true. In math, and computer science, a proof has to be well thought out and tested before being accepted. But even then, a proof can be discovered to have been wrong. There are many different ways to go about proving something, we’ll discuss 3 methods: direct proof, proof by contradiction, proof by induction. We’ll talk about what each of these proofs are, when and how they’re used.

Ques. What are the different proof methods?

Answer:

We have learnt different techniques to prove mathematical statements.

1. Direct proof :The simplest (from a logic perspective) style of proof is a direct proof. Often all that is required to prove something is a systematic explanation of what everything means. Direct proofs are especially useful when proving implications. The general format to prove P→Q is this:

Assume P Explain, explain, …, explain. Therefore Q

2. Contrapositive

Recall that an implication P→Q is logically equivalent to its contrapositive ¬Q→¬P.

There are plenty of examples of statements which are hard to prove directly, but whose contrapositive can easily be proved directly. This is all that proof by contrapositive does. It gives a direct proof of the contrapositive of the implication. This is enough because the contrapositive is logically equivalent to the original implication.The skeleton of the proof of P→Q by contrapositive will always look roughly like this:

Assume ¬Q. Explain, explain, … explain. Therefore ¬P

3. Proof by contradiction

If we can prove that ¬P leads to a contradiction, then the only conclusion is that ¬P is false, so P is true. That's what we wanted to prove. In other words, if it is impossible for P to be false, P must be true.

Proof by cases

The idea is to prove that P is true by proving that Q→P and ¬Q→P for some statement Q. So no matter what, whether or not Q is true, we know that P is true. In fact, we could generalize this. Suppose we want to prove P.

We know that at least one of the statements F

Q1,Q2,…,Qn are true. If we can show that Q1→P and Q2→P and so on all the way to Qn→P, then we can conclude P. The key thing is that we want to be sure that one of our cases (the Qi's) must be true no matter what.

4. Proof by induction

Step 1: Consider an initial value for which the statement is true. It is to be shown that the statement is true for n = initial value.

Step 2: Assume the statement is true for any value of n = k. Then prove the statement is true for n = k+1. We actually break n = k+1 into two parts, one part is n = k (which is already proved) and try to prove the other par

Ques. Explain proof by counter example.

Answer:

A proof by counterexample is not technically a proof. It is merely a way of showing that a given statement cannot possibly be correct by showing an instance that contradicts a universal statement.

For example, if you are trying to prove the statement "All cheesecakes are baked in Alaska." and you did not know whether to prove it by contrapositive or contradiction, all I would have to do is bake a cheesecake right in front of you here in Texas and then you would know that your efforts had been in vain.

To give a counterexample, I have to find an integer n such n2 is divisible by 4, but n is not divisible by 4 — the “if” part must be true, but the “then” part must be false. Consider n = 6. Then n2 = 36 is divisible by 4, but n = 6 is not divisible by 4. Thus, n = 6 is a counterexample to the statement.

Ques. Write a short note on the following with example:

Proof by contrapositive

Proof by exhaustive cases

Proof by cases

Answer:

Proof by Contrapositive:

In mathematics, proof by contrapositive, or proof by contraposition, is a rule of inference used in proofs, where one infers a conditional statement from its contrapositive."if A, then B" is inferred by constructing a proof of the claim "if not B, then not A" instead.

Truth Table is as follows:

Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases, and where each type of case is checked to see if the proposition in question holds.[1] This is a method of direct proof. A proof by exhaustion typically contains two stages:

A proof that the set of cases is exhaustive; i.e., that each instance of the statement to be proved matches the conditions of (at least) one of the cases.
A proof of each of the cases.

Proof by exhaustion can be used to prove that if an integer is a perfect cube, then it must be either a multiple of 9, 1 more than a multiple of 9, or 1 less than a multiple of 9.

Proof By Cases:

You can sometimes prove a statement by:

1. Dividing the situation into cases which exhaust all the possibilities; and

2. Showing that the statement follows in all cases.

For example, if I know that x is a real number and I'm proving something about x, here are some ways I could take cases:

(a)