Definitions

Proving Existential Statements

Proving Universal Statements

Disproof by Counterexample

In order to evaluate whether a mathematical statement is correct or not, you must understand what the statement means. First, we have to look at the definitions below:

D E F I N I T I O N S

Even An integer n is even, if and only if, n = 2k for some integer k. Symbolically, if n is an integer, then

n is even   an integer k such that n = 2k.
Odd An integer n is odd, if and only if, n = 2k + 1 for some integer k. Symbolically, if n is an integer, then

n is odd   an integer k such that n = 2k + 1
Prime An integer n is prime, if and only if, n > 1 and for all positive integers p and q, if n = p * q, then p = 1 or q = 1. Symbolically, if n is a positive integer, then

 n is prime   positive integers p and q, if n = p * q then p = 1 or q = 1.
Composite An integer n is composite, if and only if, n = p * q for some positive integers p and q with p 1 and q 1. Symbolically, if n is an integer, then


 n is composite positive integers p and q such that n = p * q
and p1 and q 1.



Consider the following examples:

Example: Is -48 even?
Solution: -48 is even, since -48 = 2(-24).
Example: Is 307 odd?
Solution: 307 is odd, since 307 = 2(153) + 1.








Proving Existential Statements

Referring to Section 1.6, a statement in the form:

is true if, and only if, Q(x) is true for at least one x in M.

There are two ways to prove this statement. The first one is to find an x in M that makes Q(x) true. Another way is to give a set of directions for finding such an x. Both of these methods are called constructive proofs of existence.

Conversely, a nonconstructive proof of existence involves showing either:

  1. that the existence of a value of x that makes Q(x) true is guaranteed by an axiom or a previously proved theorem; or

  2. that the assumptions that there is no such x leads to a contradiction.

The disadvantage of a nonconstructive proof is that it may give virtually no clue about where or how x may be found.








Proving Universal Statements

Again referring to Section 1.6, a universal statement is in the form:

When M is finite such a statement can be proved by the method of exhaustion. As the name implies, this technique tests each element (exhaust the possibilities) of the domain to show the truth of the universal statement. This method can be used when there are a finite number of elements that satisfy the condition P(x).

Another proof method is the method of direct proof. The steps are as follow:

1. Express the statement in the form as the above statement.
2. Start the proof by assuming x is an element of M for which the hypothesis P(x) is true.
3. Show that Q(x) is true by definitions, previous result and the rules for logical inference.







Disproof by Counterexample


Consider a statement of the form

Suppose that we wish to prove that this statement is false. In order to disprove this statement, we have to find a value of x in M for which P(x) is true and Q(x) is false. Such an x is called a counterexample.

Furthermore, proving that this statement is false is equivalent to showing that its negation is true. The negation of the above statement is

Finding an x that makes the above statement true will disprove the original statement.









   Go to next section review.
   Go to Class Agenda.