3
$\begingroup$

I am currently reading Kenneth Rosen's book on Discrete Mathematics.

There I came across these two kind of proof strategy.

  1. Proof By Cases
  2. Exhaustive Proof

But I was not able to figure out the differences among them.

Here are the definitions mentioned in the book.

To prove a conditional statement of the form (p1 ∨ p2 ∨· · · ∨ pn) → q the tautology [(p1 ∨ p2 ∨ · · · ∨ pn) → q] ↔ [(p1 → q) ∧ (p2 → q) ∧ · · · ∧ (pn → q)] can be used as a rule of inference. This shows that the original conditional statement with a hypothesis made up of a disjunction of the propositions p1, p2, ... , pn can be proved by proving each of the n conditional statements pi → q, i = 1, 2, . . . , n, individually. Such an argument is called a proof by cases. Sometimes to prove that a conditional statement p → q is true, it is convenient to use a disjunction p1 ∨ p2 ∨ · · · ∨ pn instead of p as the hypothesis of the conditional statement, where p and p1 ∨ p2 ∨ · · · ∨ pn are equivalent.

EXHAUSTIVE PROOF : Some theorems can be proved by examining a relatively small number of examples. Such proofs are called exhaustive proofs, or proofs by exhaustion because these proofs proceed by exhausting all possibilities. An exhaustive proof is a special type of proof by cases where each case involves checking a single example.

Please provide an example along with the explanations to illustrate the differences.

Thank You.

$\endgroup$
  • $\begingroup$ According to your own quote, the source you're quoting proceeds to provide some examples. If those examples are not good enough for you and you want different examples instead, you should probably state in your question what the examples in the book that are not good enough for you are, and also what you find lacking about them. $\endgroup$ – Henning Makholm Sep 17 '16 at 18:32
  • 1
    $\begingroup$ Also: You managed to type the sentence "An exhaustive proof is a special type of proof by cases" while typing in your quote. Does that sentence not answer your question at least halfway? $\endgroup$ – Henning Makholm Sep 17 '16 at 18:33
  • $\begingroup$ @HenningMakholm. Yes it does, but I really want to know the difference between them. I know that exhaustive proof is a kind of proof by cases. But what is that special case when proof by cases become exhaustive proofs. The examples mentioned in the book doesn't really elaborate the difference. $\endgroup$ – Navneet Srivastava Sep 17 '16 at 18:44
  • $\begingroup$ See EXAMPLE 1 [page 93] Prove that $(n + 1)3 ≥ 3n$ if n is a positive integer with $n ≤ 4$. Proof : consider $n=1 \lor n=2 \lor n=3 \lor n=4$ and apply proof by cases. $\endgroup$ – Mauro ALLEGRANZA Sep 17 '16 at 18:44
  • 1
    $\begingroup$ @MauroALLEGRANZA But how is it different from Example 3 [page 93] proof that is if n is an integer then n2 ≥ n. Proof : consider (n = 0 ∨ n ≥ 1 ∨ n ≤ -1) → n2 ≥ n. The one you mentioned is given as an example of exhaustive proof while the example I have mentioned is given as an example of proof by cases. $\endgroup$ – Navneet Srivastava Sep 17 '16 at 18:51
3
$\begingroup$

Proof by cases tends to be about splitting your proposition into cases, at least some of which are general while an exhaustive proof looks at every case in a way that is not general. For example if one were to prove a property about natural numbers, it might be easier to say prove it for even numbers and then prove it for odd numbers separately. This would be proof by cases. On the other hand, if one were to prove a property about, say, all natural numbers less than 10 then one could just check the proposition for each of the natural numbers. There would be no generality and this would be an exhaustive proof.

Here are two examples, see if you can decide which method might apply to which.

  1. The maximum diameter for a tree on 10 vertices where no vertex has degree 2 is 5
  2. Any isometry of $\mathbb R^3$ can be represented as the product of up to three reflections.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.