Chapter 2   Proofs

      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.





1. Discrete Math - 7th Edition , Richard Johnsonbaugh, Pearson

2.1 Mathematical Systems, Direct Proofs, and


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

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 k = 7 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.”


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 ,




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).







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.


Using proof by contradiction.      Induce contradictions.


Example  2.2


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

 and       either  or .


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.


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 .



 Example  2.6


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

 consists of all nonnegative integers. Show that  is true.


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.


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 ,



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) .



* Existence Proofs

A proof of


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 .


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:

Example  2.12



 be the average of the real numbers , , , .

 Prove that there exists  such that .


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



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 .]




 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


 for all .


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




(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



   // 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 , 1 <= k < n (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 


then  and .




Show that  is nonempty.

If , then

so .

Suppose that .

Since  is a positive integer, .



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 .







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


Copyright @ 2018 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
*This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2017R1D1A1B03035865).