Ch.2 Proofs 


In this section we introduce the notion of a proof and describe methods for constructing proofs. A proof is a valid argument that establishes the truth of a mathematical statement.


In our discussion we move from formal proofs of theorems toward more informal proofs.


The methods of proof discussed in this chapter are important not only because they are used

to prove mathematical theorems, but also for their many applications to computer science.


These applications include verifying that computer programs are correct, establishing that operating systems are secure, making inferences in artificial intelligence, showing that system specifications are consistent, and so on. Consequently, understanding the techniques used in proofs is essential both in mathematics and in computer science.

 

                                                 

 

2.1 Mathematical Systems, Direct Proofs, and

    Counterexamples


2.2 More Methods of Proof Problem-Solving Corner:

    Proving Some Properties of Real Numbers


2.3 Resolution Proofs (Skipped)


2.4 Mathematical Induction Problem-Solving Corner:

    Mathematical Induction


2.5 Strong Form of Induction and

    the Well-Ordering Property







2.1 Mathematical Systems, Direct Proofs, and Counterexamples


A mathematical system consists of Axioms(propositions that are assumed TRUE, Axioms are TRUE), Definitions and Undefined terms.


Definitions are used to give a precise meaning to a new term.

Theorem is a proposition that has been proved to be true.

                Special kinds of theorems are lemmas and corollary.

Lemma is useful in proving another theorem.

Corollary is a theorem that follows easily from another theorem.

An argument that establishes the truth of a theorem is a proof.


Point and line are undefined terms

 Two triangles are congruent if their vertices can be paired so that the corresponding

    sides and corresponding angles are equal.


 Two angles are supplementary if the sum of their measures is .


 

Example  1.2

 

The real numbers furnish another example of a mathematical system.

 Among the axioms are

 

  and , (가환).

 

 For , the absolute value


Example  1.5

 

 Example of theorems real numbers are

, .

and       . (Transitive)


Example  1.6

 

 An example of a lemma about real numbers is

If , then either or .



*Direct Proofs

For all , , , ,       .

Using direct proof

 is true        is true.


 

Definition  1.7

 

If is an integer, then

  is even number      an integer such that .

  is odd number      an integer such that

 

 Example  1.8

 

 The integer is even.

  an integer such that

  is divisible by .


 Example  1.9

 

 The integer is odd.

  an integer such that .

 

Example  1.10

 

 Give a direct proof of the theorem “if is odd, then is odd.”

Proof

Let be arbitrary integers.

By definition, is odd, there exists an integer such that .

.

By definition of an odd integer, is odd.  


 

Example  1.11

 

 Given a direct proof of the following statement. For all sets , and ,

.

  

 

Direct Proof


 Another way:

                 

                 

                   



Example  1.12

 

  For all real numbers , , , ,

if and , then .


Example  1.13

 

 We illustrate by giving two proofs of the statement

  for all sets and .

Proof 1

Show that for all ,

       

and

      

Let          or   .

          

                

In either case, .

Let          or   .

      

            .

Therefore, .

In either case, .


Proof 2

Letting denote the universal set, we obtain

       

                           [Distributive law]

                                 [Complement law]

                                      [Identity law]  



Disproving a Universally Quantified Statement

 

To disprove

we simply need to find one member in the domain of discourse that makes false. Such a value for is a counterexample.



Example  1.14

 

 The statement

( is prime)

 is false.

Counterexample, is not prime when .

 

Example  1.15

 

 If the statement

  for all sets , and .

 is true, prove it: otherwise, give a counterexample (disprove).

 

 

 


Proof 

         

 


2.2 More Methods of Proof


Discuss several more methods of proof:

Proof by contradiction, Proof by contrapositive, Proof by cases, Proofs of equivalence, existence Proofs



* Proof by Contradiction (or Reductio ad Absurdum)


Assuming that the hypothesis is true  and  the conclusion is false, and finding a contradiction to Establishes .

(If and are true then using and (as well as other axioms, theorems) derives a contradiction.)

                               * A contradiction is a proposition of the form .


A proof by contradiction is an indirect proof

since to establish using proof by contradiction.

We derive and then conclude that is true.



The propositions

   and     Using proof by contradiction

are equivalent.


Using a truth table: The equivalence relation is

 


 Example  2.1

 

 Using proof by contradiction, prove that

, is even      is even.

Proof 

Using proof by contradiction.      Induce contradictions.

 



Example  2.2

 

 We will given a proof by contradiction of the following statement:

 and ,       either or .

Proof 

Using proof by contradiction.

 and .

Suppose that the conclusion is false, that is, that is true.

By De Morgan’s laws of logic

.

,       .

At this point, we have derived a contradiction : and .

We conclude that and ,       either or



 Example  2.3

 

 We will prove that is irrational using proof by contradiction.

