Proving Universal Propositions

 

Now let us talk about method of direct proof from the practical or "computational point of view". That is, how do we actually prove universal propositions using this method. Recall, a statement has a form:

∀ x ∈ D, if P(x), then Q(x)

When the set of domain D is finite such a statement can be proved by the method of exhaustion.

 

Method of Direct Proof

In a direct proof we start with the hypothesis of a statement and make one deduction after another until we reach the conclusion. In a little more technical language we say that the underlying idea of direct proof is to show that every element of a domain satisfy a certain property and we accomplish this task as follows:

1. Suppose x is a particular but arbitrary chosen element of the domain.

2. Show that x satisfy the property.

For instance, suppose the property has a form:

if P(x), then Q(x)

We know from the definition of conditionals that the statement:

if P(x), then Q(x)

can be false when antecedent P(x) is true and consequent Q(x) is false.

 

Therefore, to show that

if P(x), then Q(x)

is true. We do the following two things:

1. Supposition that antecedent P(x) is true.

2. Show that consequent Q(x) must also be true.

 

In general, to prove an universal conditional statement of the form:

∀ x ∈ D, if P(x), then Q(x)

We do the following:

1. We suppose x is a particular but arbitrarily chosen element of domain D that satisfy antecedent P(x). That is, proposition function P(x) becomes true for x.
2.  Then, we show that x satisfies consequent Q(x). That is, proposition function Q(x) becomes true for x.

 

Let us formalize the above idea. We say that we execute the following steps to prove universal statements:

Step 1. Express the statement to be proved in the form: ∀ x ∈ D, if P(x), then Q(x)
Step 2. Now, suppose x is a particular but arbitrarily chosen element of D for which the antecedent P(x) is true.
Step 3. Finally, show that the consequent Q(x) is true by using definitions, previously established results, and the rules of inference.

 

As an example, consider the following universal statement (theorem):

If the sum of any two integers is even, then so is their difference.

 

First, we will proof the given theorem following above mentioned three steps. Then, we will proof formally.

Step 1. The statement has the form: 

∀ integers m and n, if m + n is even, then m - n is even.
Step 2. Suppose m and n are particular but arbitrarily chosen integer such that m + n is even. That is,

Suppose m and n are any integers and m = n is even.
Step 3. Recall, to show that the consequent is true, we are allowed to use only definitions, theorems (i.e. previously established results) and the rules of inference (such as substitution rule and modus ponens.) Thus, according to the definition, any even integer can be written in the form:

2 . (Some integer)

Therefore, using this definition, we may write:

m + n = 2k for some integer k.

Now, we need to conclude that m - n is even. In other words, we need to show that m - n can be written as

m - n = 2k for some integer.

To show this, we start with the antecendent:

m + n = 2k for some integer k.

If we subtract n from both sides, we get

m = 2k - n

which we can then substitute into the expression m - n:

                     m - n  =  (2k - n) - n

                               =  2k - 2n

                               =  2(k - n)

But the right side of above equality is in form:

2 . (something)

Now the question is that is this "something" an integer? The answer is yes because both k and n are integers (why? because we said so i.e. by supposition) and the difference of two integers is an integer. Therefore, that "something" is integer. This means, we can write the consequent in the form:

m - n = 2k for some integer k.

and this is a very definition of even integer.

 

Now, let us formalize above procedure:

 

Theorem: ∀ integers m and n, if m + n is even, then so is m - n.

Proof:

Suppose m and n are integers so that m + n is even. By definition of even, m + n = 2k for some integer k. Subtracting n from both sides gives m = 2k - n. Thus,

m - n =  (2k - n) - n by substitution
=  2k - 2n combining common terms
=  2(k - n) by factoring out a 2

But (k - n) is an integer because it is a difference of integers. Hence, (m - n) equals 2 times an integer, and so by definition of even number, (m - n) is even.

This complete the proof.

 

 

 

 

--------------------------------------------------------------------------------------------------------------