Proof  (Using proof by contradiction.)

  

 


* Proof by Contrapositive

 

We have proved

.

 is true      is true.

 and are equivalent.

This special case of proof by contradiction is proof by contrapositive (대우). 


Example  2.4

 

 Use proof by contrapositive (대우) to show that

is irrational      is irrational.

Proof 

Letting be an arbitrary real number.

The contrapositive of the given statement is

 is not irrational      is not irrational

or equivalently

 is rational      is rational.

Suppose that is rational.

Then for some integers and .

Now .

Since is the quotient of integers, is rational.

The proof is complete. 



* Proof by Cases (Exhaustive proof)


Proof by cases is used when the original hypothesis naturally divides itself into various cases. (and Prove each case separatedly)


For example, the hypothesis “ is a real number” can be divided into cases:

(a) is a nonnegative real number 

(b) is a negative real number.


Suppose that the task is to prove and that is equivalent to ( are the cases).

Instead of proving

,

we prove

.

is true.


 and are equivalent.



* Exhaustive proof

 

Sometimes the number of cases to prove is finite and not tool large so we can check them all one by one.

 

 Example  2.5

Exhaustive proof

Show that there are no solutions in positive integers and of .

Proof 

 


 


 Example  2.6

 

 is “If and are positive integers with , then ,”where the domain

 consists of all nonnegative integers. Show that is true.

Proof 

The proposition is “If , then .

”Because , the conclusion of the conditional statement “If , then ”is true.

Hence, this conditional statement, which is , is true.

This is an example of a trivial proof.


* Proof of Equivalence

Some theorems are of the form

      .

Such theorems are proved by using the equivalence

that is, to prove “      ,” prove “      ” and “      .”



 Example  2.7

 

 Prove that , is odd       is even.

Proof 

Prove that is odd        is even.

If is odd then for some integer .

.

 is even.

Prove that is even      is odd.


If is even then for some integer .

.

Therefore, is odd.                                                   

 



Example  2.8

 

 Prove that for all real numbers and all positive real numbers ,

       .

Proof 

If , then

.

If , then

.

That is,

      .

To show

      .

If , then

.

If , then . Since       .

.

In either case, we have proved that .

 


Example  2.9

 

 Let , and be sets. Prove that the following are equivalent:

(a)        (b)        (c) .

Proof 

 



* Existence Proofs

A proof of

(2.4)                                 

is an existence proof.

One way to prove (2.4) is to exhibit one member in the domain of discourse that makes true.


Example  2.10

 

 Let and be real numbers with .

 Prove that there exists a real numbers satisfying .

Proof 

It suffices to find one real number satisfying .

            

            

The real number

,

halfway between and , surely satisfies

 


 Example  2.11

 

 Prove that there exists a prime such that is composite (i.e. not prime).

Proof  [Constructive proof]

For the prime , is composite:

http://en.wikipedia.org/wiki/Mersenne_prime


Example  2.12

 

 Let

 be the average of the real numbers , , , .

 Prove that there exists such that .

Proof 

We use proof by contradiction and assume the negation of the conclusion

.

By the generalized De Morgan’s laws for logic, this latter statement is equivalent to

or

.

Thus we assume

.

Adding these inequality yields

      ,

which contradicts the hypothesis

.

Therefore, there exists such that .  



2.4 Mathematical Induction

 


The Mathematical Induction is a proof technique to prove a statement is true for every positive integer .  (by showing 2 steps)


A sequence of blocks numbered , , sits on an (infinitely) long table and that some blocks are marked with an “.” Suppose that

(2.4.1)       The first is marked.

(2.4.2)       For all , if block is marked, then block is also marked.

We claim that (2.4.1) and (2.4.2) imply that every block is marked.



[Principle of Mathematical Induction]

Suppose that we have a propositional function whose domain of discourse is the set of positive integers.

Suppose that

1. Basis Step                  is true.  

2. Inductive Step             If is true, then is true, for all .


Then is true for every positive integer . (Induction means Mathematical Induction.)



 Definition  4.1

 

For nonnegavive integer , factorial is

 If , .

Special case, .



 Example  4.3

 

 Use induction to show that

(4.9)                             n !  >=   2^{n-1}       for all .



Verify that the statements

, , , are true, where .

Basic Step

[Show : is true.]

The Basic Step is to prove that the propositional function is true for the smallest value in the domain of discourse.

Inductive Step

[Assume : for all , if is true], then [Show : is true].



Example  4.4

  Geometric Sum

 Use induction to show that if

(4.12)           where , for all .

Basis Step

For , is true.

Inductive Step

[Assume : If , then is true for .]

[Show  true for .]

Now

                                   

                                   

 is true.

By Principle of Mathematical Induction,

 is true for all .



 Example  4.5

 

 Use induction to show that is divisible by for all .



If a set has elements, the power set of , has elements.



Theorem  4.6

 

 If , then

 (4.13)                              

 for all .

Proof 

The proof is by induction on .

Basis Step ()

If , is the empty set.

The only subset of the empty set is the empty set itself; this,

.

Thus, is true for .

Inductive Step

[Assume : holds for .]

[Show  true for .]

Let be a set with elements. Choose .

 

Exactly half of the subsets of contain , and exactly half of the subset of do not contain .

 

Each subset of that contain can be paired uniquely with the subset obtained by removing from .

Thus exactly half of the subsets of contain , and exactly half subsets of do not contain .

 

 is the set obtained from by removing , has elements.

 

By the inductive assumption,    | P(Y) |  =  2^n .

 

But the subsets of are precisely the subsets of that do not contain .

From the argument in the preceding paragraph, we conclude that

.

Therefore

.

(2.4.13) hold for and the inductive step is complete.

By the Principle of Mathematical Induction,

(2.4.13) holds for all .                                                   

 

Example 2.4.7    A Tiling Problem

 


       

 

 

Loop invariant  [Factorial Computation]

Statement is true After each iteration of the loop is true

A loop invariant is true after the loop finishes.

 

For example, a loop invariant for a while loop

 

  while(condition)

   // loop body

 


Example 4.8

 

We use a loop invariant to prove that when the pseudocode

       

        

       which () {

         

         fact = fact*

       }

 

terminates, is equal to .

We prove that is an invariant for the while loop.

Before the while loop begins executing, and , so .

Assume that .

If is true, becomes and becomes

**

We have proved the Inductive Step.

 is an invariant for the while loop.

The while loop terminates when .

  is an invariant, at this point, .



2.5 Strong Form of Induction and the Well-Ordering Property

 

 

Strong Form of Mathematical Induction

 

 

 To prove is true for all positive integers , where is a propositional function, we complete two steps:

1. Basis step: Show is true.

2. Inductive step:  For all , if is true for all , (the inductive hypothesis), then  is true.     Then is true for every integer .

 

[Another way to state (Strong From of Mathematical Induction)]

 

1. Basis step: Show is true.

2. Inductive step:  Assume is true for all , (the inductive hypothesis), Show is true.  Then is true for every integer .


 

 Example  5.1

 

 Show that postage of four cents or more can be achieved by using only 2-cent, 5-cent stamps.

 is the floor of . is the greatest integer less than or equal to .


Example  5.2

 

 Suppose that the sequence , , is defined by the equations

,        for all   n >=  1.

 

We want to prove a statement for all  n >=  1  involving .

 

 

Example  5.3

 

 Define the sequence , , by the equations

,        for all .

 We want to prove a statement for all involving .

The Inductive Step will assume the truth of the statement involving .

What are the Basis Steps?

In this example, and

.

In the Inductive Step,

taking       .

Because , it follows then .

If , then .

Thus we must add to the Basis Step .

If , then and so .

Therefore if and , inequality ( ) is satisfied.

Thus the Basis Step are and .  



* Well-Ordering Property

 

The Well-Ordering Property for nonnegative integers states that every nonempty set of nonnegative integers has a least element.

         This property is equivalent to the two forms of induction.


  We use the Well-Ordering Property to prove something familiar from long division:

     divided by

 is dividend, is divisor, is quotient, is remainder,



 Example  5.5

 

 We divide by ,

  The quotient and the remainder .

   satisfies , that is, .

.



 Theorem  5.6

Quotient-Remainder Theorem

 If and , , there exist integers (quotient) and (remainder) satisfying

   .

  and are unique; that is, if

      and     

then and .

Proof

Let 

.

Show that is nonempty.

If , then

so .

Suppose that .

Since is a positive integer, .

Thus

.

In this case, .

Therefore is nonempty.

Since is nonempty set of nonnegative integers,

by Well-Ordering Property,

 has a smallest element, which we denote .

We let denote the specific of for which . Then

.

Since , . [Show that .] (BWOC) Suppose that . Then

.

Thus . Also .

But is the smallest integer in .

This contradiction shows that .

Shown that if and , , there exist integers and satisfying 

          


(2) [uniqueness] We turn now to the uniqueness of and . Suppose that

             and               .

We must show that and .

Subtracting the previous equations, we obtain

,

which can be rewritten

The preceding equation shows that divides .

However, because and ,

.

But the only integer strictly between and divisible by is .

Therefore,

.

Thus,

:

hence

.

The proof is complete. 

 

 


HW  Exercises   ( in ..., p. 86, p.93, p.102, p.113 , ... ) 

 



     Solve problems # 1+ 5k  or Exercises   1,16,19

 

 




Quiz 1

 

 


Copyright by SGLee, SKKU  sglee@skku.edu